Java 中 LinkedList 的底层数据结构及相关分析

Java 中 LinkedList 的底层数据结构及相关分析

1. 概述

LinkedList 是 Java 集合框架（Java Collections Framework，JCF）中的一个双向链表实现，它位于 java.util 包下，支持 列表（List） 和 队列（Queue） 相关操作。

在 LinkedList 中，元素的存储方式不同于 ArrayList，它使用 链表 结构来存储元素，因此在某些场景下比 ArrayList 具有更好的性能表现。

2. LinkedList 的底层数据结构

2.1 底层实现

LinkedList 的底层是一个 双向链表（Doubly Linked List），它的基本存储单元是 Node（内部静态类），每个节点包含：

• 数据域 (item)：存储当前节点的数据。
• 前驱指针 (prev)：指向前一个节点。
• 后继指针 (next)：指向后一个节点。

2.2 源码解析（JDK 8）

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;
    }
}

LinkedList 通过 first 和 last 维护头尾节点：

transient Node<E> first;
transient Node<E> last;

3. LinkedList 的实现原理

3.1 添加元素

add(E e) (默认尾部添加)

1. 创建新节点。
2. 让新节点的 prev 指向旧的 last，并更新 last 指针。
3. 若链表为空，则 first 也指向该节点。

示例代码：

public boolean add(E e) {
    linkLast(e);
    return true;
}

private 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;
}

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

1. 先找到索引位置的前驱和后继节点。
2. 让新节点的 prev 和 next 指向前驱和后继。
3. 更新前驱和后继节点的指针。

3.2 删除元素

• removeFirst()：删除 first 指向的节点，调整 first 指针。
• removeLast()：删除 last 指向的节点，调整 last 指针。
• remove(index)：找到索引对应节点，调整前后指针。

示例代码（删除头节点）：

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    return element;
}

3.3 查找元素

• get(int index)：通过索引访问元素。
• contains(Object o)：遍历链表检查是否包含该元素。
• indexOf(Object o)：遍历链表查找元素的索引。

get(int index) 方法会从 first 或 last 开始遍历（优化访问）：

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;
    }
}

4. LinkedList 的应用场景

4.1 适用场景

• 频繁插入和删除元素（避免 ArrayList 频繁扩容和移动元素）。
• 作为队列（Queue）使用，如 Deque 结构（poll()、peek() 操作）。
• 作为栈（Stack）使用，如 push()、pop() 操作。
• 需要双向遍历的场景。

4.2 不适用场景

• 需要频繁随机访问的情况，get(index) 需要 O(n) 时间。
• 存储大量数据时，链表结构的额外指针占用较多内存。

5. LinkedList 的优缺点

5.1 优点

✅ 插入和删除操作效率高，时间复杂度 O(1)。
✅ 适用于 FIFO 队列和 LIFO 栈操作。
✅ 动态分配内存，避免 ArrayList 频繁扩容。

5.2 缺点

❌ 访问元素效率低，查找时间复杂度 O(n)。
❌ 额外的 prev 和 next 指针增加内存占用。
❌ 不适用于高并发场景（非线程安全）。

6. 替代方案

示例：如果希望使用线程安全的队列，可以使用 ConcurrentLinkedQueue：

Queue<Integer> queue = new ConcurrentLinkedQueue<>();
queue.add(10);
queue.add(20);
System.out.println(queue.poll()); // 输出 10

7. 总结

• LinkedList 底层是 双向链表，适用于 频繁插入/删除，但 随机访问较慢。
• 适用于 队列（FIFO）、栈（LIFO） 相关应用。
• 在大多数情况下，ArrayList 比 LinkedList 更合适，除非有特殊需求。
• 需要线程安全时，可使用 ConcurrentLinkedQueue、CopyOnWriteArrayList 等。