企业官网建设流程全解析

• 文档
• 教程
• 后端

LinkedList 是 Java 集合框架中基于双向链表实现的 List，其插入删除仅需移动指针，而随机查询则需要遍历节点。本文以 JCSprout 仓库中的 LinkedList 底层分析 文档为核心，结合仓库内 JMH 基准测试与算法源码，深入拆解add()、get()的底层实现细节，并给出与 ArrayList 的选型结论。

一、LinkedList 的底层数据结构：双向链表

正如 docs/collections/LinkedList.md 所述，LinkedList底层是基于双向链表实现的，同时实现了List接口，因此拥有 List 的特点（有序、可重复、允许 null 等）。需要注意的是：JDK 1.7/1.8 之后 LinkedList 取消了循环链表结构，修改为标准的双向链表，即每个节点持有指向前驱节点和后继节点的两个指针。

其内部节点结构大致如下（JDK 1.8 源码）：

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

这与仓库中 LinkedListMergeSort.java 自定义的单向链表节点结构形成对照——后者只包含int e与Node next两个字段，说明"链表"本质就是"节点 + 指针"的串联结构，双向链表只是额外维护了prev指针以便双向遍历。

二、新增方法：add() 与 linkLast() 的指针移动

原文档给出了add(E e)的核心实现：

public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ 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; size++; modCount++; }

可以看到linkLast()的执行流程非常简洁：

1. 记录当前尾节点l = last；
2. 创建新节点newNode，其prev指向l，next指向null；
3. 更新链表尾部指针last = newNode；
4. 若链表为空（l == null），则新节点同时也是头节点first；
5. 否则将原尾节点的next指向新节点；
6. size++与modCount++维护集合大小与结构性修改计数。

关键点：整个插入过程只涉及指针的重新指向，没有任何元素的搬移。而 ArrayList 的底层分析 中展示的add(int index, E element)则需要先扩容校验，再通过System.arraycopy将 index 之后的所有元素向后移动一位，属于典型的"拷贝数组"操作。因此，在尾部追加的场景下，LinkedList 的插入效率远高于 ArrayList——这正是原文档所说"每次插入都是移动指针，和 ArrayList 的拷贝数组来说效率要高上不少"的依据。

仓库中的实际使用也能印证这一点：在 RedPacket.java（模拟微信红包生成）中，作者用List<Integer> moneys = new LinkedList<>()承接每次生成的随机红包金额，循环中反复执行尾部add()，正是利用 LinkedList 尾插移动指针的高效特性；随后在main方法中顺序遍历累加金额（RedPacket.java），即"高频尾部追加 + 顺序遍历"的典型使用范式。

三、查询方法：get() 与 node() 的折半遍历

原文档给出了get(int index)的实现：

public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(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; } }

这段代码充分利用了双向链表的特性做了"就近遍历"优化：

• get()先通过checkElementIndex(index)校验索引合法性，防止越界；
• node(index)通过size >> 1（等价于size / 2）判断目标索引位于链表的前半段还是后半段：
  • 索引小于链表大小的一半：从头节点first出发，沿next指针正向遍历；
  • 索引大于等于链表大小的一半：从尾节点last出发，沿prev指针反向遍历。

这就是原文档总结的"使用空间（双向链表）来换取时间"：相比单向链表只能从头部单向遍历，双向链表凭借prev指针多提供了一条从尾部折返的路径，将最坏情况下的遍历距离从O(n)优化到O(n/2)。

同时原文档也明确指出：node()以O(n/2)的性能获取一个结点，如果索引值大于链表大小的一半，将从尾结点开始遍历；这样的效率仍然非常低，特别是当 index 越接近 size 的中间值时。因为无论从哪一端出发，都需要逐节点"跳指针"访问，无法像数组那样通过下标直接寻址（elementData[index]一次内存访问即可完成）。

四、性能对比实验：仓库中的 JMH 基准测试

为验证"LinkedList 尾插高效、但随机访问是短板"的结论，JCSprout 在 CollectionsTest.java 中提供了基于 JMH（Java Microbenchmark Harness）的对比基准，核心配置如下：

@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) public class CollectionsTest { private static final int TEN_MILLION = 10000000; @Benchmark @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) public void arrayList() { List<String> array = new ArrayList<>(); for (int i = 0; i < TEN_MILLION; i++) { array.add("123"); } } @Benchmark @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) public void arrayListSize() { List<String> array = new ArrayList<>(TEN_MILLION); for (int i = 0; i < TEN_MILLION; i++) { array.add("123"); } } @Benchmark @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) public void linkedList() { List<String> array = new LinkedList<>(); for (int i = 0; i < TEN_MILLION; i++) { array.add("123"); } } // main 方法通过 OptionsBuilder 运行全部基准 }

测试设计要点解读：

• 三个基准方法都向集合中追加1000 万条字符串；
• arrayList()使用无参构造（默认容量 10，会触发多次扩容拷贝）；
• arrayListSize()使用指定容量构造（预分配 1000 万，避免扩容）；
• linkedList()使用 LinkedList 逐条尾插；
• 模式为AverageTime，单位微秒，衡量的是平均耗时（越小越好）。

该基准可以直观回答一个问题：无扩容成本时 ArrayList 的尾插是否一定慢于 LinkedList？参考 ArrayList 底层分析 的grow()源码可知，ArrayList 的主要开销正是数组扩容（Arrays.copyOf整体拷贝）与指定位置插入的数据搬移，因此：

• 若频繁在头部/中间插入，LinkedList 移动指针的优势明显；
• 若只在尾部追加且预分配容量，ArrayList 凭借内存连续性反而可能更快；
• LinkedList 的插入优势主要体现在"不关心扩容、只做指针操作"的任意位置插入场景。

运行方式：该测试类包含main方法，可直接在仓库根目录通过 Maven 执行，例如mvn test -Dtest=CollectionsTest（需在 pom.xml 已引入 JMH 依赖的前提下），或直接运行CollectionsTest.main查看本机基准结果。

五、LinkedList 的"副业"：作为队列/栈使用

LinkedList 不仅实现了List接口，还实现了Deque接口，提供addFirst/addLast、offer/poll、push/pop等双端操作，因此在仓库中常被当作队列使用。典型例子是 BinaryNode.java 的二叉树层序遍历：

public void levelIterator(BinaryNode node){ LinkedList<BinaryNode> queue = new LinkedList<>() ; //先将根节点入队 queue.offer(node) ; BinaryNode current ; while (!queue.isEmpty()){ current = queue.poll(); System.out.print(current.data+"--->"); if (current.getLeft() != null){ queue.offer(current.getLeft()) ; } if (current.getRight() != null){ queue.offer(current.getRight()) ; } } }

这里利用LinkedList的offer()（尾部入队）与poll()（头部出队）实现 FIFO 队列语义，配合"先进先出"完成二叉树的逐层输出。类似的队列用法还出现在 BinaryNodeTravel.java（层序遍历串联节点）以及 LRUAbstractMap.java（LRU 淘汰队列的offer/poll）中。

这从工程角度补充了原文档的结论：LinkedList 擅长的是"两端增删、顺序访问"型操作，无论作为 List 还是 Deque，其性能优势都集中在指针操作上，而劣势始终是按下标随机访问。

六、总结：LinkedList 的适用边界

结合原文档与仓库源码，可以给出如下结论：

• 插入、删除效率高：任意位置（尤其头部/中间）的增删只需移动指针，无需像 ArrayList 那样拷贝数组；
• 查找效率低：node()需要折半遍历，时间复杂度O(n/2)，索引越接近中间值开销越大；
• 适用场景：频繁增删、顺序遍历、作为队列/栈使用（如层序遍历、红包金额追加、LRU 队列）；
• 不适用场景：需要频繁按下标随机访问的业务，此时应选择基于数组的 ArrayList；
• 工程佐证：仓库内 CollectionsTest.java 提供了 1000 万次尾插的 JMH 对比基准，RedPacket.java、BinaryNode.java 则展示了 LinkedList 在"尾插 + 顺序遍历"和"队列"两类场景下的真实用法，读者可直接运行相关测试类复现验证。

一句话选型建议：链表操作（增删、双端访问）优先 LinkedList，下标随机访问优先 ArrayList；若需队列/栈且对并发无要求，LinkedList 同样是一个无需额外引入容器的轻量选择。

• 文档
• 教程
• 后端