目錄

1. LinkedList的模擬實現

1.1?雙向鏈表結構圖?編輯

1.2?三個簡單方法的實現

1.3?頭插法

1.4 尾插法

1.5 中間插入

1.6?刪除 key

1.7?刪除所有key

1.8?clear

2.LinkedList的使用

2.1 什么是LinkedList

5.2 LinkedList的使用

?1.LinkedList的構造

2. LinkedList的其他常用方法介紹

3.LinkedList的遍歷33.

5.3 ArrayList 和 LinkedList的區別

---

1. LinkedList的模擬實現

1.1?雙向鏈表結構圖

1.2?三個簡單方法的實現

@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}@Overridepublic int size() {int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}return len;}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}

此處和單鏈表一樣，不在贅述。

1.3?頭插法

    @Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if (head == null) {head = last = node;}else {node.next = head;head.prev = node;head = node;}}

1.4 尾插法

    @Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {last = head = node;}else {last.next = node;node.prev = last;last = last.next;}}

1.5 中間插入

@Override
public void addIndex(int index, int data) {int len = size();if (index < 0 || index > len) {return;}if (index == 0) {addFirst(data);return;}if (index == len) {addLast(data);return;}// 中間插入ListNode node = new ListNode(data);ListNode cur = findIndex(index);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;
}
private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;
}

此處直接找到 index 位置即可，不需要找 index - 1，因為有 prev

1.6?刪除 key

@Overridepublic void remove(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {// 開始刪除if (cur == head) {head = head.next;if (head != null) {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;}else {cur.next.prev = cur.prev;}}return;}cur = cur.next;}}

注意：

1.此處最關鍵的代碼：

????????cur.prev.next = cur.next;

????????cur.next.prev = cur.prev;

2.但是很顯然解決不了頭節點和尾節點，需要條件語句單獨處理

3.特殊情況：

????????只有一個節點的鏈表，且為key值

? ? ? ? 需要加上判斷邏輯：

????????????????????if (head != null) {
? ? ? ? ? ? ? ? ? ? ? ? head.prev = null;
? ? ? ? ? ? ? ? ? ? }

1.7?刪除所有key

@Overridepublic void removeAllKey(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {// 開始刪除if (cur == head) {head = head.next;if (head != null) {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}}

注意：

????????很顯然將 刪除key代碼中的 return；刪除即可

1.8?clear

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

2.LinkedList的使用

2.1 什么是LinkedList

LinkedList 的官方文檔

????????LinkedList的底層是雙向鏈表結構，由于鏈表沒有將元素存儲在連續的空間中，元素存儲在單獨的節點中，然后通過引用將節點連接起來了，因此在在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。

在集合框架中，LinkedList也實現了List接口，具體如下：

【說明】

1. LinkedList實現了List接口

2. LinkedList的底層使用了雙向鏈表

3. LinkedList沒有實現RandomAccess接口，因此LinkedList不支持隨機訪問

4. LinkedList的任意位置插入和刪除元素時效率比較高，時間復雜度為O(1)

5. LinkedList比較適合任意位置插入的場景

5.2 LinkedList的使用

?1.LinkedList的構造

2. LinkedList的其他常用方法介紹

3.LinkedList的遍歷33.

 public static void main(String[] args) {LinkedList<Integer> linkedList2 = new LinkedList<>();linkedList2.add(1);linkedList2.addLast(3);linkedList2.addLast(4);linkedList2.addLast(5);System.out.println(linkedList2);System.out.println("=========ListIterator=========");ListIterator<Integer> listIterator = linkedList2.listIterator(linkedList2.size());while (listIterator.hasPrevious()) {System.out.print(listIterator.previous() + " ");}System.out.println();System.out.println("=========ListIterator=========");ListIterator<Integer> listIterator1 = linkedList2.listIterator();while (listIterator1.hasNext()) {System.out.print(listIterator1.next() + " ");}System.out.println();System.out.println("=========Iterator=========");Iterator<Integer> iterator = linkedList2.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + " ");}System.out.println();System.out.println("=========for each=========");for (Integer x : linkedList2) {System.out.print(x + " ");}System.out.println();System.out.println("=========for=========");for (int i = 0; i < linkedList2.size(); i++) {System.out.print(linkedList2.get(i) + " ");}System.out.println();}

5.3 ArrayList 和 LinkedList的區別