JCSprout 源码精读LinkedList 底层双向链表实现与增查性能分析【免费下载链接】JCSprout‍ Java Core Sprout : basic, concurrent, algorithm项目地址: https://gitcode.com/gh_mirrors/jc/JCSprout导读本文基于 JCSprout 知识库中的 LinkedList 底层分析docs 目录下另有同主题文档 docs/collections/LinkedList.md并在 docs/_sidebar.md 中作为“集合”板块的核心条目收录系统拆解LinkedList基于双向链表的底层实现逐行分析新增add/linkLast与查询get/node两条核心链路并结合仓库内的 JMH 基准测试与链表排序源码说明“插入删改快、随机访问慢”这一特性的来源。读完本文你将能够从字节码级别的数据结构视角回答面试中关于LinkedList与ArrayList选型的经典问题并理解为什么随机访问越靠近链表中间代价越高。LinkedList 的数据结构双向链表LinkedList底层是基于双向链表实现的它同样实现了List接口因此继承了List允许重复元素、保持插入顺序等语义。需要注意的是JDK 1.7/1.8 之后取消了循环链表结构修改为标准的双向链表——即链表中不再有“首尾相连”的环形引用而是由一个first头结点和一个last尾结点界定边界。每个链表节点Node持有三部分信息item当前节点存储的元素next指向后继节点的指针prev指向前驱节点的指针。正是由于每个节点同时持有前后两个方向的指针LinkedList才能实现 O(1) 的头尾插入/删除以及后续将要分析的“从两端向中间折半遍历”的查询策略。新增方法移动指针而非拷贝数组LinkedList的默认尾部新增入口是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; }关键点解读先取出当前尾结点l以(l, e, null)构造新节点——新节点的前驱指向旧尾结点后继为null将last指向新节点若链表为空l null则新节点同时作为first头结点否则把旧尾结点l.next指向新节点完成指针链接最后size维护元素个数modCount记录结构性修改次数供迭代器做 fail-fast 检查。可以看出整个插入过程只需要创建新节点并调整两处指针引用没有任何数组拷贝动作。对比同一知识库中 ArrayList 底层分析 的add(E e)——它需要先执行ensureCapacityInternal扩容校验在容量不足时触发Arrays.copyOf数组复制而指定位置插入add(int index, E element)更是要System.arraycopy把 index 之后的元素整体后移。因此对“只在尾部追加”的场景LinkedList的插入效率相比ArrayList要高出不少。仓库中的 JMH 基准测试 CollectionsTest.java 正好印证了这一结论它分别对ArrayList无参构造、ArrayList预分配 1000 万容量与LinkedList各执行 1000 万次尾部add(123)并以微秒为单位的平均耗时Mode.AverageTime作为比较基准。该测试代码即为 JCSprout 对“LinkedList 插入快、ArrayList 扩容有开销”这一理论判断的实测证据感兴趣的读者可以在本地用 JMH 运行CollectionsTest观察三者差异。查询方法双向链表带来的折半遍历LinkedList的随机访问通过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; } }这段代码是双向链表“用空间换时间”思想的典型体现先通过checkElementIndex(index)校验下标合法性size 1等价于size / 2若index小于链表大小的一半说明目标离头结点更近则从first出发沿next正向遍历否则说明目标离尾结点更近则从last出发沿prev反向遍历。即node()会以O(n/2)的性能去获取一个结点当索引值大于链表大小的一半时将从尾结点开始遍历。相比ArrayList基于数组下标 O(1) 的随机访问这样的查找效率是非常低的特别是当 index 越接近 size 的中间值时——此时无论从头部还是尾部出发都要走完约一半的节点数。因此可以给出明确的选型结论LinkedList插入、删除都是移动指针效率很高查找需要进行遍历查询效率较低。结合源码的延伸思考链表场景下的算法实践理解了“链表查询靠遍历”之后再来审视仓库中对链表的实际算法运用会更有收获。LinkedListMergeSort.java 实现了一个单向链表的归并排序其注释明确建议链表排序使用归并排序——因为链表的随机访问是 O(n) 的而快排依赖下标访问归并排序只需顺序遍历即可完成与链表的指针移动模型天然契合。该实现中值得注意的细节是归并时需要在中间元素位置将middle.next置为null从而把一个链表打散为两个独立链表源码注释中专门强调了这一点随后递归对左右两半排序再用双指针合并。合并逻辑与仓库中 MergeTwoSortedLists.java 一脉相承对应的单元测试见 LinkedListMergeSortTest.java其中覆盖了左右链表为空、单节点、长度 2 等多种边界情况。这段算法代码虽然不是LinkedList类本身但它揭示了同一条底层规律链表数据结构的特点无下标、指针相连决定了它的插入删除优势也决定了它的查询和排序策略必须围绕“指针遍历”来设计。这也正是面试中“链表排序为什么选归并”问题的答案来源。总结操作LinkedList 底层行为复杂度尾部新增add(e)linkLast创建新节点、移动指针O(1)指定位置插入/删除定位节点遍历 指针调整O(n)定位开销随机访问get(i)node()从头部或尾部折半遍历O(n/2)最坏 O(n)核心结论与 MD/LinkedList.md 保持一致LinkedList底层是双向链表JDK 1.7/8 之后为无环双向链表实现List接口新增元素通过linkLast移动指针完成比ArrayList的数组扩容/拷贝效率高随机访问依赖node()的折半遍历以 O(n/2) 的代价换取节点越靠近中间越慢工程选型上频繁头部/尾部增删选LinkedList频繁按下标随机访问选ArrayList且ArrayList应尽量预估容量减少扩容。【免费下载链接】JCSprout‍ Java Core Sprout : basic, concurrent, algorithm项目地址: https://gitcode.com/gh_mirrors/jc/JCSprout创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考