文章目錄
-
- 一、底層數據結構與特性
-
- 1. 核心數據結構
- 2. 關鍵特性
- 二、核心操作機制解析
-
- 1. 添加元素機制
- 2. 刪除元素機制
- 三、性能關鍵點分析
-
- 1. 時間復雜度對比
- 2. 空間開銷
- 四、線程安全解決方案
-
- 1. 同步包裝器
- 2. 使用并發集合
- 五、經典面試題解析
-
- 1. ArrayList 和 LinkedList 的區別？
- 2. 如何實現 LRU 緩存？
- 3. LinkedList 為什么不能實現 RandomAccess 接口？
- 六、高級應用場景
-
- 1. 實現阻塞隊列
- 2. 實現圖結構
- 七、常見陷阱與解決方案
-
- 1. 迭代過程中修改列表
- 2. 頻繁中間插入性能陷阱
- 3. 內存泄漏問題
- 八、性能優化實踐
-
- 1. 批量操作優化
- 2. 使用 ListIterator 優化順序訪問
- 3. 避免不必要的裝箱
一、底層數據結構與特性
1. 核心數據結構
// JDK 17 源碼片段
private static class Node<E> {E item; // 存儲的數據元素Node<E> next; // 指向下一個節點Node<E> prev; // 指向前一個節點
}transient Node<E> first; // 鏈表頭節點
transient Node<E> last; // 鏈表尾節點
transient int size = 0; // 元素數量
2. 關鍵特性
| 特性 | 說明 |
|---|---|
| 雙向鏈表結構 | 每個節點包含前后指針，支持雙向遍歷 |
| 非連續內存存儲 | 元素存儲在離散的節點中，不需要擴容 |
| 非線程安全 | 多線程環境下需要外部同步 |
| 允許 null 值 | 可以存儲任意數量的 null |
| 實現多個接口 | 實現了 List、Deque 接口，可作列表、雙端隊列、棧使用 |
| Fail-Fast 迭代器 | 迭代過程中檢測到結構性修改會拋出 ConcurrentModificationException |
二、核心操作機制解析
1. 添加元素機制
頭部添加：
public void addFirst(E e) {linkFirst(e);
}// 將元素e作為新的頭節點插入到鏈表的最前面
private void linkFirst(E e) {// 保存當前第一個節點的引用ffinal Node<E> f = first;// 創建新節點newNode，其前驅為null，后繼指向原第一個節點ffinal Node<E> newNode = new Node<>(null, e, f);// 將first指針指向新節點first = newNode;if (f == null)// last也指向新節點last = newNode;else// 否則將原第一個節點的prev指向新節點f.prev = newNode;// 鏈表大小加1，修改計數器加1size++;modCount++;
}
尾部添加：
public boolean add(E e) {linkLast(e);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;elsel.next = newNode;size++;modCount++;
}
2. 刪除元素機制
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 
