LinkedList源码解析

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 的存储对比

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; // 帮助GC
    size--;
    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) 设计取舍

5. 应用场景建议

• 使用 LinkedList 的场景：
  • 频繁在 头部/中部 插入删除（如实现队列/栈）。
  • 不需要频繁随机访问。
• 使用 ArrayList 的场景：
  • 需要快速随机访问。
  • 内存敏感型应用。