恒美微站 Logo 恒美微站
  • 首页
  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心
  • 联系我们

LinkedList源码阅分析

  • 首页
  • 资讯中心
  • /
  • LinkedList源码阅分析

相关资讯

银河麒麟 V10 / 统信 UOS 深度适配(内核参数到 seccomp) 2026/8/21 14:25:43
PHP 在国产 CPU 上的编译与运行(四架构实战) 2026/8/21 14:25:43
djangochannelsrestframework 前后端实战:搭配 dcrf-client 构建实时 Web 应用的完整教程 2026/8/21 14:20:42

最新资讯

TikTok Shop店群自动化管理系统:不抢焦不抢屏,后台跑百店你前台打游戏
Cherry MX 键帽 3D 打印完整指南:5 步从模型文件到可用键帽
如何用 BallonTranslator 一键 AI 翻译整本漫画:漫画翻译完整指南
监听控制器:专业音频制作中信号路由与音量控制的核心枢纽
QMT量化交易入门:从Python环境配置到策略实盘部署全流程
几步把图表里的数据点提出来:Engauge Digitizer 免费使用指南

今日推荐

OpenCode AI编程助手:从核心原理到本地部署的完整实践指南
基于SpringBoot与Vue的企业资产与采购管理系统设计与实现(程序+文档+讲解)
Linux命令-uucico(UUCP传输程序)

本周热门

【文章复现】非线性值迭代自适应动态规划(ADP):离散时间非线性系统的策略迭代自适应动态规划算法研究附Matlab代码
【双层规划,节点出清价,绿证交易,CVaR方法】两级电力市场环境下计及风险的省间交易商最优购电模型附Matlab代码
隐式mpc+自适应mpc+时变mpc,线性时变模型预测控制附Simulink仿真

本月精选

如何用DamaiHelper实现演唱会门票的智能自动化抢购:完整技术解决方案指南
第4篇:59 倍性能差距的索引瓶颈定位——一次教科书级的全表扫描调优
终极歌词批量下载神器:5分钟解决离线音乐库歌词同步难题

LinkedList源码阅分析

发布时间:2026/8/21 14:25:43
LinkedList源码阅分析 一、引言LinkedList是 Java 集合框架中基于双向链表实现的重要数据结构。理解其内部实现细节特别是各种操作的实现原理有助于避免常见的空指针异常并对链表的优缺点形成更全面的认识。本文将通过源码分析深入探讨 LinkedList 的核心实现机制。二、继承关系与整体结构2.1 继承关系图与 ArrayList 相比LinkedList 实现了 List 和 Deque 接口支持双向队列操作。2.2 核心数据结构LinkedList 中的每个元素都存储在 Node 节点中Node 是一个典型的双向链表节点结构private static class NodeE { E item; // 存储元素 NodeE next; // 指向下一个元素 NodeE prev; // 指向上一个元素 Node(Nodelt;Egt; prev, E element, Nodelt;Egt; next) { this.item element; this.next next; this.prev prev; } }2.3 成员变量LinkedList 主要维护三个核心变量transient int size 0; // 当前列表的元素个数 /** Pointer to first node. Invariant: (first null last null) || (first.prev null amp;amp; first.item ! null) */ transient NodeE first; // 第一个元素 /** Pointer to last node. Invariant: (first null last null) || (last.next null amp;amp; last.item ! null) */ transient NodeE last; // 最后一个元素三、构造函数与初始化LinkedList 提供两个构造函数public LinkedList() {} // 无参构造函数 public LinkedList(Collection? extends E c) { this(); addAll(c); // 将集合c中的所有元素添加到列表中 }四、核心操作方法4.1 批量添加元素addAll() 方法支持在指定位置批量添加元素public boolean addAll(Collection? extends E c) { return addAll(size, c); // 默认添加到末尾 } public boolean addAll(int index, Collection? extends E c) { checkPositionIndex(index); // 检查位置合法性 [0, size] Object[] a c.toArray(); int numNew a.length; if (numNew 0) return false; Nodelt;Egt; pred, succ; // 前驱与后继节点 if (index size) { // 添加到末尾 succ null; pred last; } else { // 添加到中间位置 succ node(index); // 获取index位置的节点作为后继 pred succ.prev; // 后继的前驱作为前驱 } // 逐个插入新节点 for (Object o : a) { SuppressWarnings(unchecked) E e (E) o; Nodelt;Egt; newNode new Nodelt;gt;(pred, e, null); if (pred null) first newNode; else pred.next newNode; pred newNode; } // 连接剩余部分 if (succ null) { last pred; } else { pred.next succ; succ.prev pred; } size numNew; modCount; return true; }4.2 节点查找优化node() 方法通过二分查找优化节点访问NodeE node(int index) { // 根据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; } }4.3 测试示例public class Main { public static void main(String[] args) { ListString list new LinkedList(Arrays.asList(1, 2, 3)); System.out.println(list.toString()); // [1, 2, 3] list.addAll(2, Arrays.asList(4, 5)); System.out.println(list.toString()); // [1, 2, 4, 5, 3] list.addAll(0, Arrays.asList(6, 7)); System.out.println(list.toString()); // [6, 7, 1, 2, 4, 5, 3] } }五、元素添加操作5.1 基本添加方法LinkedList 提供了三个核心的链接方法5.1.1 链接到头部private void linkFirst(E e) { final NodeE f first; final NodeE newNode new Node(null, e, f); first newNode; if (f null) last newNode; else f.prev newNode; size; modCount; }5.1.2 链接到尾部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; }5.1.3 链接到指定节点前void linkBefore(E e, NodeE succ) { final NodeE pred succ.prev; final NodeE newNode new Node(pred, e, succ); succ.prev newNode; if (pred null) first newNode; else pred.next newNode; size; modCount; }5.2 公共添加接口public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { checkPositionIndex(index); if (index size) linkLast(element); else linkBefore(element, node(index)); } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); }六、元素删除操作6.1 核心删除方法6.1.1 删除首节点private E unlinkFirst(NodeE f) { final E element f.item; final NodeE next f.next; f.item null; f.next null; // help GC first next; if (next null) last null; else next.prev null; size--; modCount; return element; }6.1.2 删除尾节点private E unlinkLast(NodeE l) { final E element l.item; final NodeE prev l.prev; l.item null; l.prev null; // help GC last prev; if (prev null) first null; else prev.next null; size--; modCount; return element; }6.1.3 删除任意节点E unlink(NodeE x) { final E element x.item; final NodeE next x.next; final NodeE prev x.prev; if (prev null) { first next; } else { prev.next next; x.prev null; } if (next null) { last prev; } else { next.prev prev; x.next null; } x.item null; size--; modCount; return element; }6.2 公共删除接口public E removeFirst() { final NodeE f first; if (f null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final NodeE l last; if (l null) throw new NoSuchElementException(); return unlinkLast(l); } public boolean remove(Object o) { if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) { unlink(x); return true; } } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }七、元素修改与查询7.1 修改元素public E set(int index, E element) { checkElementIndex(index); NodeE x node(index); E oldVal x.item; x.item element; return oldVal; }7.2 查询元素public E get(int index) { checkElementIndex(index); return node(index).item; } public E getFirst() { final NodeE f first; if (f null) throw new NoSuchElementException(); return f.item; } public E getLast() { final NodeE l last; if (l null) throw new NoSuchElementException(); return l.item; }7.3 查找元素位置public int indexOf(Object o) { int index 0; if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) return index; index; } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) return index; index; } } return -1; } public int lastIndexOf(Object o) { int index size; if (o null) { for (NodeE x last; x ! null; x x.prev) { index--; if (x.item null) return index; } } else { for (NodeE x last; x ! null; x x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }八、边界检查与工具方法// 下标检查保证数组访问不越界 [0, size) private boolean isElementIndex(int index) { return index 0 index size; } // 位置检查用于插入操作 [0, size] private boolean isPositionIndex(int index) { return index 0 index size; }九、总结与扩展LinkedList 作为双向链表的实现在插入和删除操作上具有 O(1) 的时间复杂度已知节点位置时但随机访问需要 O(n) 的时间。它还实现了 Queue 接口支持队列操作。在实际使用中需要根据具体场景选择合适的数据结构。关于序列化和迭代器的实现与 ArrayList 有所不同可以参考 ArrayList 的相关解析进行对比学习。

关于恒美微站

恒美微站专注于为个体商户、工作室提供极简自助建站服务,让每个人都能轻松拥有专业网站。

快速链接

  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心

服务项目

  • 可视化建站
  • 拖拽编辑
  • 主题定制
  • SEO 优化
  • 网站托管

联系方式

  • 📍 地址:北京市朝阳区建国路 88 号
  • 📞 电话:400-888-8888
  • ✉️ 邮箱:info@hmyw.cn
  • 🕐 时间:周一至周日 9:00-18:00

© 2024 恒美微站 hmyw.cn 版权所有 | 京 ICP 备 12345678 号