在 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 |
LinkedList 的“动态”源于其节点化和指针链接的设计。它用 first 和 last 两个指针高效地管理链表的两端，用 prev 和 next 构建了双向的连接，使得头尾操作异常迅速。
何时选择 LinkedList？
- 频繁在列表的头部或尾部进行插入/删除操作。
- 需要实现栈（Stack） 或 队列（Queue） 的数据结构（
LinkedList实现了Deque接口）。
何时避免 LinkedList？
- 需要频繁进行随机访问（
get(index)），因为需要从头或尾遍历。 - 内存非常紧张，因为每个节点有额外的引用开销。
理解了 LinkedList 的双向链表本质，你就能在 ArrayList 和 LinkedList 之间做出更明智的选择。
希望这篇解析能帮你彻底掌握 LinkedList 的源码精髓！
)
