• 【数据结构】链表

    目录

    一、线性表接口

    二、单链表

    2.1 单链表的结构定义

    2.2 头插法

    2.3中间位置的插入

    2.4尾插法

    2.5遍历链表

    2.6查询线性表中是否包含指定元素

     2.7返回索引为index的元素值

    2.8修改索引为index位置的元素为新值，返回修改前的元素值

    2.9删除链表中索引为index的元素，返回删除前的元素值

    2.10删除第一个值为val的元素

    2.11在表中删除所有值为val的元素

    三、带头单链表dummyHead

    3.1结构定义

    3.2中间位置的插入

    3.3头插法和尾插法

     3.4遍历带头链表

    3.5 在表中删除所有值为val的元素

     四、用递归写链表的方法

    4.1链表指定位置的插入

    4.2链表的正向输出

    4.3链表的反向输出

    五、双向链表

    5.1结构定义

    5.2头插法和尾插法

    5.3在指定位置插入结点 

     5.4包含、查找指定索引值、修改指定索引值。

     5.5删除操作

    六、ArrayList和LinkedList的区别

    数组这种结构适用于频繁查询低频插入和修改的场景，若频繁插入和删除时，由于需要进行元素的搬移以及扩容等操作，浪费空间，性能开销较大，因此引入了链表。

    链表是逻辑连续的，不是物理连续的。

    物理连续指的是前一个元素一定是位于后一个元素之前，典型的就是数组。

    逻辑连续是指每一个结点之间通过一个“钩子”连接，没有这个钩子，每个节点之间是彼此独立的毫无关系。优点就是可以在任意结点之前或者之后插入新的结点，对其他的节点并不造成影响。不需要考虑空间是否够用以及扩容问题，不会造成空间的浪费。

    由于链表可以根据是否带头结点、是否循环、是否双向，排列组合有8中结构，只需要考虑三种结构：带向不带头的单链表（单向链表），单项带头链表，双向不带头链表。

    一、线性表接口

    定义线性表接口Seqlist。定义接口带来的好处：就是可以以非常低的成本来更换具体的子类。

    1. public interface SeqList {
    2.     void add(int val);
    3.     // 在索引为index的位置插入新元素
    4.     void add(int index,int val);
    5.     // 查询线性表中是否包含指定元素val
    6.     boolean contains(int val);
    7.     // 返回索引为index的元素值
    8.     int get(int index);
    9.     // 修改索引为index位置的元素为新值，返回修改前的元素值
    10.     int set(int index,int newVal);
    11.     // 删除线性表中索引为index的元素，返回删除前的元素值
    12.     int removeByIndex(int index);
    13.     // 删除第一个值为val的元素
    14.     void removeByValueOnce(int val);
    15.     // 在线性表中删除所有值为val的元素
    16.     void removeAllValue(int val);
    17. }

    二、单链表

    有两个特殊的结点：头结点：只有头结点没有前驱。尾结点：只有尾结点没有后继。

    单链表只能从前向后遍历，无论是插入还是删除方法在链表中都要找到操作位置的前驱结点。

    2.1 单链表的结构定义

    val表示该结点中存储的数值，next属性保存下一个结点的地址，若没有下一个结点则为null。

    size表示该链表中保存的有效元素个数，head 保存了第一个结点的地址。

    1. public class MyLinkedList implements SeqList {
    2.     private int size;
    3.     private Node head;
    4.     private  class Node {
    5.         private int val;
    6.         private Node next;
    7.         public Node(int val) {
    8.             this.val = val;
    9.         }
    10.     }
    11. }

    2.2 头插法

    必须先让新结点先挂在原先头结点的前面，然后再让head指向新的结点。

    1.     public void addFirst(int val) {
    2.         Node node = new Node(val);
    3.         node.next = head;
    4.         head = node;
    5.         size ++ ;
    6.     }

    2.3中间位置的插入

    首先要排除不合法的情况，然后根据index的特殊索引选择头插法，然后剩下的情况再继续分析，首先需要遍历该列表停在index位置的前驱节点，然后将该位置的next指向新的node，将node的next修改为原位置的next，最后size++。

    1.     public void add(int index, int val) {
    2.         if (index < 0 || index > size) {
    3.             throw new IllegalArgumentException("add index illegal!");
    4.         }
    5.         if (index == 0) {
    6.             addFirst(val);
    7.             return;
    8.         }
    9.         Node prev = head;
    10.         for (int i = 1; i 
    11.             prev = prev.next;
    12.         }
    13.         Node node = new Node(val);
    14.         node.next = prev.next;
    15.         prev.next = node;
    16.         size++;
    17.     }

    2.4尾插法

    尾插法不必全部写出，在按照索引插入中，index == size时就是尾插， 并且同样是有前驱节点，尾结点本来指向的就是空，所以新的尾结点也应该指向空。所以尾插法中写入 add(size,val)即可。

    1.     public void add(int val) {
    2.         add(size,val);
    3.     }

    2.5遍历链表

    不能直接使用head进行遍历，遍历一次之后，头结点的地址就找不到了。所以创建一个n使他等于head，用n进行遍历。

    1.     public String toString() {
    2.         StringBuilder sb = new StringBuilder();
    3.         for(Node n = head;n!=null;n = n.next){
    4.             sb.append(n.val);
    5.             sb.append("->");
    6.             if(n.next == null){
    7.                 sb.append("NULL");
    8.             }
    9.         }
    10.         return sb.toString();
    11.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.addFirst(1);
    4.         myLinkedList.add(3);
    5.         myLinkedList.add(5);
    6.         myLinkedList.addFirst(7);
    7.         myLinkedList.add(2,10);
    8.         System.out.println();
    9.     }

     调用三种添加方法，尾插3，头插1，尾插5，头插7，在索引为3的位置插入4。最后的结果应为1,3,5,4,7。

    402e48a38a364180836a97bcbd9980d7.png

    2.6查询线性表中是否包含指定元素

    创建一个Node类型的n使他等于head，然后遍历整个链表，当第一次遇见n的val等于指定元素，即返回true。如果遍历到最后还是没有，则返回false。遍历到最后意味着n==null。

    1.     public boolean contains(int val) {
    2.         for(Node n = head;n!= null;n = n.next){
    3.             if(n.val == val){
    4.                 return true;
    5.             }
    6.         }
    7.         return false;
    8.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(3);
    4.         myLinkedList.addFirst(1);
    5.         myLinkedList.add(5);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(3,4);
    8.         System.out.println(myLinkedList.toString());
    9.         System.out.println(myLinkedList.contains(40));
    10.         System.out.println(myLinkedList.contains(4));
    11.     }

    77184a55a1594a11a71e0794ff97b8b0.png

     2.7返回索引为index的元素值

    首先要创建一个rangeCheck来判断index是否合法。然后遍历链表，找到索引为index的结点，返回该结点的值。

    1.     public int get(int index) {
    2.         if(!rangCheck(index)){
    3.             throw new IllegalArgumentException("get index illegal!");
    4.         }
    5.         Node node = head;
    6.         for(int i = 0;i
    7.             node = node.next;
    8.         }
    9.         return node.val;
    10.     }
    11.  
    12.     private boolean rangCheck(int index) {
    13.         return index >= 0 && index < size;
    14.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(3);
    4.         myLinkedList.addFirst(1);
    5.         myLinkedList.add(5);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(3,4);
    8.         System.out.println(myLinkedList.toString());
    9.         System.out.println(myLinkedList.get(2));
    10.     }

    9e365547745a41df85a5e455532baa4f.png

    2.8修改索引为index位置的元素为新值，返回修改前的元素值

    1.     public int set(int index, int newVal) {
    2.         if(!rangCheck(index)){
    3.             throw new IllegalArgumentException("get index illegal!");
    4.         }
    5.         Node node = head;
    6.         for(int i = 0;i
    7.             node = node.next;
    8.         }
    9.         int temp = node.val;
    10.         node.val = newVal;
    11.         return temp;
    12.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(3);
    4.         myLinkedList.addFirst(1);
    5.         myLinkedList.add(5);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(3,4);
    8.         System.out.println(myLinkedList.toString());
    9.         System.out.println(myLinkedList.set(4,9));
    10.         System.out.println(myLinkedList.toString());
    11.         System.out.println(myLinkedList.set(0,10));
    12.         System.out.println(myLinkedList.toString());
    13.         System.out.println(myLinkedList.set(2,20));
    14.         System.out.println(myLinkedList.toString());
    15.     }

    fbe55d969e6840c1b20ec9004e3f1fde.png

    2.9删除链表中索引为index的元素，返回删除前的元素值

    这个方法可以引申出链表的另外两个方法，删除头结点和尾结点。只需要调用该函数并且把index设置为0或者size-1。

    想要删除在索引位置上的元素，就需要找到该位置的前驱结点，使前驱节点的与索引位置的next结点连接，这时候就有一个特殊情况，头结点是没有前驱结点的，所以需要把头结点单独分析。

    排除不合法的情况后，现针对index == 0来分析，直接将head = head.next即可，同时要让长度减一。剩下的情况只需要找到index位置的前驱结点，使它的next = index位置的next。

    1.     public int removeFirst(){
    2.        return removeByIndex(0);
    3.     }
    4.     public int removeLast(){
    5.         return removeByIndex(size-1);
    6.     }
    7.     public int removeByIndex(int index) {
    8.         if(!rangCheck(index)){
    9.             throw new IllegalArgumentException("get index illegal!");
    10.         }
    11.         if(index ==0){
    12.             int tmp = head.val;
    13.             head = head.next;
    14.             size--;
    15.             return tmp;
    16.         }
    17.         Node node = head;
    18.         for(int i = 1;i
    19.             node = node.next;
    20.         }
    21.         int tmp = node.next.val;
    22.         node.next = node.next.next;
    23.         size--;
    24.         return tmp;
    25.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(1);
    4.         myLinkedList.add(3);
    5.         myLinkedList.add(5);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(3,4);
    8.         System.out.println(myLinkedList.toString());
    9.         System.out.println(myLinkedList.removeFirst());
    10.         System.out.println(myLinkedList.removeLast());
    11.         System.out.println(myLinkedList.removeByIndex(1));
    12.         System.out.println(myLinkedList.toString());
    13.     }

     先删除头结点，然后删除尾结点，再删除下标为1的数。

    f3c6b3f98e1d4bb0a2b257c878dd6f87.png

    2.10删除第一个值为val的元素

    想要删除值为的元素，就需要找到它的前驱结点，使前驱节点的与查找元素的后继结点连接，这种时候也需要将头结点单独来看，因为头结点没有前驱结点。

    并且如果链表为null这种情况也要分开处理，因为链表为空代表链表中没有值处理不了。

    逻辑上的终止条件（假设要删除位置的前驱结点为prev）：此处删除的是prev的后继节点，因此保证prev的后继节点必须存在，所以终止条件是prev.next != null。

    1.     public void removeByValueOnce(int val) {
    2.         if(head == null){
    3.             return ;
    4.         }
    5.         if(head.val==val){
    6.             int tmp = head.val;
    7.             head = head.next;
    8.             size--;
    9.             return ;
    10.         }
    11.         for(Node prev = head;prev.next!= null;prev = prev.next){
    12.             if(prev.next.val== val){
    13.                 prev.next = prev.next.next;
    14.                 size--;
    15.                 return;
    16.             }
    17.         }
    18.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(7);
    4.         myLinkedList.add(1);
    5.         myLinkedList.add(3);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(5);
    8.         myLinkedList.add(3,4);
    9.         myLinkedList.add(7);
    10.         System.out.println(myLinkedList.toString());
    11.         myLinkedList.removeByValueOnce(7);
    12.         System.out.println(myLinkedList.toString());
    13.         myLinkedList.removeByValueOnce(7);
    14.         System.out.println(myLinkedList.toString());
    15.         myLinkedList.removeByValueOnce(7);
    16.         System.out.println(myLinkedList.toString());
    17.     }

    5293d15625c244cdb570f7c33bbec098.png

    2.11在表中删除所有值为val的元素

    若链表为空则直接返回，若链表的头结点就是待删除的结点，需要考虑删除后补上的结点的值也是val，所以需要进行while循环，直到head的值不是val，在这种情况中需要让head！=null ，否则无法取得head的val值。

    进行完这一步，head可能为空，也可能head的值不是val。同样创建prev进行遍历使 prev= head。所以需要先保证prev不为空，才能取得prev.next的val值。

    删除一个结点之后不能直接使prev引用向后走，prev引用直到prev.next.val != val时prev才能向后走，否则如果补上的结点值也为val则会被忽略。

    1.     public void removeAllValue(int val) {
    2.         if(head == null){
    3.             return ;
    4.         }
    5.         while (head!=null&&head.val==val){
    6.             int tmp = head.val;
    7.             head = head.next;
    8.             size--;
    9.         }
    10.         if(head == null){
    11.             return ;
    12.         }
    13.         Node prev = head;
    14.         while(prev.next!=null){
    15.             if(prev.next.val== val){
    16.                 prev.next = prev.next.next;
    17.                 size--;
    18.             }else {
    19.                 prev = prev.next;
    20.             }
    21.         }
    22.     }
    1.     public static void main(String[] args) {
    2.         MyLinkedList myLinkedList = new MyLinkedList();
    3.         myLinkedList.add(7);
    4.         myLinkedList.add(7);
    5.         myLinkedList.add(3);
    6.         myLinkedList.add(7);
    7.         myLinkedList.add(7);
    8.         myLinkedList.add(5);
    9.         myLinkedList.add(3,4);
    10.         myLinkedList.add(7);
    11.         System.out.println(myLinkedList.toString());
    12.         myLinkedList.removeAllValue(7);
    13.         System.out.println(myLinkedList.toString());
    14.     }

    67a3bc3b3a354a3388ec5b60864c0a18.png

    三、带头单链表dummyHead

    在单链表的操作过程中，每次插入和删除都需要考虑头结点的情况，因为只有头结点特殊，没有前驱，所以需要想一个办法，让链表中所有的有效结点都一视同仁，就不需要区额外关注头结点的情况。

    因此引入一种新的结构，虚拟头结点dummyHead，不存储具体的元素，只是作为链表的头来使用，所有存储元素的结点都是该头结点的后继结点。

    3.1结构定义

    与单链表不同的地方就是要在构造方法中先定义虚拟头结点。后来每一个结点都在虚拟头结点的后面。

    1. public class LinkedListWithHead {
    2.     private int size;
    3.     private Node dummyHead;
    4.     private static class Node {
    5.         private int val;
    6.         private Node next;
    7.         public Node(int val) {
    8.             this.val = val;
    9.         }
    10.     }
    11.     public LinkedListWithHead(){
    12.         this.dummyHead = new Node(-1);
    13.     }
    14. }

    3.2中间位置的插入

    首先排除不合法情况后不需要将第一个有效结点单独拿出来调用头插法，因为它也有前驱结点，所以可以一视同仁。

    1.     public void add(int index, int val){
    2.         if (index < 0 || index > size) {
    3.             throw new IllegalArgumentException("add index illegal!");
    4.         }
    5.         Node prev = dummyHead;
    6.         for (int i = 0; i < index; i++) {
    7.             prev = prev.next;
    8.         }
    9.         Node node = new Node(val);
    10.         node.next = prev.next;
    11.         prev.next = node;
    12.         size++;
    13.     }

    3.3头插法和尾插法

     与单链表没有什么差别，就是将单链表的头结点换成了带头链表的虚拟头结点的后继节点。

    1.     public void addFirst(int val){
    2.         Node node = new Node(val);
    3.         node.next = dummyHead.next;
    4.         dummyHead.next = node;
    5.         size++;
    6.     }

     但是在带头链表中，第一个有效结点也有前驱节点，所以也可以像尾插法一样运用add方法。

    1.     public void addFirst(int val){
    2.         add(0,val);
    3.     }
    4.     public void addLast(int val) {
    5.         add(size,val);
    6.     }

     3.4遍历带头链表

    经过链表之后，带头链表的遍历就很好写了，摘除头结点之后遍历即可。

    1.     public String toString() {
    2.         StringBuilder sb = new StringBuilder();
    3.         Node cur = dummyHead.next;
    4.         while (cur != null) {
    5.             sb.append(cur.val);
    6.             sb.append("->");
    7.             if (cur.next == null) {
    8.                 sb.append("NULL");
    9.             }
    10.             cur = cur.next;
    11.         }
    12.         return sb.toString();
    13.     }
    1.     public static void main(String[] args) {
    2.         LinkedListWithHead linkedListWithHead = new LinkedListWithHead();
    3.         linkedListWithHead.addLast(3);
    4.         linkedListWithHead.addLast(5);
    5.         linkedListWithHead.addLast(9);
    6.         linkedListWithHead.addFirst(1);
    7.         linkedListWithHead.add(3,7);
    8.         System.out.println(linkedListWithHead.toString());
    9.     }

     先尾插3,5,9。然后头插1，在指定位置3插入7。

    196b99151d3e41bc984633f142997bec.png

    3.5 在表中删除所有值为val的元素

    具体逻辑也是和单链表一样的，只是不需要特别考虑头结点。用cur指向虚拟头结点，来判断cur.next的val是否和需要判断的值相同，如果相同就将cur.next指向 cur.next.next，直到不相同的时候，就让cur向右移。

    1.     public void removeAllValue(int val){
    2.         Node cur = dummyHead;
    3.         while (cur.next!=null){
    4.             Node sec = cur.next.next;
    5.             if(cur.next.val == val){
    6.                 cur.next = sec;
    7.                 size--;
    8.             }else{
    9.                 cur = cur.next;
    10.             }
    11.         }
    12.     }
    1.     public static void main(String[] args) {
    2.         LinkedListWithHead linkedListWithHead = new LinkedListWithHead();
    3.         linkedListWithHead.addLast(1);
    4.         linkedListWithHead.addLast(1);
    5.         linkedListWithHead.addLast(3);
    6.         linkedListWithHead.addLast(1);
    7.         linkedListWithHead.addLast(5);
    8.         linkedListWithHead.addLast(1);
    9.         linkedListWithHead.addFirst(1);
    10.         System.out.println(linkedListWithHead.toString());
    11.         linkedListWithHead.removeAllValue(1);
    12.         System.out.println(linkedListWithHead.toString());
    13.     }

    9a4842d212f84973a58572e2732640aa.png

     四、用递归写链表的方法

    具体构造还是和之前一样。

    1. public class LinkedListR implements SeqList {
    2.     private int size;
    3.     private Node head;
    4.     private  class Node {
    5.         private int val;
    6.         private Node next;
    7.         public Node(int val) {
    8.             this.val = val;
    9.         }
    10.     }
    11. }

    4.1链表指定位置的插入

    首先就是不合法情况的排除，然后先判断如果index==0就是头插法，如果index!=0，那么直接让head.next = add(head.next,index - 1,val)，调用递归一直到找到index位置然后插入即可。

    然后头插和尾插都调用这个方法输入对应的位置即可。

    1.     public void addFirst(int val) {
    2.         add(0,val);
    3.     }
    4.  
    5.     @Override
    6.     public void add(int val) {
    7.         add(size,val);
    8.     }
    9.  
    10.     @Override
    11.     public void add(int index, int val) {
    12.         if (index < 0 || index > size) {
    13.             throw new IllegalArgumentException("add index illegal!");
    14.         }
    15.         head = add(head,index,val);
    16.     }
    17.     private Node add(Node head, int index, int val) {
    18.         if (index == 0) {
    19.             Node node = new Node(val);
    20.             node.next = head;
    21.             head = node;
    22.             size ++;
    23.             return head;
    24.         }
    25.         head.next = add(head.next,index - 1,val);
    26.         return head;
    27.     }

    4.2链表的正向输出

    链表的正向输出用递归写也很简单，首先head==null时，输出NULL然后返回即可，然后先输出当前的值在调用递归，一个接一个输出。

    1.     private void print(Node head) {
    2.         if (head == null) {
    3.             System.out.print("NULL\n");
    4.             return;
    5.         }
    6.         System.out.print(head.val + "->");
    7.         print(head.next);
    8.     }
    9.     public void print() {
    10.         print(head);
    11.     }

    4.3链表的反向输出

    用递归的方法反向输出会更加的容易，能倒叙从尾结点开始输出内容，一直到头结点。

    首先当head==null时，直接返回就好，然后需要把先把子链表全部输出完，站在head位置，只要一直输出就好。但是这个时候最后输出没有办法加上null，正常正向输出最后会有null，所以创建一个变量count计数，在每次调用递归前count++。然后每次调用完递归返回后再count--，当count==0时，已经走到了链表的头结点，在最后要继续输出null。

    1.     public void printReverse() {
    2.         printReverse(head);
    3.     }
    4.     int count = 0;
    5.     private void printReverse(Node head) {
    6.         if (head == null) {
    7.             return;
    8.         }
    9.         count ++;
    10.         printReverse(head.next);
    11.         count --;
    12.         System.out.print(head.val + "->");
    13.         if (count == 0) {
    14.             System.out.print("NULL\n");
    15.         }
    16.     }
    1.     public static void main(String[] args) {
    2.         LinkedListR list = new LinkedListR();
    3.         list.addFirst(1);
    4.         list.addFirst(3);
    5.         list.add(5);
    6.         list.add(7);
    7.         list.add(1,10);
    8.         list.print();
    9.         list.printReverse();
    10.     }

    08bf786edcd8419b816174925f69fc49.png

    五、双向链表

    工程中常用的链表就是双向链表。

    每个节点即保存下一个结点的地址，也保存第一个结点的地址，因此我们在双向链表的任意一个节点，就可以即向后遍历，又可以向前遍历。

    5.1结构定义

    双向链表的Node重要定义三个变量，prev是前驱，next是后继，val是存储的值。

    主要的变量也要定义三个，size长度，head头结点，tail尾结点。

    1. public class DoubleLinkedList implements SeqList {
    2.     private int size;
    3.     private Node head;
    4.     private Node tail;
    5.     private static class Node {
    6.         private Node prev;
    7.         private int val;
    8.         private Node next;
    9.         public Node(int val) {
    10.             this.val = val;
    11.         }
    12.     }
    13. }
    14.

    5.2头插法和尾插法

    双向链表的头插和尾插就很简单，只要排除了链表为空的情况即可，若链表为空那么直接让head = tail = node。有了前驱和后继两个指向，剩下就方便解决了，尾插就直接让原先的尾结点的后继指向node，然后让node的前驱指向tail，再将tail改成node即可，头插同理。

    1.     public void add(int val) {
    2.         Node node = new Node(val);
    3.         size ++;
    4.         if(tail == null){
    5.             head = tail = node;
    6.             return;
    7.         }
    8.         tail.next = node;
    9.         node.prev = tail;
    10.         tail = node;
    11.     }
    12.     public void addFirst(int val){
    13.         Node node = new Node(val);
    14.         size ++;
    15.         if(head == null){
    16.             head = tail = node;
    17.             return;
    18.         }
    19.         head.prev = node;
    20.         node.next = head;
    21.         head = node;
    22.     }

    5.3在指定位置插入结点 

    首先排除不合法情况，然后排除头插和尾插法。

    然后创建一个node方法来找到index位置的前驱结点，为了让node方法进入循环的次数少一些要判断一下index-1和size一半的大小关系，如果小就从头遍历，如果大就从尾部遍历。然后用prev存储前驱结点，用sec存储原链表的index位置的结点，将node插入即可。

    1.     public void add(int index, int val) {
    2.         if (index < 0 || index > size) {
    3.             throw new IllegalArgumentException("add index illegal!");
    4.         }
    5.         if(index == 0){
    6.             addFirst(val);
    7.             return;
    8.         }
    9.         if(index == size){
    10.             add(val);
    11.             return;
    12.         }
    13.         Node prev = node(index - 1);
    14.         Node sec = prev.next;
    15.         Node node = new Node(val);
    16.         size ++;
    17.         prev.next = node;
    18.         node.prev = prev;
    19.         node.next = sec;
    20.         sec.prev = node;
    21.     }
    22.     private Node node(int index){
    23.         Node result = null;
    24.         if(index<(size>>1)){
    25.             result = head;
    26.             for(int i = 0;i
    27.                 result = result.next;
    28.             }
    29.         }else{
    30.             result = tail;
    31.             for(int i = size-1;i > index;i--){
    32.                 result = result.prev;
    33.             }
    34.         }
    35.         return result;
    36.     }
    1.     public static void main(String[] args) {
    2.         DoubleLinkedList list = new DoubleLinkedList();
    3.         list.add(3);
    4.         list.add(7);
    5.         list.add(9);
    6.         list.addFirst(1);
    7.         list.add(2,5);
    8.         System.out.println(list.toString());
    9.     }

     5.4包含、查找指定索引值、修改指定索引值。

    包含就很容易了只要遍历数组查找有没有结点的值和指定值相同。

    get也很简单只要调用node方法，找到index位置的前驱元素，返回index位置的值即可。

    set直接找到index位置的元素，然后将这个位置元素换成新的元素。

    1.     public boolean contains(int val) {
    2.         Node node = head;
    3.         for(int i = 0;i
    4.             if(node.val==val){
    5.                 return true;
    6.             }
    7.             node = node.next;
    8.         }
    9.         return false;
    10.     }
    11.     @Override
    12.     public int get(int index) {
    13.         Node node = node(index-1);
    14.         return node.next.val;
    15.     }
    16.     @Override
    17.     public int set(int index, int newVal) {
    18.         Node node = node(index);
    19.         int x = node.val;
    20.         Node sec = new Node(newVal);
    21.         sec.prev = node.prev;
    22.         sec.next = node.next;
    23.         node.prev.next = sec;
    24.         node.next.prev = sec;
    25.         return x;
    26.     }
    1.     public static void main(String[] args) {
    2.         DoubleLinkedList list = new DoubleLinkedList();
    3.         list.add(3);
    4.         list.add(7);
    5.         list.add(9);
    6.         list.addFirst(1);
    7.         list.add(2,5);
    8.         System.out.println(list.toString());
    9.         System.out.println(list.contains(1));
    10.         System.out.println(list.get(2));
    11.         System.out.println(list.set(3,1));
    12.         System.out.println(list.toString());
    13.     }

     5.5删除操作

    删除指定位置结点有node方法就很好做了，找到该节点然后通过node.next.prev = node.prev; node.prev.next = node.next;删除即可。

    删除第一次出现val值首先要排除头结点和尾结点，先对这两个点进行处理，然后处理中间结点，找到和val值一样的结点的前驱结点，然后进行删除操作。

    删除全部val值也要排除头结点和尾结点，先对这两个点进行处理，并且要使用循环操作，以防补上来的结点也满足条件，然后处理中间结点，找到和val值一样的结点的前驱结点，然后进行删除操作，如果不是就对下一个结点进行操作。

    1.     public int removeByIndex(int index) {
    2.         Node node = node(index);
    3.         int x = node.val;
    4.         node.next.prev = node.prev;
    5.         node.prev.next = node.next;
    6.         size--;
    7.         return x;
    8.     }
    9.     @Override
    10.     public void removeByValueOnce(int val) {
    11.         if(head.val == val){
    12.             head.next.prev = null;
    13.             head = head.next;
    14.             size--;
    15.             return;
    16.         }
    17.         if(tail.val == val){
    18.             tail.prev.next = null;
    19.             tail = tail.prev;
    20.             size--;
    21.             return;
    22.         }
    23.         Node node = head;
    24.         for(int i = 0;i
    25.             if(node.val==val){
    26.                 node.next.prev = node.prev;
    27.                 node.prev.next = node.next;
    28.                 size--;
    29.             }
    30.             node = node.next;
    31.         }
    32.     }
    33.     @Override
    34.     public void removeAllValue(int val) {
    35.         while (head.val == val){
    36.             head.next.prev = null;
    37.             head = head.next;
    38.             size--;
    39.         }
    40.         while (tail.val == val){
    41.             tail.prev.next = null;
    42.             tail = tail.prev;
    43.             size--;
    44.         }
    45.         Node node = head;
    46.         while (node.next!=null){
    47.             if(node.next.val==val){
    48.                 node.next= node.next.next;
    49.                 node.next.prev = node;
    50.                 size--;
    51.             }else {
    52.                 node = node.next;
    53.             }
    54.         }
    55.     }
    1.     public static void main(String[] args) {
    2.         DoubleLinkedList list = new DoubleLinkedList();
    3.         list.add(3);
    4.         list.add(7);
    5.         list.add(9);
    6.         list.add(3);
    7.         list.add(3);
    8.         list.addFirst(1);
    9.         list.addFirst(3);
    10.         list.addFirst(3);
    11.         list.add(2,5);
    12.         list.add(4,3);
    13.         System.out.println(list.toString());
    14.         System.out.println(list.removeByIndex(3));
    15.         System.out.println(list.toString());
    16.         list.removeByValueOnce(3);
    17.         System.out.println(list.toString());
    18.         list.removeAllValue(3);
    19.         System.out.println(list.toString());
    20.     }

    六、ArrayList和LinkedList的区别

    LinkedList还是队列Queue的子类，也是双端队列Deque的子类。

    LinkedList不仅有正向遍历的迭代器，还有一个反向遍历的迭代器，从链表的尾部开始遍历。

    不同点ArrayListLinkedList
    存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
    随机访问支持O（1）

    不支持：O(N)

    头插需要搬移元素，效率低O(N)只需修改引用的指向，O(1)

    插入

    		空间不够时需要扩容没有扩容的概念
    应用场景元素高效存储+频繁访问任意位置插入和删除频繁

  • 相关阅读:
    【类和对象之构造方法】
    Bus 消息总线
    【分布式】: 幂等性和实现方式
    工作记录：vue-grid-layout 修改 margin 导致 item 高度剧烈变化
    Google codelab WebGPU入门教程源码＜3＞ - 绘制网格(源码)
    1.django部署(案例)
    python+Vue在线投稿网站系统pycharm源码
    Stream流中的 max（）和 sorted（）方法
    猿创征文｜设计模式之享元模式的理解
    个人项目中使用Flume的拦截器以及ChannelSelector和SinkProcessor的介绍
  • 原文地址：https://blog.csdn.net/m0_50987960/article/details/127867041