Java实现顺序表和链表结构

前言：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串。

顺序表

定义：

用一段物理地址连续的存储单元依次存储数据元素的线性结构（逻辑上连续，物理上也连续）

（1）静态顺序表：使用定长数组存储。

（2）动态顺序表：使用动态开辟的数组存储

【注意】静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以相比之下，动态数组更为灵活，可根据需要动态分配空间大小

实现方法：

增、删、改、查

增加操作：从头部插入、从尾部插入、在任意索引位置处插入

删除操作：根据索引删除元素、根据元素值删除第一个出现的该元素、根据元素值删除所有该值元素 

查找操作：根据元素值查找是否存在某元素、根据索引下标返回该处元素值、根据元素值返回索引下标 

修改操作：根据索引下标修改该处元素 

代码实现：

public class MyArray {
   private int[]data;
   private int size;
//    无参构造
   public MyArray(){
       this.data=new int[5];
   }
//    有参构造
   public MyArray(int n){
       this.data=new int[n];
   }
//    grow方法用于扩充内存
   private void grow() {
       int[] newdata= Arrays.copyOf(data,size*2);
       this.data=newdata;
   }
//    toString方法输出顺序表内容
   public String toString(){
       String str="[";
       for (int i = 0; i <size ; i++) {
           str+=data[i];
           if(i!=size-1){
           str+=",";
           }
       }
       str+="]";
       return str;
   }
//    尾插法：
   public void addLast(int value){
       if(size== data.length){
           grow();
       }
       data[size]=value;
       size++;
   }
//    头插法：
   public void addFirst(int value){
       if(size==data.length){
           grow();
       }
       for (int i = size-1; i >=0; i--) {
           data[i+1]=data[i];
       }
       data[0]=value;
       size++;
   }
//    中间任意位置插入：
   public void addIndex(int index,int value){
       if(size==data.length)
           grow();
       if(index<0||index>size){
           System.err.println("插入位置不合理！");
           return;
       }
       else {
           for (int i = size - 1; i >= index; i--) {
               data[i + 1] = data[i];
           }
           data[index] = value;
           size++;
       }
   }
//    查看当前数组中是否存在该元素
   public boolean contains(int value){
       for (int i = 0; i < size; i++) {
           if(data[i]==value)
               return true;
       }
       return false;
   }
//    查找当前数组元素对应的下标
   public int getIndex(int value){
       for (int i = 0; i < size; i++) {
           if(data[i]==value){
               return i;
           }
       }
       return -1;

}
//    查找数组下标为index的元素
   public int getValue(int index) {
       if (index < 0 || index > size - 1) {
           System.out.println("输入下标不合理");
           return -1;
       }

return data[index];
   }
//    根据索引删除元素,注意将最后一个元素置为0
   public void removeIndex(int index){
       if(index<0||index>=size){
           System.err.println("输入不合法！");
       }
       for (int i = index; i <size-1; i++) {
           data[i]=data[i+1];
       }
       size--;
       data[size]=0;
   }
//    删除第一个元素值为value的元素
   public void removeValueOnce(int value){
       int a=getIndex(value);
     removeIndex(a);

}
//        删除所有元素值为value的元素
   public void removeValueAll(int value){
       for (int i = 0; i < size; i++) {
          while(i!=size||data[i]==value)
              removeIndex(i);

}

}
//    根据索引修改元素
   public void recompose(int index,int newValue){
       if(index<0||index>=size){
           System.err.println("输入不合法！");
       }

data[index]=newValue;
   }
   }

链表

定义：

逻辑上连续，物理上非连续存储。

链表由一个个节点组成，每个节点存储该节点处的元素值val 以及下一个节点的地址next，由地址next实现逻辑上连续

分类：

分类方式：

（1）单链表、双链表

（2）带虚拟头节点、不带虚拟头节点

（3）循环链表、非循环链表

按不同分类方式组合有8种：

非循环四种：

（1）不带虚拟头节点的单向链表（非循环）

（2）带虚拟头节点的单向链表（非循环）

（3）不带虚拟头节点的双向链表（非循环）

（4）带虚拟头节点的双向链表（非循环）

循环四种：

（5）不带虚拟头节点的单向链表（循环）

（6）带虚拟头节点的单向链表（循环）

（7）不带虚拟头节点的双向链表（循环）

（8）带虚拟头节点的双向链表（循环）

其中：

（1）不带虚拟头节点的单向链表（非循环）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多

（7）不带虚拟头节点的双向链表（循环）：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

实现方法：

增、删、查、改     和顺序表实现方法基本一样；

唯一注意：带虚拟头节点与不带虚拟头节点相比，带虚拟头节点避免了考虑头节点为空的特殊情况

代码实现：

（1）不带虚拟头节点的单链表：

class Node {
//    val表示存储的数值，next表示下一个节点的地址
   int val;
   Node next;

//    构造方法
   public Node(int val) {
       this.val = val;
   }
}

public class SingleList {
   //    size表示节点个数
//    head表示头节点
   private int size;
   private Node head;

//定义toString方法以输出链表内容
   public String toString() {
       String str = "";
       Node node = head;
       while (node != null) {
           str += node.val;
           str += "->";
           node = node.next;
       }
       str += null;
       return str;
   }

//将判断输入的索引是否合法抽象为方法islegal
   public boolean islegal(int index) {
       if (index < 0 || index > size) {
           return false;
       } else {
           return true;
       }
   }

//    头插法
   public void addHead(int value) {
       Node node = new Node(value);
       if (head == null) {
           head = node;

} else {
           node.next = head;
           head = node;
       }
       size++;
   }

//    中间任意位置插入
   public void addIndex(int index, int val) {
       if (!islegal(index)) {
           System.out.println("输入数据不合法！");
           return;
       }
       if (index == 0) {
           addHead(val);
           return;
       }
       Node node = new Node(val);
       Node pre = head;

for (int i = 0; i < index - 1; i++) {
           pre = pre.next;
       }
       node.next = pre.next;
       pre.next = node;
       size++;
       return;
   }

//    尾插法
   public void addLast(int val) {
       if (head == null) {
           addHead(val);
       } else {
           addIndex(size, val);
       }
   }

//    删除指定索引位置的元素
   public void removeIndex(int index) {

if (islegal(index)) {
           if (index == 0) {
               Node temp = head;
               head = head.next;
               temp.next = null;
               size--;
               return;
           } else {

Node pre = head;
               for (int i = 0; i < index - 1; i++) {
                   pre = pre.next;
               }
               Node cur = pre.next;
               pre.next = cur.next;
               cur.next = null;

size--;
           }

} else {
           System.out.println("输入数据不合法！");
       }
   }

//    根据元素值删除元素，且只删除第一次出现的该元素
   public void removeValueOnce(int val) {
       if (head.next != null && head.val == val) {
           removeIndex(0);
       } else {
           Node pre = head;
           while (pre.next != null) {
               if (pre.next.val == val) {
                   pre.next = pre.next.next;
                   pre.next.next = null;
                   size--;
                   return;

}
               pre = pre.next;
           }
       }
   }

//    根据元素值删除元素，且删除所有该元素
   public void removeValueAll(int val) {
       while (head.next != null && head.val == val) {
           Node temp = head;
           head = head.next;
           temp = null;
           size--;
       }
       if (head == null) {
           return;
       } else {
           Node pre = head;
           while (pre.next != null) {
               if (pre.next.val == val) {
                   pre.next = pre.next.next;
                   size--;
                   return;

} else {
                   pre = pre.next;
               }
           }
       }
   }

//       根据元素值删除元素，且删除所有该元素并返回头节点(带虚假节点）
   public Node removeValueAllWithDummy(int val) {
       Node dummyHead = new Node(-1);
       dummyHead.next = head;
       Node pre = dummyHead;
       while (pre.next != null) {
           if (pre.next.val == val) {
               Node cur = pre.next;
               pre.next = cur.next;
               cur.next = null;
               size--;
           } else {
               pre = pre.next;
           }
       }
       return dummyHead.next;

}

//    根据索引查元素值
   public int get(int index) {
       if (islegal(index)) {
           Node cur = head;
           for (int i = 0; i < index; i++) {
               cur = cur.next;
           }
           return cur.val;
       } else {
           System.out.println("输入数据不合法！");
           return -1;
       }
   }

//    能否查到给定的某元素值（自己写的，好像很复杂）
   public boolean contains(int val) {
       boolean a = false;
       if (head == null) {
           System.out.println("该链表为空！");
           return false;
       } else {
           Node node = head;

for (int i = 0; i < size; i++) {
               if (node.val == val) {
                   a = true;
               }
               node = node.next;
           }
       }
       return a;
   }

//    能否查到给定的某元素值，老师写的方法
   public boolean contains2(int val) {
       for (Node temp = head; temp != null; temp = temp.next) {
           if (temp.val == val) {
               return true;
           }
       }
       return false;
   }

//    根据索引修改元素值
   public void set(int index, int newValue) {
       if (islegal(index)) {
           Node node = head;
           for (int i = 0; i < index; i++) {
               node = node.next;
           }
           node.val = newValue;
           return;
       }
       System.out.println("输入数据不合法!");
   }
}

（2）带虚拟头节点的单链表

以在指定索引位置插入元素为例，理解虚拟头节点的作用即可

public class SingleListWithDummyHead {
   Node dummyNode=new Node(-1);
   int size;
//    在指定位置插入元素,因为有虚拟头节点故不用考虑index=0的情况，全部为在中间位置插入的情况
   public void addIndex(int index,int value){
//        先判断index是否合法
       if(index<0||index>size){
           System.out.println("illegal");
           return;
       }
       Node a=new Node(value);
       Node pre=dummyNode;
       for(int i=0;i<index;i++){
           pre=pre.next;
       }
       a.next=pre.next;
       pre.next=a;
       size++;
   }
}

（3）带虚拟头节点的双链表

public class DoubleLinkedList {
   private int size;
   private Node dummyHead = new Node(-1);
   private Node tail;

//    定义toString方法用以方便输出
   public String toString() {
       String s = "";
       Node node = dummyHead.next;
       while (node != null) {
           s = s + node.val;
           s = s + "->";
           node = node.next;
       }
       s += "null";
       return s;
   }

//    判断输入的索引是否合法
   private boolean isRange(int index) {
       if (index < 0 || index >= size) {
           System.out.println("输入不合法！");
           return false;
       } else
           return true;
   }

//    头插法
   public void addHead(int val) {
       Node a = new Node(val, dummyHead, dummyHead.next);
//链表为空
       if (dummyHead.next == null) {
           tail = a;
           dummyHead.next = a;
       }
//        否则链表不为空
       else {
           dummyHead.next.prev = a;
           dummyHead.next = a;
       }
       size++;
   }

//    尾插法
   public void addTail(int val) {
       Node a = new Node(val, tail, null);
//        链表为空
       if (dummyHead.next == null) {
           dummyHead.next = a;
       }
//        链表不为空
       else {
           tail.next = a;
       }
       tail = a;
       size++;
   }

//    中间位置插入
   public void addMiddle(int index, int val) {
//      判断插入位置合理否
       if (index < 0 || index > size) {
           System.out.println("输入不合法！");
       }
//        头部插入
       else if (index == 0) {
           addHead(val);
       }
//        尾部插入
       else if (index == size) {
           addTail(val);
       }
//        中间任意位置插入
       else {
//先找到要插入位置的前一个元素，可另一个方法找该元素
           Node a = new Node(val, find(index), find(index).next);
           find(index).next.prev = a;
           find(index).next = a;
           size++;
       }
   }

//    这里find的方法是找到index位置的前一个节点元素
   public Node find(int index) {
       Node f = dummyHead;
       for (int i = 0; i < index; i++) {
           f = f.next;
       }
       return f;

}

//    根据索引删除指定位置的元素
   public void removeIndex(int index) {
       if (index < 0 || index >= size) {
           System.out.println("输入不合法!");
           return;
       } else {
           find(index).next.next.prev = find(index);
           find(index).next = find(index).next.next;
           size--;
       }
   }

//    删除指定节点
   private void deleteNode(Node node) {
//        分治思想，先处理node与左边节点，再处理node与右边节点
       Node pre = node.prev;
       Node next = node.next;
//        处理左边，因为有虚拟头节点，故不用另讨论为头节点的情况
       pre.next = next;
       node.prev = null;
//       处理右边
       if (next == null) {
           tail = pre;
       } else {
           next.prev = pre;
           node.next = null;
       }
       size--;

}

//    删除指定元素值（只删除第一次出现的）
   public void removeValueOnce(int val) {
       for (Node a = dummyHead.next; a != null; a = a.next) {
           if (a.val == val) {
               deleteNode(a);
               return;
           }
       }
       System.out.println("链表中无该元素故无法删除");

}

public void removeValueAll(int val) {
       for (Node a = dummyHead.next; a != null; ) {
           if (a.val == val) {
               Node b = a.next;
               deleteNode(a);
               a = b;
           } else a = a.next;
       }
   }

//    根据索引查找元素值
   public int get(int index) {
       if (isRange(index)) {
           return find(index).next.val;
       } else {
           return -1;
       }
   }

//    查找是否存在某元素
   public boolean contains(int val) {
       Node a = dummyHead;
       while (a.next != null) {
           if (a.next.val == val) {
               return true;
           }
           a = a.next;
       }
       return false;
   }

//    修改，将指定位置元素修改为另一值
   public void set(int index, int newValue) {
       if (isRange(index)) {
           find(index).next.val = newValue;
       }

}

}

//节点类
class Node {
   int val;
   Node prev;
   Node next;

public Node(int val) {
       this.val = val;
   }

public Node(int val, Node prev, Node next) {
       this.val = val;
       this.prev = prev;
       this.next = next;
   }
}

顺序表 & 链表

顺序表：

优点：空间连续、支持随机访问

缺点：中间或前面部分的插入删除时间复杂度O(N)

           增容的代价比较大。

链表：

优点：任意位置插入删除时间复杂度为O(1)

           没有增容问题，插入一个开辟一个空间 

缺点：以节点为单位存储，不支持随机访问

来源：https://blog.csdn.net/m0_58652786/article/details/122863350