第八期：LinkedList与链表(三))
数据结构第八期：LinkedList 与链表（Java 版）
这是 Java 中最常被问到的数据结构之一，也是面试、笔试、日常开发中最容易踩坑的地方。
下面从原理 → 源码 → 常见操作 → 面试高频题 → 实际使用建议完整梳理一遍。
1. LinkedList 在 Java 中的真实身份
publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>,Deque<E>,Cloneable,java.io.Serializable一句话总结：
LinkedList 同时实现了 List 和 Deque 接口，所以它既是“双向链表”，也是“双端队列”。
最关键的两点：
- 底层是双向链表（doubly-linked list）
- 没有像 ArrayList 那样的连续数组存储
2. 核心内部结构（JDK 8/11/17/21 一致）
privatestaticclassNode<E>{Eitem;// 元素本身Node<E>next;// 后继指针Node<E>prev;// 前驱指针}三个重要成员变量：
transientintsize=0;// 元素个数transientNode<E>first;// 头节点（first）transientNode<E>last;// 尾节点（last）最经典的图示（双向链表）：
null ← prev [prev | item | next] ↔ [prev | item | next] ↔ [prev | item | next] next → null ↑ first ↑ last3. 常用操作的时间复杂度（面试必背）
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| get(index) | O(n) | 从头/尾选近的一端开始遍历 |
| set(index, element) | O(n) | 同上，需要找到第 index 个节点 |
| addFirst / addLast | O(1) | 直接操作 first/last 指针 |
| add(index, element) | O(n) | 找到位置 + 修改指针（最坏 O(n)） |
| removeFirst / removeLast | O(1) | 直接操作 first/last |
| remove(Object o) | O(n) | 需要线性查找 + 修改指针 |
| remove(index) | O(n) | 找到节点 + 修改前后指针 |
| contains(Object o) | O(n) | 线性查找 |
| size() / isEmpty() | O(1) | 直接返回 size 字段 |
| iterator() / listIterator() | O(1) | 返回链表迭代器（支持双向遍历） |
一句话总结：
凡是涉及“按索引操作”的几乎都是 O(n)，凡是“头尾操作”的都是 O(1)。
4.LinkedList 作为 Deque（双端队列）的常用方法
LinkedList 实现了 Deque 接口，所以可以用它当栈、队列、双端队列用。
| 场景 | 首选方法（推荐） | 等价方法（不推荐抛异常版） | 说明 |
|---|---|---|---|
| 入队（尾） | offerLast(e) / addLast(e) | add(e) | 尾插 |
| 出队（头） | pollFirst() | removeFirst() | 头出，空返回 null |
| 入栈（头） | push(e) | addFirst(e) | 头插（栈顶） |
| 出栈（头） | pop() | removeFirst() | 头出（栈顶） |
| 取头 | peekFirst() | getFirst() | 看头元素，不删除 |
| 取尾 | peekLast() | getLast() | 看尾元素，不删除 |
面试最爱问的写法对比：
// 当栈用（LIFO）LinkedList<Integer>stack=newLinkedList<>();stack.push(1);// 入栈stack.push(2);stack.pop();// 出栈 → 2// 当队列用（FIFO）LinkedList<Integer>queue=newLinkedList<>();queue.offer(1);// 入队queue.offer(2);queue.poll();// 出队 → 15. 源码中最容易被问到的几个点
- addFirst / addLast 的实现（O(1)）
publicvoidaddFirst(Ee){linkFirst(e);}privatevoidlinkFirst(Ee){finalNode<E>f=first;finalNode<E>newNode=newNode<>(null,e,f);first=newNode;if(f==null)last=newNode;elsef.prev=newNode;size++;modCount++;}- get(int index) 为何慢（O(n)）
publicEget(intindex){checkElementIndex(index);returnnode(index).item;}Node<E>node(intindex){// assert isElementIndex(index);if(index<(size>>1)){// 前半段从头开始找Node<E>x=first;for(inti=0;i<index;i++)x=x.next;returnx;}else{// 后半段从尾开始找（关键优化！）Node<E>x=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}}- 为什么 LinkedList 实现了 RandomAccess 接口？
答案：它其实没有实现 RandomAccess！
（ArrayList 实现了，LinkedList 没有）
publicclassArrayList<E>...implementsRandomAccess...publicclassLinkedList<E>...// 没有 implements RandomAccess这也是为什么List遍历时推荐用for-each或iterator，而不是get(i)循环的原因。
6. 面试高频题 TOP 10（带答案）
LinkedList 是线程安全的吗？
否。所有方法都没有 synchronized。LinkedList 和 ArrayList 的区别？（必问）
| 项目 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(n) |
| 插入/删除（头尾） | O(n)（需移动元素） | O(1) |
| 插入/删除（中间） | O(n) | O(n)（查找）+O(1)（修改指针） |
| 内存开销 | 较小（连续） | 较大（每个节点有 prev/next） |
| 适用场景 | 读多写少、频繁随机访问 | 频繁头尾增删、队列/栈 |
LinkedList 可以当栈和队列用吗？怎么用？
可以。推荐用 push/pop 当栈，offer/poll 当队列。为什么 LinkedList 没有 capacity（容量）概念？
因为是链表，不需要预分配空间。Iterator 和 ListIterator 的区别？
LinkedList 的 iterator() 是单向的，listIterator() 是双向的，支持 add/set/remove。modCount 有什么作用？
快速失败机制（fail-fast）。结构修改时 modCount++，迭代器发现 modCount 变化就抛 ConcurrentModificationException。ConcurrentLinkedQueue 和 LinkedList 的区别？
前者是线程安全的无界队列（CAS），后者非线程安全。为什么不建议用 LinkedList 做大数据量的随机访问？
每次 get(i) 都要从头/尾遍历，时间复杂度 O(n)，n 很大时很慢。LinkedList 的 subList() 返回的是什么？
SubList 内部类，是原链表的视图，修改会影响原链表（非深拷贝）。实际项目中什么时候选 LinkedList？
- 频繁在头部/尾部增删（如队列、栈、滑动窗口）
- 作为 Deque 使用
- 内存不敏感，且明确知道不会频繁按索引访问
7. 2026 年真实使用建议
- 日常开发：99% 的 List 场景用ArrayList（读多写少）
- 用 LinkedList 的场景：
- LinkedBlockingQueue 的底层实现参考
- 手写 LRU Cache（双向链表 + HashMap）
- 某些滑动窗口 / 队列场景
- 需要频繁头尾操作且数据量不大
- 面试心态：能手写双向链表的增删节点、能说出 get(i) 为何 O(n)，基本就过关了。
需要我手写一个双向链表的完整实现（不依赖 LinkedList）吗？
或者想看 LinkedList 在 LeetCode 哪些题中是最佳解？
随时告诉我～
)
