文档教程后端【免费下载链接】JCSprout Java Core Sprout : basic, concurrent, algorithm项目地址https://gitcode.com/gh_mirrors/jc/JCSprout点击查看免费下载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 NodeE { E item; // 节点存储的数据 NodeE next; // 指向后继节点 NodeE prev; // 指向前驱节点 Node(NodeE prev, E element, NodeE 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 NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }可以看到linkLast()的执行流程非常简洁记录当前尾节点l last创建新节点newNode其prev指向lnext指向null更新链表尾部指针last newNode若链表为空l null则新节点同时也是头节点first否则将原尾节点的next指向新节点size与modCount维护集合大小与结构性修改计数。关键点整个插入过程只涉及指针的重新指向没有任何元素的搬移。而 ArrayList 的底层分析 中展示的add(int index, E element)则需要先扩容校验再通过System.arraycopy将 index 之后的所有元素向后移动一位属于典型的拷贝数组操作。因此在尾部追加的场景下LinkedList 的插入效率远高于 ArrayList——这正是原文档所说每次插入都是移动指针和 ArrayList 的拷贝数组来说效率要高上不少的依据。仓库中的实际使用也能印证这一点在 RedPacket.java模拟微信红包生成中作者用ListInteger moneys new LinkedList()承接每次生成的随机红包金额循环中反复执行尾部add()正是利用 LinkedList 尾插移动指针的高效特性随后在main方法中顺序遍历累加金额RedPacket.java即高频尾部追加 顺序遍历的典型使用范式。三、查询方法get() 与 node() 的折半遍历原文档给出了get(int index)的实现public E get(int index) { checkElementIndex(index); return node(index).item; } NodeE node(int index) { // assert isElementIndex(index); if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE 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 中提供了基于 JMHJava 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() { ListString array new ArrayList(); for (int i 0; i TEN_MILLION; i) { array.add(123); } } Benchmark BenchmarkMode(Mode.AverageTime) OutputTimeUnit(TimeUnit.MICROSECONDS) public void arrayListSize() { ListString 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() { ListString 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 -DtestCollectionsTest需在 pom.xml 已引入 JMH 依赖的前提下或直接运行CollectionsTest.main查看本机基准结果。五、LinkedList 的副业作为队列/栈使用LinkedList 不仅实现了List接口还实现了Deque接口提供addFirst/addLast、offer/poll、push/pop等双端操作因此在仓库中常被当作队列使用。典型例子是 BinaryNode.java 的二叉树层序遍历public void levelIterator(BinaryNode node){ LinkedListBinaryNode 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.javaLRU 淘汰队列的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 同样是一个无需额外引入容器的轻量选择。赞分享文档教程后端【免费下载链接】JCSprout Java Core Sprout : basic, concurrent, algorithm项目地址https://gitcode.com/gh_mirrors/jc/JCSprout点击查看免费下载相关推荐JCSprout 源码精读LinkedList 底层双向链表实现与增查性能分析JCSprout 源码精读LinkedList 底层双向链表实现与增查性能分析 导读 本文基于 JCSprout 知识库中的 LinkedList 底层分析文档教程后端JCSprout 源码级解读LinkedHashMap 底层原理与基于双向链表的 LRU 缓存实战JCSprout 源码级解读LinkedHashMap 底层原理与基于双向链表的 LRU 缓存实战 LinkedHashMap 是 JDK 中为数不多天生有文档教程后端Ferdium开发者指南从零开始构建自定义功能扩展Ferdium开发者指南从零开始构建自定义功能扩展 Ferdium是一款强大的开源桌面应用能够将所有常用服务整合到一个界面中帮助用户高效管理工作流。本指南即时通讯桌面应用上一篇终极 Elementary OS 官网项目问题解决指南10个常见故障排除技巧下一篇VAT Calculator 开源项目常见问题解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
