1. 數據結構設計

(1) 節點結構

LinkedList 的核心是雙向鏈表節點 Node：

private static class Node<E> {E item;         // 存儲的元素Node<E> next;   // 后繼節點Node<E> prev;   // 前驅節點Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}

• 雙向鏈接：每個節點同時記錄前驅和后繼，支持雙向遍歷。
• 首尾指針：通過 first 和 last 字段快速訪問鏈表兩端。

(2) 與 ArrayList 的存儲對比

特性	LinkedList	ArrayList
底層結構	雙向鏈表	動態數組
內存占用	更高（每個元素額外存儲指針）	更低（連續內存）
CPU緩存友好性	差（節點分散）	好（局部性原理）

---

2. 核心操作實現

(1) 添加元素

尾部插入（add(E e)）

public boolean add(E e) {linkLast(e); // 時間復雜度 O(1)return true;
}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null) {first = newNode; // 空鏈表初始化} else {l.next = newNode; // 鏈接原尾節點}size++;
}

• 優勢：無需擴容，直接修改指針。

指定位置插入（add(int index, E element)）

public void add(int index, E element) {checkPositionIndex(index);if (index == size) {linkLast(element); // 尾部插入優化} else {linkBefore(element, node(index)); // 需要遍歷找到目標節點}
}Node<E> node(int index) {// 二分遍歷：根據索引位置選擇從頭或從尾開始查找if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++) x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--) x = x.prev;return x;}
}

• 時間復雜度：
  • 頭尾操作：O(1)
  • 中間操作：O(n)（需遍歷）

(2) 刪除元素

remove(int index)

public E remove(int index) {checkElementIndex(index);return unlink(node(index)); // 先找到節點，再解除鏈接
}E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next; // 刪除的是頭節點} else {prev.next = next;x.prev = null; // 清除引用}if (next == null) {last = prev; // 刪除的是尾節點} else {next.prev = prev;x.next = null;}x.item = null; // 幫助GCsize--;return element;
}

• 關鍵點：正確處理頭尾節點的邊界條件。

(3) 訪問元素

get(int index)

public E get(int index) {checkElementIndex(index);return node(index).item; // 需遍歷鏈表
}

• 性能缺陷：隨機訪問效率遠低于 ArrayList（O(n) vs O(1)）。

---

3. 迭代器實現

(1) 普通迭代器 (Iterator)

private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;public boolean hasNext() { return nextIndex < size; }public E next() {checkForComodification();if (!hasNext()) throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}
}

• 快速失敗機制：通過 modCount 檢測并發修改。

(2) 雙向迭代器 (ListIterator)

支持向前遍歷：

public E previous() {checkForComodification();if (!hasPrevious()) throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item;
}

---

4. 線程安全與性能優化

(1) 線程安全問題

• 非線程安全：并發修改會導致數據不一致或迭代器失效。
• 解決方案：

  List<String> syncList = Collections.synchronizedList(new LinkedList<>());
  

  或使用并發容器 ConcurrentLinkedDeque。

(2) 設計取舍

操作	LinkedList	ArrayList
頭部插入	O(1)	O(n)（需移動元素）
中間插入	O(n)（查找）+ O(1)	O(n)（移動元素）
隨機訪問	O(n)	O(1)
內存占用	高	低

---

5. 應用場景建議

• 使用 LinkedList 的場景：
  • 頻繁在 頭部/中部 插入刪除（如實現隊列/棧）。
  • 不需要頻繁隨機訪問。
• 使用 ArrayList 的場景：
  • 需要快速隨機訪問。
  • 內存敏感型應用。