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

目录

一、ArrayList的短板：为什么还需要LinkedList？

1.1 ArrayList的痛点

二、链表：另一种组织数据的方式

2.1 什么是链表？

2.2 链表的分类

2.3 我们重点关注的两种链表

无头单向非循环链表

无头双向循环链表（LinkedList的底层实现）

三、LinkedList的底层实现：手写一个简化版

3.1 定义节点类

3.2 实现核心方法

3.3 测试我们的实现

四、LinkedList的使用

4.1 构造LinkedList

4.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的痛点

// 场景：频繁在列表头部插入数据 List<Integer> 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 链表的分类

链表有很多变种，理解它们之间的区别是关键：

这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

// 方式一：无参构造 List<Integer> list1 = new LinkedList<>(); // 方式二：用已有集合构造 List<String> source = new ArrayList<>(); source.add("Java"); source.add("Python"); List<String> list2 = new LinkedList<>(source);

4.2 常用方法一览

LinkedList<String> 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 四种遍历方式

LinkedList<Integer> 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(); // 方式二：正向迭代器 ListIterator<Integer> it = list.listIterator(); while (it.hasNext()) { System.out.print(it.next() + " "); } System.out.println(); // 方式三：反向迭代器 ListIterator<Integer> 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的全面对比

5.1 如何选择？

选ArrayList的场景：

• 主要操作是读取和遍历

• 主要在尾部添加数据

• 数据量可预估，避免频繁扩容

选LinkedList的场景：

• 频繁在头部或中间插入/删除

• 需要实现队列或双端队列功能

• 数据量不确定，且操作频繁

5.2 一个简单的选择判断

// 场景一：批量读取数据，偶尔修改 List<User> userList = new ArrayList<>(); // ✅ // 场景二：实现一个消息队列 List<Message> 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 + nR（n≥1，快指针可能在环里绕了n圈）

因为快指针速度是慢指针的2倍：

2(L + X) = L + X + nR

L + X = nR

L = nR - X

这意味着：从起点出发的指针和从相遇点出发的指针，每次都走一步，最终会在环入口相遇。

七、总结与学习建议

7.1 核心要点回顾

1. 链表是非连续存储的数据结构，通过指针链接节点

2. LinkedList底层是无头双向循环链表

3. 链表插入删除快（O(1)），但随机访问慢（O(n)）

4. 选择ArrayList还是LinkedList，取决于你的主要操作类型

5. 链表的快慢指针是解决许多问题的利器

7.2 学习路线建议

1. 先理解原理：画图理解链表的节点关系和操作过程

2. 手写实现：自己实现一遍核心方法，加深理解

3. 阅读源码：打开IDE看LinkedList的源码，学习大师的设计思想

4. 刷题巩固：在LeetCode上刷链表专题，把快慢指针、反转链表等技巧练熟

如果你觉得这篇文章对你有帮助，欢迎点赞收藏。下一篇我们将深入栈和队列，看看这两种特殊的线性表是如何在实际开发中大显身手的，敬请期待！

注：本文为个人学习总结，所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。