数据结构(Java版)第八期：LinkedList与链表(三)

数据结构第八期：LinkedList 与链表（Java 版）

这是 Java 中最常被问到的数据结构之一，也是面试、笔试、日常开发中最容易踩坑的地方。

下面从原理 → 源码 → 常见操作 → 面试高频题 → 实际使用建议完整梳理一遍。

1. LinkedList 在 Java 中的真实身份

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

一句话总结：
LinkedList 同时实现了 List 和 Deque 接口，所以它既是“双向链表”，也是“双端队列”。

最关键的两点：

• 底层是双向链表（doubly-linked list）
• 没有像 ArrayList 那样的连续数组存储

2. 核心内部结构（JDK 8/11/17/21 一致）

private static class Node<E> {
    E item;              // 元素本身
    Node<E> next;        // 后继指针
    Node<E> prev;        // 前驱指针
}

三个重要成员变量：

transient int size = 0;          // 元素个数
transient Node<E> first;         // 头节点（first）
transient Node<E> last;          // 尾节点（last）

最经典的图示（双向链表）：

null ← prev   [prev | item | next] ↔ [prev | item | next] ↔ [prev | item | next]   next → null
               ↑ first                                             ↑ last

3. 常用操作的时间复杂度（面试必背）

操作	时间复杂度	说明
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 = new LinkedList<>();
stack.push(1);    // 入栈
stack.push(2);
stack.pop();      // 出栈 → 2

// 当队列用（FIFO）
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);   // 入队
queue.offer(2);
queue.poll();     // 出队 → 1

5. 源码中最容易被问到的几个点

1. addFirst / addLast 的实现（O(1)）

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

2. get(int index) 为何慢（O(n)）

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

3. 为什么 LinkedList 实现了 RandomAccess 接口？

答案：它其实没有实现 RandomAccess！
（ArrayList 实现了，LinkedList 没有）

public class ArrayList<E> ... implements RandomAccess ...
public class LinkedList<E> ... // 没有 implements RandomAccess

这也是为什么 List 遍历时推荐用 for-each 或 iterator，而不是 get(i) 循环的原因。

6. 面试高频题 TOP 10（带答案）

1. LinkedList 是线程安全的吗？
   否。所有方法都没有 synchronized。
2. LinkedList 和 ArrayList 的区别？（必问）

项目	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
插入/删除（头尾）	O(n)（需移动元素）	O(1)
插入/删除（中间）	O(n)	O(n)（查找）+O(1)（修改指针）
内存开销	较小（连续）	较大（每个节点有 prev/next）
适用场景	读多写少、频繁随机访问	频繁头尾增删、队列/栈

3. LinkedList 可以当栈和队列用吗？怎么用？
   可以。推荐用 push/pop 当栈，offer/poll 当队列。
4. 为什么 LinkedList 没有 capacity（容量）概念？
   因为是链表，不需要预分配空间。
5. Iterator 和 ListIterator 的区别？
   LinkedList 的 iterator() 是单向的，listIterator() 是双向的，支持 add/set/remove。
6. modCount 有什么作用？
   快速失败机制（fail-fast）。结构修改时 modCount++，迭代器发现 modCount 变化就抛 ConcurrentModificationException。
7. ConcurrentLinkedQueue 和 LinkedList 的区别？
   前者是线程安全的无界队列（CAS），后者非线程安全。
8. 为什么不建议用 LinkedList 做大数据量的随机访问？
   每次 get(i) 都要从头/尾遍历，时间复杂度 O(n)，n 很大时很慢。
9. LinkedList 的 subList() 返回的是什么？
   SubList 内部类，是原链表的视图，修改会影响原链表（非深拷贝）。
10. 实际项目中什么时候选 LinkedList？
    • 频繁在头部/尾部增删（如队列、栈、滑动窗口）
    • 作为 Deque 使用
    • 内存不敏感，且明确知道不会频繁按索引访问

7. 2026 年真实使用建议

• 日常开发：99% 的 List 场景用 ArrayList（读多写少）
• 用 LinkedList 的场景：
• LinkedBlockingQueue 的底层实现参考
• 手写 LRU Cache（双向链表 + HashMap）
• 某些滑动窗口 / 队列场景
• 需要频繁头尾操作且数据量不大
• 面试心态：能手写双向链表的增删节点、能说出 get(i) 为何 O(n)，基本就过关了。

需要我手写一个双向链表的完整实现（不依赖 LinkedList）吗？
或者想看 LinkedList 在 LeetCode 哪些题中是最佳解？
随时告诉我～