6.Java LinkedList深度解析：从链表原理到源码实践

目录一、ArrayList的短板为什么还需要LinkedList1.1 ArrayList的痛点二、链表另一种组织数据的方式2.1 什么是链表2.2 链表的分类2.3 我们重点关注的两种链表无头单向非循环链表无头双向循环链表LinkedList的底层实现三、LinkedList的底层实现手写一个简化版3.1 定义节点类3.2 实现核心方法3.3 测试我们的实现四、LinkedList的使用4.1 构造LinkedList4.2 常用方法一览4.3 四种遍历方式五、LinkedList与ArrayList的全面对比5.1 如何选择5.2 一个简单的选择判断六、链表面试题精选6.1 反转单链表6.2 寻找链表的中间节点6.3 判断链表是否有环6.4 寻找环的入口节点七、总结与学习建议7.1 核心要点回顾7.2 学习路线建议写在前面本文基于《LinkedList与链表》课程内容整理结合个人学习笔记和实践经验编写。文中所有示例代码均为独立编写旨在帮助读者深入理解链表这一基础数据结构以及Java中LinkedList的实现原理。如需系统学习建议配合Oracle官方文档和JDK源码阅读。一、ArrayList的短板为什么还需要LinkedList在前面的文章中我们详细介绍了ArrayList。它基于动态数组实现随机访问速度快但在某些场景下表现不尽如人意。1.1 ArrayList的痛点// 场景频繁在列表头部插入数据 ListInteger list new ArrayList(); for (int i 0; i 100000; i) { list.add(0, i); // 每次都在头部插入 }这段代码运行起来非常慢原因在于ArrayList底层是数组在头部插入元素时需要将所有已有元素向后移动一位。100000次插入意味着总共要移动约50亿次元素时间复杂度分析尾部插入O(1)头部/中间插入O(n)随机访问O(1)当我们的业务场景是频繁在任意位置插入和删除时ArrayList就显得力不从心了。这时候LinkedList闪亮登场。二、链表另一种组织数据的方式2.1 什么是链表链表是一种物理存储结构上非连续的数据结构数据元素之间的逻辑顺序通过指针引用链接起来。想象一下火车车厢每节车厢里装着货物数据车厢之间通过挂钩指针相连。你可以轻松地在任意位置加挂或卸下车厢而不需要移动其他车厢。2.2 链表的分类链表有很多变种理解它们之间的区别是关键分类维度类型特点方向单向链表每个节点只有next指针方向双向链表每个节点有prev和next指针头节点带头节点有一个哨兵节点不存数据头节点不带头节点第一个节点就存数据是否循环循环链表尾节点指向头节点是否循环非循环链表尾节点指向null这3个维度两两组合一共有2×2×2 8种​ 链表结构。2.3 我们重点关注的两种链表无头单向非循环链表head → [data|next] → [data|next] → [data|null]特点结构最简单只能从头到尾遍历删除节点时需要找到前驱节点应用场景哈希桶、图的邻接表、面试题常客无头双向循环链表LinkedList的底层实现head ↔ [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] ↔ head特点可以从两个方向遍历插入和删除都很方便首尾相连形成环应用场景Java中的LinkedList正是这种结构三、LinkedList的底层实现手写一个简化版理解了链表原理后我们来自己实现一个简单的双向链表这能帮助你更好地理解LinkedList的源码。3.1 定义节点类public class ListNode { public int val; // 节点存储的数据 public ListNode prev; // 指向前一个节点的引用 public ListNode next; // 指向后一个节点的引用 public ListNode(int val) { this.val val; } }3.2 实现核心方法public class MyLinkedList { private ListNode head; // 指向第一个节点 private ListNode tail; // 指向最后一个节点 private int size; // 链表长度 // 头插法在链表头部插入 public void addFirst(int data) { ListNode node new ListNode(data); if (head null) { // 链表为空 head tail node; } else { node.next head; head.prev node; head node; } size; } // 尾插法在链表尾部插入 public void addLast(int data) { ListNode node new ListNode(data); if (tail null) { head tail node; } else { tail.next node; node.prev tail; tail node; } size; } // 在指定位置插入 public void addIndex(int index, int data) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界); } if (index 0) { addFirst(data); return; } if (index size) { addLast(data); return; } // 找到index位置的节点 ListNode cur head; for (int i 0; i index; i) { cur cur.next; } // 在cur之前插入新节点 ListNode node new ListNode(data); node.prev cur.prev; node.next cur; cur.prev.next node; cur.prev node; size; } // 查找是否包含某元素 public boolean contains(int key) { ListNode cur head; while (cur ! null) { if (cur.val key) { return true; } cur cur.next; } return false; } // 删除第一次出现的key public void remove(int key) { ListNode cur head; while (cur ! null) { if (cur.val key) { // 删除cur节点 if (cur head) { head head.next; if (head ! null) { head.prev null; } } else { cur.prev.next cur.next; } if (cur tail) { tail tail.prev; if (tail ! null) { tail.next null; } } else { cur.next.prev cur.prev; } size--; return; } cur cur.next; } } // 获取链表长度 public int size() { return size; } // 打印链表 public void display() { ListNode cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } // 清空链表 public void clear() { ListNode cur head; while (cur ! null) { ListNode next cur.next; cur.prev null; cur.next null; cur next; } head tail null; size 0; } }3.3 测试我们的实现public static void main(String[] args) { MyLinkedList list new MyLinkedList(); list.addLast(1); list.addLast(2); list.addLast(3); list.display(); // 1 2 3 list.addFirst(0); list.display(); // 0 1 2 3 list.addIndex(2, 99); list.display(); // 0 1 99 2 3 list.remove(99); list.display(); // 0 1 2 3 System.out.println(是否包含2 list.contains(2)); // true System.out.println(链表长度 list.size()); // 4 }四、LinkedList的使用4.1 构造LinkedList// 方式一无参构造 ListInteger list1 new LinkedList(); // 方式二用已有集合构造 ListString source new ArrayList(); source.add(Java); source.add(Python); ListString list2 new LinkedList(source);4.2 常用方法一览LinkedListString list new LinkedList(); // 添加元素 list.add(A); // 尾部添加 list.add(1, B); // 指定位置添加 list.addFirst(HEAD); // 头部添加 list.addLast(TAIL); // 尾部添加 // 获取元素 String first list.getFirst(); // 获取第一个 String last list.getLast(); // 获取最后一个 String elem list.get(2); // 获取指定位置 // 删除元素 list.remove(); // 删除第一个 list.removeFirst(); // 删除第一个 list.removeLast(); // 删除最后一个 list.remove(1); // 删除指定位置 list.remove(B); // 删除指定元素 // 查找 boolean exists list.contains(A); int index list.indexOf(A); int lastIndex list.lastIndexOf(A); // 其他 int size list.size(); list.clear();4.3 四种遍历方式LinkedListInteger list new LinkedList(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); // 方式一foreach遍历最简洁 for (int num : list) { System.out.print(num ); } System.out.println(); // 方式二正向迭代器 ListIteratorInteger it list.listIterator(); while (it.hasNext()) { System.out.print(it.next() ); } System.out.println(); // 方式三反向迭代器 ListIteratorInteger rit list.listIterator(list.size()); while (rit.hasPrevious()) { System.out.print(rit.previous() ); } System.out.println(); // 方式四普通for循环不推荐效率低 for (int i 0; i list.size(); i) { System.out.print(list.get(i) ); // 每次get都要遍历 } System.out.println();特别注意LinkedList的get(int index)方法需要遍历链表找到目标位置时间复杂度为O(n)。在大数据量下用普通for循环遍历LinkedList是非常低效的做法。五、LinkedList与ArrayList的全面对比对比维度ArrayListLinkedList底层结构动态数组双向链表存储空间物理连续逻辑连续物理不连续随机访问O(1) ✅O(n) ❌头部插入O(n) ❌O(1) ✅尾部插入O(1) ✅O(1) ✅中间插入O(n) ❌O(1) ✅内存占用较小只存数据较大存数据前后指针扩容机制需要扩容1.5倍没有容量概念适用场景读多写少尾部操作写多读少任意位置操作5.1 如何选择选ArrayList的场景主要操作是读取和遍历主要在尾部添加数据数据量可预估避免频繁扩容选LinkedList的场景频繁在头部或中间插入/删除需要实现队列或双端队列功能数据量不确定且操作频繁5.2 一个简单的选择判断// 场景一批量读取数据偶尔修改 ListUser userList new ArrayList(); // ✅ // 场景二实现一个消息队列 ListMessage messageQueue new LinkedList(); // ✅ // 场景三不确定用哪个 // 如果80%以上是读取操作 → ArrayList // 如果80%以上是插入删除操作 → LinkedList六、链表面试题精选链表相关的题目是面试中的高频考点下面整理了几道经典题目附上解题思路。6.1 反转单链表public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } return prev; }思路遍历链表逐个改变节点的next指向。6.2 寻找链表的中间节点public ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }思路快慢指针法。快指针走两步慢指针走一步快指针到达末尾时慢指针正好在中间。6.3 判断链表是否有环public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }思路同样用快慢指针。如果链表有环快慢指针一定会相遇。为什么快指针走两步慢指针走一步一定能相遇假设慢指针刚进入环时快指针已经在环内。此时两指针相距最多为环的长度R。每次移动距离减少1步所以最多R次移动后必定相遇。如果快指针走3步、4步呢有可能永远追不上因为可能出现恰好套圈的情况。6.4 寻找环的入口节点public ListNode detectCycle(ListNode head) { ListNode slow head; ListNode fast head; // 先找到相遇点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 找到了相遇点 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } } return null; }数学原理设头节点到环入口距离为L环入口到相遇点距离为X环周长为R慢指针走过的路程L X快指针走过的路程L X nRn≥1快指针可能在环里绕了n圈因为快指针速度是慢指针的2倍2(L X) L X nRL X nRL nR - X这意味着从起点出发的指针和从相遇点出发的指针每次都走一步最终会在环入口相遇。七、总结与学习建议7.1 核心要点回顾链表是非连续存储的数据结构通过指针链接节点LinkedList底层是无头双向循环链表链表插入删除快O(1)但随机访问慢O(n)选择ArrayList还是LinkedList取决于你的主要操作类型链表的快慢指针是解决许多问题的利器7.2 学习路线建议先理解原理画图理解链表的节点关系和操作过程手写实现自己实现一遍核心方法加深理解阅读源码打开IDE看LinkedList的源码学习大师的设计思想刷题巩固在LeetCode上刷链表专题把快慢指针、反转链表等技巧练熟如果你觉得这篇文章对你有帮助欢迎点赞收藏。下一篇我们将深入栈和队列看看这两种特殊的线性表是如何在实际开发中大显身手的敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。