【Java---數據結構】鏈表 LinkedList

1. 鏈表的概念

鏈表用于存儲一系列元素，由一系列節點組成，每個節點包含兩部分：數據域和指針域。

數據域：用于存儲數據元素

指針域：用于指向下一個節點的地址，通過指針將各個節點連接在一起，形成一個鏈式結構。

注意：

鏈表在邏輯上是連續的，空間上并不是連續的

根據指針的連接方式，鏈表可以分為單向鏈表和雙向鏈表

注意：

單向鏈表和雙向鏈表的結點存在差異

2. 單向鏈表

單向鏈表是鏈表的一種，它的每個節點除了存儲數據外，還包含一個指針指向下一個節點地址

2.1 單向列表的節點

每個節點只有一個指針，指向下一個節點。

最后一個節點的指針指向null，表示鏈表結束。

代碼實現：

class ListNode{int val;ListNode next;//next指向新的節點public ListNode(int val) {this.val = val;}}

注意：?

結點一般都是從堆上申請出來，每次在堆上申請的空間，按照一種策略來進行分配，多次申請出來的空間，可能連續，也可能不連續

2.2 鏈表的創建

1. 創建一個節點

2.創建第二個節點，讓第一個節點的指針域存放第一個節點的地址，以此類推，可以創建出鏈表

代碼實現：

 public void createList(){//創建節點ListNode listNode = new ListNode(15);ListNode listNode1 = new ListNode(56);ListNode listNode2 = new ListNode(45);ListNode listNode3 = new ListNode(88);//節點連接listNode.next = listNode1;listNode1.next = listNode2;listNode2.next = listNode3;this.head = listNode;}

注意：

不要忘記標注鏈表的頭節點，當輸出頭節點時，會輸出整個鏈表的數據

2.3?鏈表的種類

2.4?鏈表的基本操作

2.4.1 增加

（1）頭插法

主要操作：

將新創建的節點的指針域更改為頭節點的地址?
將頭節點的位置進行改變

public void addFirst(int data){//代碼不能交換//必須先綁定信息ListNode listNode = new ListNode(data);listNode.next = head;head = listNode;}

?注意：代碼的先后順序不能顛倒，否則獲取不到listNode.next的位置?

（2）尾插法

主要操作：

將最后一個節點的指針域指向新節點的地址?

特殊情況：

鏈表內沒有一個節點，那么讓新節點成為頭節點

代碼實現：

    public void addLast(int data){ListNode listNode  = new ListNode(data);ListNode cur = head;if(cur==null){head = listNode;return ;}while(cur.next!=null){//關注next的指向,找到最后一個節點cur = cur.next;}cur.next = listNode;}

（3）固定位置插入

主要操作：

找到要插入位置的前一個位置（cur）
讓新節點的指針域指向要插入位置的舊節點
讓cur指針域指向新節點的地址

注意：第二步和第三步不能交換位置，如果交換，會導致cur的位置發生改變，導致無法找到要插入位置的地址

代碼實現：

public void addIndex(int index,int data){if(index<0||index>size()){System.out.println("位置有問題");return;}if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return ;}ListNode cur = head;int count = 0;ListNode listNode = new ListNode(data);while(count<index-1){cur =cur.next;count++;}//不能互換位置listNode.next = cur.next;cur.next = listNode;}

注意：

不要忘記檢查，插入的位置是否合法

?如果插入的位置為0；那么意味著頭插法，位置為元素的長度，那么就是尾插法

2.4.2 刪除

（1）刪除第一個出現的元素

主要步驟：

找到你要刪除元素的前一個節點
找到你要刪除的節點
進行刪除操作

代碼實現：

    public void remove(int data){if(head ==null){return;}if(head.val ==data){head = head.next;return;}//1.找到你要刪除的前一個節點ListNode cur = head;int count = 0;while(cur.next!=null){if(cur.next.val == data){break;}count++;cur= cur.next;}//找到要刪除的節點ListNode del = head;int delindex = 0;while (del!=null){if(del.val ==data){break;}delindex++;del = del.next;}//刪除操作cur.next = del.next;}

?注意：刪除的具體操作就是：刪除節點的前一個節點的指向發生改變，指向刪除元素的指向

（2）刪除出現的所有元素

主要步驟：

初始化兩個節點，cur節點進行判斷值是否相同，previous是cur節點的前一個結點，方便進行刪除操作
進行遍歷鏈表，找到相同的值，則進行刪除操作，反之將兩個節點都向后移動一位

代碼實現：

        if(head ==null){return;}ListNode cur = head.next;ListNode previous = head;while(cur!=null){if(cur.val==data){previous.next = cur.next;cur = cur.next;}else{previous = cur;//注意，小心寫成 previous.next = cur;//錯誤cur = cur.next;}}if(head.val ==data){head = head.next;}}

注意：不要忘記對頭節點進行判斷

2.4.3 查看

（1）查看鏈表是否存在元素

    public boolean contains(int value){ListNode cur = head;while(cur!=null){if(cur.val==value){return true;}cur = cur.next;}return false;}

?主要步驟：

采用遍歷的形式，如果找到元素，則返回true，反之，返回false

2.4.4?獲取鏈表長度

    int  size(){int count = 0;ListNode cur = head;while (cur!=null){cur = cur.next;count++;}return count;}

?2.4.5 清空鏈表

void clear(){ListNode cur  = head;ListNode curNext ;while(cur!=null){curNext = cur.next;cur.next = null;cur = curNext;}head = null;}
}

注意：?遍歷鏈表逐個釋放節點的引用，讓每個節點不再被引用

3. 快慢指針

思想：通過使用兩個速度不同的指針（快指針和慢指針）來遍歷數據結構，從而實現特定的功能

注意：本質就是利用指針的移動速度差異來解決問題

常見的解決情況：

（1）找出中間的節點

    ListNode findListNode(Text_2 list){ListNode mid = head;if(head == null){return null;}if(head.next ==null){return head;}int count = size(list);int midCount = count/2;while (midCount>0){mid = mid.next;midCount--;}return mid;}

這是解決這種問題，我們第一個想到的方法，需要遍歷兩次鏈表，獲取長度和中間節點?，復雜度高，下面是我們引用了快慢指針：

    ListNode findListNode1(){ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null){//不能交換fast = fast.next.next;slow = slow.next;}return slow;}

核心思想：使用快慢雙指針，快的是慢的二倍；那么快的到了，慢的一定就在中間

（2）找出倒數第k個節點

    ListNode findListNode(int k){if(head ==null){return null;}if(k<=0||k>size()){System.out.println("k取值不對");return null;}ListNode slow = head;ListNode fast = head;int count = k-1;while (count>0){fast = fast.next;count--;}while(fast!=null&&fast.next!=null){fast =fast.next;slow =slow.next;}return slow;}

核心思想：快的比慢的先走了k-1個，然后每次都移動一個，那么快的到了，滿的就是倒數第k個.

先走k-1個，因為下標從0開始

4. 雙向鏈表

雙向鏈表是鏈表的一種，它的每個節點除了存儲數據外，還包含兩個指針：一個指向前一個節點，另一個指向下一個節點

4.1 雙向列表的節點

注意：

由于有前驅指針，刪除和插入操作更高效。

每個節點需要額外存儲一個指針，因此比單向鏈表占用更多內存。

可以從頭節點向后遍歷，也可以從尾節點向前遍歷。

代碼實現：

class ListNode{int val;ListNode prev;ListNode next;public ListNode(int val) {this.val = val;}
}

4.2 LinkedList

在 Java 中，LinkedList是java.util 包中的一個類，LinkedList的底層使用了雙向鏈表

4.3?LinkedList的使用

4.3.1 LinkedList的構造

（1）無參構造

        //調用無參構造List<Integer> list =new LinkedList<>();

（2）利用Collection構建

        List<Integer> list1 =new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);System.out.println(list1);List<Integer> list2 = new LinkedList<>(list1);list2.add(2);System.out.println(list2);

?注意：會繼承傳入實例對象的所有元素，并且元素的順序也會保持一致

4.3.2? LinkedList的常用API

boolean add(E e)	尾插
void add(int index, E element)	在index位置添加元素
boolean addAll(Collection<? extends E> c)	將c中的所有元素插入進來
E remove(int index)	刪除index下標的元素
boolean remove(Object o)	刪除一個o元素
E get(int index)	獲得index下標的元素
E set(int index, E element)	將index下標的元素更改為element
void clear()	清空順序表
boolean contains(Object o)	查看是否有元素o
int indexOf(Object o)	獲取第一個元素o的下標
int lastIndexOf(Object o)	獲取最后一個元素o的下標
List<E> subList(int fromIndex, int toIndex)	截取順序表的一部分

（1）增加

public class Add {public static void main(String[] args) {//尾插法LinkedList<Integer> list =new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);//插入固定位置LinkedList<Integer> list1 = new LinkedList<>();list1.add(0,1);list1.add(0,6);list1.add(1,9);System.out.println(list1);//尾插所有元素Integer[] array = {9,99,999};list.addAll(Arrays.asList(array));System.out.println(list);}
}

（2）刪除

public class Remove {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);//刪除下標的數list.remove(2);System.out.println(list);//刪除第一個出現的數list.remove(new Integer(2));System.out.println(list);}
}

（3）修改

public class Set {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.set(1,999);System.out.println(list);}
}

（4）獲取

public class Get {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);int x = list.get(2);System.out.println(x);}
}

（5）清空

public class Clear {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.clear();System.out.println(list);}
}

（6）查找

public class Contains {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);
//        判斷元素是否在表中Boolean x = list.contains(2);System.out.println(x);
//      返回第一個元素所在的下標int a = list.indexOf(2);System.out.println(a);
//      返回最后一個元素所在的下標int b = list.lastIndexOf(2);System.out.println(b);}
}

（7）截取

public class Sublist {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(6);list.add(9);//        LinkedList<Integer> list1 = new LinkedList<>(list.subList(1,4));//創建新的對象，進行操作，不會影響原來列表的數據//subList返回值是List類型List<Integer> list1 = list.subList(1,4);list1.add(999);list1.add(888);list1.set(0,111);System.out.println(list1);System.out.println(list);}
}

?4.3.3 LinkedList的遍歷

（1）for循環遍歷

        //1.for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();

（2）for-each遍歷

        //2for (int x : list){System.out.print(x+" ");}

（3）使用迭代器

正向遍歷

        //3Iterator<Integer> iterator = list.listIterator();//傳數據while (iterator.hasNext()){System.out.print(iterator.next()+" ");}System.out.println();

反向遍歷

        //4ListIterator<Integer> listIterator = list.listIterator(list.size());while (listIterator.hasPrevious()){System.out.print(listIterator.previous()+" ");}System.out.println();

注意：

（從前往后）while循環中的判斷條件表示：是否存在下一個元素，如果存在，則獲取迭代器的下一個元素并輸出，因為 next 方法，所以在每次調用后進行移動1位

5. ArrayList和LinkedList的區別

差別	ArrayList	LinkedList
底層實現	基于動態數組實現	基于雙向鏈表實現
訪問效率	隨機訪問效率高	隨機訪問效率低
插入和刪除效率	尾部插入和刪除效率高中間或頭部插入和刪除效率低	任意位置插入和刪除效率高
內存占用	內存占用較少，因為只需要存儲數據和數組容量。可能存在內存浪費，因為數組會預留一定的容量	內存占用較多，因為每個節點需要存儲數據以及前后指針。