当前位置：首页 > ds >正文

【集合框架LinkedList底层添加元素机制】

ds 2025/8/20 8:29:49

在 Java 集合框架中，LinkedList 与 ArrayList 是两种截然不同的线性表实现。如果说 ArrayList 像一个可以伸缩的“盒子阵列”，那么 LinkedList 就像一条由“节点”串联而成的“双向链条”。

今天，我们将深入 LinkedList 的源码，一步步剖析它作为双向链表的精妙设计。通过这篇解析，你将彻底明白 LinkedList 是如何通过 first 和 last 指针，高效地管理元素的。

一、`LinkedList` 的诞生：空链的起点

当我们执行 new LinkedList<>() 时，LinkedList 在底层做了什么？

// 代码块
LinkedList<String> list = new LinkedList<>();

核心真相：此时，LinkedList 并没有创建任何节点。它只初始化了两个至关重要的指针（引用）：

first：指向链表的头节点（第一个节点）。
last：指向链表的尾节点（最后一个节点）。

在创建之初，链表为空，因此 first 和 last 都被初始化为 null。

// 代码块
// LinkedList 源码中的定义
transient Node<E> first;
transient Node<E> last;

二、成长的第一步：添加第一个元素

当我们调用 list.add("Hello") 时，发生了什么？

创建新节点：LinkedList 会创建一个全新的 Node 对象。这个节点的结构非常简单，包含三部分：
- item：存储元素 "Hello"。
- next：指向下一个节点的引用。
- prev：指向前一个节点的引用。
初始化节点：由于这是第一个节点，它的 prev 和 next 都指向 null。
更新指针：first 和 last 这两个指针，都指向这个新创建的节点。因为此时，这个节点既是头节点，也是尾节点。

// 代码块
// 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 的内部结构如下图所示：

三、链的延伸：添加第二个元素

当我们调用 list.add("World") 时，链表开始延伸。

创建新节点：创建一个新的 Node 对象，存储元素 "World"。
建立连接：
- 前向连接：第一个节点（当前的 last）的 next 指针，将指向这个新节点。
- 后向连接：新节点的 prev 指针，将指向第一个节点。
更新尾指针：last 指针不再指向第一个节点，而是更新为指向这个新创建的节点。first 指针保持不变，仍然指向第一个节点。

此时，链表的结构变成了：

first -> [item: "Hello", prev: null, next: ->] <-> [item: "World", prev: <-, next: null] <- last

四、双向链表的魅力：高效的操作

LinkedList 的双向链表结构赋予了它独特的优势：

1. 头尾操作的极致效率

addFirst() / addLast()：由于 first 和 last 指针的存在，向链表头部或尾部添加元素的时间复杂度都是 O(1)。
removeFirst() / removeLast()：同理，删除头尾元素也是 O(1)。

2. 中间插入/删除的“局部性”

在链表中间插入或删除元素，虽然需要先通过遍历找到位置（O(n)），但一旦找到，实际的插入/删除操作本身是 O(1) 的，因为它只需要修改相邻节点的指针，而不需要像 ArrayList 那样移动大量元素。

3. 内存的“按需分配”

与 ArrayList 预先分配数组不同，LinkedList 的每个节点都是在需要时才创建，内存使用更“灵活”，但每个节点有额外的 prev 和 next 引用开销。

最终效果：

五、总结：`LinkedList` 的设计哲学

通过这次源码级的剖析，我们可以总结出 LinkedList 的核心工作原理：

阶段	关键动作	指针变化
创建	初始化 `first` 和 `last` 指针	`first = null`, `last = null`
首次添加	创建节点，`first` 和 `last` 都指向它	`first -> Node1`, `last -> Node1`
后续添加	创建新节点，修改相邻节点指针，更新 `last`	`Node1.next -> Node2`, `Node2.prev -> Node1`, `last -> Node2`