目录
顺序表
顺序表的概念与结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1.静态顺序表:使用定长数组存储。
2.动态顺序表:使用动态开辟的数组存储。
实现顺序表
import java.util.Arrays;
public class MyArrayList {
public int[] elem;//定义数组
public int usedSize;//使用数组长度
//使用构造方法初始化数组
public MyArrayList(){
this.elem = new int[5];
}
//构建一个顺序表 实现操作如下
//1.打印顺序表
public void display(){ }
//2.判断数组是否满了
public boolean isFull(){ return true; }
//3.在 pos 位置新增元素data
public void add(int pos, int data) { }
//4.判断数组是否为空
public boolean isEmpty(){ return true; }
//5.判定是否包含某个元素
public boolean contains(int toFind) { return true; }
//6.查找某个元素对应的位置 即找元素的下标
public int search(int toFind) { return -1; }
//7.获取 pos 位置的元素
public int getPos(int pos) { return -1; }
//8.给 pos 位置的元素设为 value
public void setPos(int pos, int value) { }
//9.删除第一次出现的关键字key
public void remove(int toRemove) { }
//10.获取顺序表长度
public int size() { return 0; }
//11.清空顺序表
public void clear() { }
}1.打印顺序表
public void display(){
for (int i = 0;i < this.usedSize;i++){
System.out.print(this.elem[i]+" ");
}
System.out.println();
}2.判断数组是否满了
public boolean isFull(){
return this.usedSize == this.elem.length;
}3.在pos位置新增元素data
public void add(int pos,int data){
if (pos < 0 || pos > usedSize){//考虑pos位置不合法的情况
System.out.println("pos位置错误");
return;
}
if (this.isFull()) { //判断满了则二倍扩容
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
System.out.println("扩容！");
}
for (int i = usedSize-1;i >= pos;i--){//从后到前 依次挪后一个数据
elem[i+1] = elem[i];
}
this.elem[pos] = data;//把data赋值给pos位置
this.usedSize++;//添加后 数组使用长度加一
}4.判断数组是否为空
public boolean isEmpty(){
return usedSize == 0;
}5.判断是否包含某个元素
public boolean contains(int toFind){
if (isEmpty()){
System.out.println("顺序表为空！");
return false;
}
for (int i = 0;i < usedSize;i++){
if (this.elem[i] == toFind){
System.out.println("该数组包含"+toFind);
return true;
}
}
System.out.println("该数组不包含"+toFind);
return false;
}6.查找某个元素对应的位置
public int search(int toFind){
if (isEmpty()){
System.out.println("顺序表为空！");
return -1;
}
for (int i = 0;i < usedSize;i++){
if (this.elem[i] == toFind){
System.out.println("该元素的位置是:elem["+i+"]");
return i;
}
}
System.out.println("该数组不包含"+toFind);
return -1;
}7.获取pos位置的元素
public int getPos(int pos){
if (pos < 0 || pos >= usedSize){//考虑pos位置不合法的情况 注意pos是下标
//return -1 不可写 避免pos元素也是-1的情况
throw new ArrayIndexOutOfBoundsException("pos位置错误");//自定一个异常
}
System.out.print(pos+"位置的元素是：");
return this.elem[pos];
}8.给pos位置的元素设置为value
public void setPos(int pos,int value) {
if (pos < 0 || pos >= usedSize) {//考虑pos位置不合法的情况
throw new ArrayIndexOutOfBoundsException("pos位置错误");//手动抛出异常
}
this.elem[pos] = value;
}9.删除第一次出现的元素key
public void remove(int toRemove){
if (contains(toRemove)){//判断是否含有toRemove元素
//从toRemove的下标开始
for (int i = search(toRemove);i < usedSize-1; i++){
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
System.out.println("删除成功！");
display();
}
else System.out.println("元素不存在！");
}10.获取顺序表有效数据长度
public int size(){
System.out.println("有效数据长度为："+usedSize);
return this.usedSize;
}11.清空顺序表
public void clear(){
for (int i = 0;i <this.usedSize;i++){
this.elem[i] = 0;//如果是引用类型 this.elem[i]=null;
}
this.usedSize = 0;
System.out.println("清空成功！");
}顺序表的问题及思考
1. 顺序表中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考: 如何解决以上问题呢?下面给出了链表的结构。
链表
链表的概念与结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构:
单向、双向 带头、不带头 循环、非循环
无头单向链表：
无头双向链表：
虽然有这么多的链表的结构，但是重点掌握两种:
1.无头单向非循环链表:结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2.无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
单链表的实现
class Node{//定义一个节点类
public int value;//定义一个值域 整型
public Node next;//定义一个next域 Node类型 因为next指向下一个节点的地址
//构造方法 用于初始化对象
public Node(int value){
this.value = value;
}
}
public class MyLinkedList {
public Node head;//单链表头节点的引用 在链表内定义一个表头head
//1.生成一个单链表
public void createLinkedList(){
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(1);
Node node4 = new Node(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
this.head = node1;
}
//2.打印链表
public void show(){
Node cur = this.head;
while (cur != null){
System.out.print(cur.value+" ");
cur= cur.next ;
}
System.out.println();
}
//3.得到链表长度
public int size(){
int count = 0;
Node cur = this.head;
while (cur != null){
count++;
cur = cur.next;
}
System.out.println("链表长度为："+count);
return count;
}
//4.头插法 把新节点插入链表头部
public void addFirst(int data){
Node node = new Node(data);//定义一个插入的新节点
node.next = this.head;//当前head地址赋值给新节点的next
this.head = node;//把head换给新节点
}
//5.尾插法 把新节点插入链表尾部
public void addLast(int data){
Node node = new Node(data);
if (head == null){ //判断链表是否为空 如果为空下方cur.next会报错
this.head = node;
return;
}
Node cur = this.head;
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
//6.任意位置插入 第一个数据节点为0下标
public boolean addIndex(int index,int data){
if (index < 0 || index > size()){//先判断index位置合法性
System.out.println("插入位置错误！");
return false;
}
if (index == 0){//特殊位置 插入0位置 即头插法
addFirst(data);
return true;
}
if (index == size()){//特殊位置 插入末尾 即尾插法
addLast(data);
return true;
}
Node node = new Node(data);
Node cur = findIndex(index);//找index-1位置的节点 即插入点左侧
node.next = cur.next;//新节点next默认为null 给其赋值cur.next即所插入位置的右侧
cur.next = node;//新节点node赋值给左侧的cur.next
return true;
}
//为方便实现6. 写一个查找index-1位置的节点
public Node findIndex(int index){
Node cur = this.head;
while (index-1 != 0){
cur = cur.next;
index--;
}
return cur;
}
//7.查找是否包含key是否在单链表中
public boolean contains(int key){
Node cur = this.head;
while (cur.next != null){
if (cur.value == key){
System.out.println("该链表包含"+key);
return true;
}
cur = cur.next;
}
System.out.println("链表不包含"+key);
return false;
}
//8.删除第一次出现的key的节点
public void remove(int key){
Node cur = this.head;
if (contains(key)){
if (this.head.value == key){//判断第一个值是否为key
this.head = this.head.next;
return;
}
while (cur.next != null){
if (cur.next.value == key){
cur.next = cur.next.next;
System.out.println("删除成功");
return;
}
}
}
else {
System.out.println("删除失败");
}
}
//9.删除所有值为key的节点 只遍历链表一次
public void removeAllKey(int key){
if (this.head == null){
System.out.println("链表为空！");
return;
}
Node prev = this.head;//定义一个cur.value的前驱
Node cur = this.head.next;//从第二个开始遍历
while (cur != null){
if (cur.value == key){
prev.next = cur.next;
} else{
prev = cur;
}
cur = cur.next;
}
if (this.head.value == key)//第一个值就是key的情况
this.head = this.head.next;
}
//10.清空链表
public void clear(){
this.head = null;//粗暴方法
}
}
双链表的实现
class Node2{
public int value;
public Node2 next;
public Node2 prev;
//提供构造方法
public Node2(int value) {
this.value = value;
}
}
public class DoubleLinkedList {
public Node2 head;//在双向链表内定义一个表头head 谁的属性定义在谁的类中
public Node2 last;//定义一个表尾last
//1.生成一个双向链表
public void create(){
Node2 node1 = new Node2(1);
Node2 node2 = new Node2(2);
Node2 node3 = new Node2(3);
Node2 node4 = new Node2(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
this.last = node4;//表尾
node4.prev = node3;
node3.prev = node2;
node2.prev = node1;
this.head = node1;//表头
}
//2.打印链表
public void display(){
Node2 cur = this.head;
while (cur != null){
System.out.print(cur.value+" ");
cur = cur.next;
}
System.out.println();
}
//3.得到链表长度
public int size(){
int count = 0;
Node2 cur = this.head;
while (cur != null){
count++;
cur = cur.next;
}
System.out.println("链表长度为："+count);
return count;
}
//4.头插法
public void addFirst(int data){
Node2 node2 = new Node2(data);
if (this.head == null){
this.head = node2;
this.last = node2;
}
else {
node2.next = this.head;
this.head.prev = node2;
this.head = node2;
}
}
//5.尾插法
public void addLast(int data){
Node2 node2 = new Node2(data);
if (this.head == null){
this.head = node2;
this.last = node2;
}else {
this.last.next = node2;
node2.prev = this.last;
this.last = node2;
}
}
//6.任意位置插入 第一个数据节点为0下标
public boolean addIndex(int index,int data){
if (index < 0 || index > size()){
System.out.println("插入位置不合法！");
return false;
}
if (index == 0){
addFirst(data);
return true;
}
if (index == size()){
addLast(data);
return true;
}
Node2 cur = this.head;
Node2 node2 = new Node2(data);//定义应插入的新节点
while (index != 0 ){
cur = cur.next;
index--;
}//此时cur走到待插入位置 即插入点右侧
node2.next = cur;
cur.prev.next = node2;
node2.prev = cur.prev;
cur.prev = node2;
return true;
}
//7.查找是否包含key是否在双链表中
public boolean contains(int key){
Node2 cur = this.head;
while (cur != null){
if (cur.value == key){
return true;
}
cur = cur.next;
}
return false;
}
//8.删除第一次出现的key的节点
public void remove(int key){
Node2 cur = this.head;
if (contains(key)){
while (cur.value != key){
cur = cur.next;
}//找到所删除的节点 接下来判断节点位置
//节点在头部同时也在尾部 即只有一个节点
if (cur == this.head && cur.next ==null){
clear();
return;
}
if (cur == this.head){//节点在头部
cur.next.prev = null;
this.head = this.head.next;
return;
}
if (cur.next ==null){//节点在尾部
cur.prev.next = null;
this.last = this.last.prev;
return;
}
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
System.out.println("不包含"+key+" 删除失败！");
}
}
//9.删除所有值为key的节点
public void removeAllKey(int key){
int count = 0;
while (contains(key)){
remove(key);
count++;
}
if (count != 0){
System.out.println("删除成功！");
}else {
System.out.println("删除失败！");
}
}
//10.清空链表
public void clear(){
//this.head = null;不可以 因为是双向链表 它还被后面所指向
while (this.head != null){//循环遍历 每一个节点的prev和next都要置为空
Node2 cur = this.head.next;//循环内部定义 改变cur
this.head.next = null;
this.head.prev = null;
this.head = cur;
}
this.last = null;//循环遍历完后 记住还有last也要置为空
System.out.println("清空！");
}
}
顺序表和链表的区别
顺序表:
1.中间或前面部分的插入删除时间复杂度O(N)
2.增容的代价比较大
3.空间连续、支持随机访问
链表:
1.任意位置插入删除时间复杂度为O(1)
2.没有增容问题 增加一个开辟一个
3.以节点为单位存储，不支持随机访问
对于顺序表
增删：移动数据时间复杂度o(n)
查找修改：顺序查找 o(n)
给定下标查找 o(1)
所以 顺序表适合查改 链表适合增删
版权声明：本文为weixin_50922984原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。