🚀歡迎互三👉： 2的n次方_💎💎
🚀所屬專欄：數據結構與算法學習💎💎

🍁1. 鏈表的介紹

鏈表是數據結構中一種非常重要的基礎結構，它不同于數組，鏈表中的元素在物理存儲上并不連續，而是通過指針（或引用）連接在一起。在Java中，鏈表的應用非常廣泛，尤其是在需要動態添加或刪除元素的場景中。

🍁2. 鏈表的實現

🍁2.1 單向鏈表

單鏈表中的每個元素都稱為節點（Node），每個節點包含兩個部分：一部分存儲數據（value），另一部分存儲指向列表中下一個節點的引用（next）。最后一個節點的next引用為null，表示鏈表的結束。

所以采用內部類的形式進行創建：

public class MySingleList {static class ListNode {public int value;public ListNode next;public ListNode(int value) {this.value = value;}}public ListNode head;
}

還可以創建一個IList接口，對其中的增刪查改等方法進行規范，之后MySingleList對接口進行實現

public interface IList {void display();int size();boolean contains(int key);void addFirst(int key);void addLast(int key);void addIndex(int key,int index);void remove(int key);void removeAllKey(int key);void clear();
}

接下來就是方法的實現

🍁2.1.1 size()

返回長度:

只需要將head依次往末尾移動，并記錄移動次數進行返回就可以了，當head為null時就表示已經遍歷完成

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

🍁2.1.2 display()

遍歷打印:

遍歷的話需要找到頭節點，接著依次往后移動，為了不該變頭節點的指向，創建一個cur節點輔助遍歷，同樣的，結束的標志也是最后的指向不為空

public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}

🍁2.1.3 contains(int key)

判斷值是否存在鏈表中，這里同樣需要依次遍歷，然后比較value的值

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

🍁2.1.4 addFirst(int key)，addLast(int key)，addIndex(int key, int index)

頭插：

頭插比較簡單，直接創建一個節點，并初始化值，指向原來的head節點，接著改為新的head節點

public void addFirst(int key) {ListNode node = new ListNode(key);node.next = head;head = node;}

尾插：

尾插就需要判斷head節點是否為null，接著找到尾節點進行插入

public void addLast(int key) {ListNode node = new ListNode(key);//頭結點為null，直接插入if (head == null) {head = node;return;}//找到尾節點進行插入ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}

在指定索引插入：

在指定索引插入就更加麻煩一些，需要對傳入的索引進行判斷，如果是0.就調用頭插的方法，如果等于鏈表的長度，就調用尾插的方法，如果是中間的索引，就遍歷鏈表，找到該索引進行插入

public void addIndex(int key, int index) {ListNode node = new ListNode(key);//調用頭插if (index == 0) {addFirst(key);return;}//調用尾插if (index == this.size()) {addLast(key);return;}//傳入索引不合法的情況if (index < 0 || index > this.size()) {throw new IndexOutOfBoundsException();}//找到目標索引進行插入ListNode cur = head;while (index - 1 != 0) {cur = cur.next;index--;}node.next = cur.next;cur.next = node;}

🍁2.1.5 remove(int key)，removeAllKey(int key)

刪除指定元素：

如果head為空，直接返回，如果head的value就是目標元素，就把head的下一個節點作為頭結點，其他情況就根據value的值尋找目標索引，如果沒找到就返回，也就是cur節點為null，找到的話把cur的引用指向cur的之后第二個節點

//根據元素找到目標索引
private ListNode findIndexofKet(int key) {ListNode cur = head;while (cur.next != null) {if (cur.next.value == key) {return cur;}cur = cur.next;}return null;}public void remove(int key) {//頭結點為空if (head == null) {return;}//頭結點為目標元素if (head.value == key) {head = head.next;}//其他節點為目標元素ListNode cur = findIndexofKet(key);if (cur == null) {return;}cur.next = cur.next.next;}

刪除所有指定元素：

需要有兩個指針，同時往后遍歷，刪除cur節點所指元素需要將pre節點的next指向cur的next，循環判斷，最后還要判斷head節點是否為指定元素

public void removeAllKey(int key) {//頭結點為null，直接返回if (this.head == null) {return;}ListNode pre = head;ListNode cur = head.next;//循環刪除while (cur != null) {if (cur.value == key) {pre.next = cur.next;cur = cur.next;} else {pre = cur;cur = cur.next;}}//判斷頭結點if (head.value == key) {head = head.next;}}

🍁2.1.6 clear()

清空鏈表：

清空鏈表只需要遍歷鏈表所有節點，將每一個節點置為null即可，因為是從頭結點開始，如果直接將head置為null，后續再找head.next就會報錯，所以還需要用一個中間變量cur輔助遍歷

public void clear() {ListNode cur = head;while (cur != null) {//創建變量，解決空指針異常ListNode curn = cur.next;cur = null;cur = curn.next;}head = null;}

🍁2.2 雙向鏈表

雙向鏈表有兩個指針域，一個指向前一個節點，一個指向后一個節點

public class MyLinkedList implements IList {static class TListNode {public int value;TListNode pre;TListNode next;public TListNode(int value) {this.value = value;}}public TListNode head;public TListNode last;
}

雙向鏈表的size() ，display()，contains(int key)和單向鏈表是一樣的，下面來實現其他的方法

🍁2.2.1 addFirst(int key)

頭插：

public void addFirst(int key) {TListNode node = new TListNode(key);if (head == null) {head = last = node;} else {node.next = head;head.pre = node;head = node;}}

🍁2.2.2 addLast(int key)

尾插：

public void addLast(int key) {TListNode node = new TListNode(key);if (head == null) {head = last = node;} else {last.next = node;node.pre = last;last = last.next;}}

🍁2.2.3 addIndex(int key, int index)

指定位置插入：

public void addIndex(int key, int index) {TListNode node = new TListNode(key);if(index < 0 || index > size()) return;if (index == 0) {addFirst(key);return;}if (index == size()) {addLast(key);}if (index > 0 && index < size()) {TListNode cur = head;//可以直接到indext的位置，因為雙向鏈表可以找到前一個節點while (index-- != 0) {cur = cur.next;}node.next = cur;cur.pre.next = node;node.pre = cur.pre;cur.pre = node;}}

需要修改四個位置，把要插入的節點node的next 指向cur，再把cur.pre的next指向node，此時節點的next都有了指向，接著node的pre指向cur.pre節點，cur的pre再指向node，此時就完成了插入

🍁2.2.4 remove(int key)和removeAllKey(int key)

首先找到要刪除的值的索引

private TListNode findIndexofKet(int key) {TListNode cur = head;while (cur != null) {if (cur.value == key) {return cur;}cur = cur.next;}return null;}

刪除的時候還要考慮是否為頭結點和尾節點

public void remove(int key) {TListNode cur = findIndexofKet(key);if(cur == null){return;}//頭節點的情況if(cur == head){head = cur.next;//只有一個節點時，指向next后head為null所以當head！=空時才能把pre置為nullif (head != null) {head.pre = null;}}else{cur.pre.next = cur.next;//尾節點的情況if(cur.next == null){last = last.pre;}else{cur.next.pre = cur.pre;}}}

相比于單向鏈表，雙向鏈表的刪除所有指定元素就非常簡單了，只需要在原來刪除一個的基礎上稍加修改就可以了

public void removeAllKey(int key) {TListNode cur = head;while (cur != null) {if (cur.value == key) {if (cur == head) {head = cur.next;if (head != null) {head.pre = null;}} else {cur.pre.next = cur.next;if (cur.next == null) {last = last.pre;} else {cur.next.pre = cur.pre;}}}cur = cur.next;}}

🍁2.2.5 clear()

清空鏈表還是依次遍歷每一個節點，把每一個節點都置為null，最后把head和last也置為null

public void clear() {TListNode cur = head;while(cur.next!=null){TListNode curn = cur;curn.pre = null;curn.next = null;cur = curn;}head = last = null;}

🍁3. Java中LinkedList的使用

🍁3.1 LinkedList的創建和使用

在上一篇數據結構ArrayList的講解中已經簡單提到過👉點我看回顧，集合的一些基本框架，LinkedList也實現了List接口，所以也可以通過接口創建對象，也可以使用List接口中的方法

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

可以直接對LinkedList的對象進行打印，也就是說LinkedList重寫了toSting方法

這些都是LinkedList中獨有的方法，這里就不列舉使用了，

🍁3.2 LinkedList的遍歷

LinkedList的遍歷和ArrayList的遍歷方式一樣，在上一篇介紹了五種遍歷方式，這次再簡單回顧一下

public class Demo {public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);//迭代器 ListIteratorListIterator<Integer> lit = list1.listIterator();while(lit.hasNext()){System.out.print(lit.next() + " ");}System.out.println();//IteratorIterator<Integer> it = list1.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();//增強forfor(Integer l : list1){System.out.print(l + " ");}System.out.println();//普通forfor(int i = 0;i < list1.size();i++){System.out.print(list1.get(i) + " ");}System.out.println();//lambda表達式list1.forEach(e -> {System.out.print(e + " ");});System.out.println();}
}

🍁4. ArrayList和LinkedList的區別

ArrayList底層是一個動態數組
LinkedList底層是雙向鏈表
ArrayList:訪問元素的時間復雜度為 O(1)（直接通過索引）。
LinkedList:訪問元素的時間復雜度為 O(n)（需要從頭或尾開始遍歷到目標位置）。
ArrayList:
在末尾添加元素的時間復雜度為 O(1)。
在中間插入或刪除元素時，時間復雜度為 O(n)，因為需要移動其他元素以保持連續的內存塊。
LinkedList:
在任意位置添加或刪除元素的時間復雜度為 O(1)，只需改變前后節點的指針（需要先找到目標位置，時間復雜度為 O(n)）。

使用場景：
ArrayList:
適合頻繁讀取、隨機訪問元素的場景。
如需要大量順序讀寫、索引訪問操作。
LinkedList:
適合頻繁插入、刪除元素的場景，尤其是在列表中間進行操作。
如需要頻繁的增刪操作，但不常用到隨機訪問。