LinkedList是单向链表还是双向链表？

Question

LinkedList 是单向链表还是双向链表？在 Java 中，`java.util.LinkedList` 的底层结构究竟是如何实现的？许多开发者在面试或实际开发中常误认为 LinkedList 是单向链表，但其内部节点类 `Node` 包含 `prev` 和 `next` 引用，表明它是双向链表。这种结构支持高效的双向遍历和在任意位置的插入删除操作。那么，为什么 Java 选择使用双向链表而非单向链表来实现 LinkedList？这对其性能和内存开销有何影响？请结合源码分析其设计优势与潜在缺点。

Answer 1

一、LinkedList 的基本认知：单向还是双向？

在 Java 中，java.util.LinkedList 是基于双向链表（Doubly Linked List）实现的。这一点从其内部节点类 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;
    }
}
    

每个节点包含三个字段：数据域 item、指向后继节点的 next 指针和指向前驱节点的 prev 指针。这种设计是典型的双向链表特征。

链表类型	前驱指针	后继指针	典型用途
单向链表	无	有	栈、简单队列
双向链表	有	有	Deque、List 随机访问优化

二、源码视角：为何选择双向链表？

Java 的 LinkedList 实现了 List 和 Deque 接口，这意味着它必须支持：

• 在任意位置插入/删除元素（List 特性）
• 两端高效添加/移除元素（Deque 特性）
• 双向迭代（如 ListIterator）

若采用单向链表，实现 removeLast() 或反向遍历时需从头遍历至倒数第二个节点，时间复杂度为 O(n)。而双向链表通过 prev 指针可直接定位前驱节点，使这些操作降至 O(1)。

// 示例：获取最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

// 删除最后一个节点
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
    

三、性能与内存开销的权衡分析

双向链表的设计带来了显著的操作优势，但也引入了额外的内存开销。我们通过以下对比进行量化分析：

操作	单向链表	双向链表（LinkedList）
addFirst(e)	O(1)	O(1)
addLast(e)	O(1)	O(1)
removeFirst()	O(1)	O(1)
removeLast()	O(n)	O(1)
listIterator(index).hasPrevious()	不支持	O(1)
内存占用（每节点）	2 指针 + 数据	3 指针 + 数据

可以看出，在涉及尾部操作或反向迭代的场景中，双向链表具有压倒性优势。这也是 Java 设计者选择它的根本原因——优先保障接口语义的完整性与操作效率。

四、设计优势与潜在缺点深度剖析

结合 JDK 源码与实际应用场景，我们可以总结出如下设计考量：

1. 支持高效的双向遍历：通过 ListIterator 可向前或向后移动，适用于需要逆序处理的业务逻辑。
2. 实现 Deque 接口更自然：作为双端队列，offerFirst、pollLast 等操作无需遍历。
3. 插入删除统一高效：无论在头部、中部还是尾部，修改指针即可完成，平均时间复杂度 O(1)（已知节点位置）。
4. 内存开销增加约 50%：相比单向链表，每个节点多一个引用字段，在大规模数据下可能成为瓶颈。
5. 缓存局部性较差：节点分散在堆中，不像 ArrayList 连续存储，影响 CPU 缓存命中率。
6. 垃圾回收压力增大：更多对象引用增加了 GC 扫描负担，尤其在频繁增删的场景中。

五、可视化理解：LinkedList 结构示意图

以下是 LinkedList 添加三个元素后的内存结构图：

graph LR
    A[head] --> B[Node: prev=null, item=A, next→]
    B --> C[Node: prev←, item=B, next→]
    C --> D[Node: prev←, item=C, next=null]
    D --> E[tail]
    style A fill:#f9f,stroke:#333
    style E fill:#f9f,stroke:#333
    

图中清晰展示了前后指针的连接方式，以及头尾节点的维护机制。这种结构使得从任一方向遍历都只需常数步跳转。