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

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

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

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

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

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

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

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

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

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

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

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

1. 创建新节点：LinkedList 会创建一个全新的 Node 对象。这个节点的结构非常简单，包含三部分：
   • item：存储元素 "Hello"。
   • next：指向下一个节点的引用。
   • prev：指向前一个节点的引用。
2. 初始化节点：由于这是第一个节点，它的 prev 和 next 都指向 null。
3. 更新指针：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") 时，链表开始延伸。

1. 创建新节点：创建一个新的 Node 对象，存储元素 "World"。
2. 建立连接：
   • 前向连接：第一个节点（当前的 last）的 next 指针，将指向这个新节点。
   • 后向连接：新节点的 prev 指针，将指向第一个节点。
3. 更新尾指针：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 的核心工作原理：

LinkedList 的“动态”源于其节点化和指针链接的设计。它用 first 和 last 两个指针高效地管理链表的两端，用 prev 和 next 构建了双向的连接，使得头尾操作异常迅速。

何时选择 LinkedList？

• 频繁在列表的头部或尾部进行插入/删除操作。
• 需要实现栈（Stack） 或 队列（Queue） 的数据结构（LinkedList 实现了 Deque 接口）。

何时避免 LinkedList？

• 需要频繁进行随机访问（get(index)），因为需要从头或尾遍历。
• 内存非常紧张，因为每个节点有额外的引用开销。

理解了 LinkedList 的双向链表本质，你就能在 ArrayList 和 LinkedList 之间做出更明智的选择。

希望这篇解析能帮你彻底掌握 LinkedList 的源码精髓！