链表从入门到精通：一文掌握链表的精髓
一、链表的基本概念：为什么需要链表？
1.1 数组的局限性
在介绍链表之前，我们先回顾一下数组的特点：
// 数组示例 int[] arr = new int[10]; // 固定大小，一旦创建无法改变 arr[0] = 1; // 随机访问，O(1)时间复杂度数组的缺点：
- 大小固定，扩展/收缩成本高
- 插入和删除元素需要移动大量元素（O(n)时间复杂度）
- 可能造成内存浪费（分配过大）或空间不足（分配过小）
假如数组的长度为 n。
访问：O（1）//访问特定位置的元素
插入：O（n）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时
1.2 链表的诞生
链表就是为了解决数组的这些痛点而设计的动态数据结构：
// 链表的节点定义 class Node { int data; // 存储数据 Node next; // 指向下一个节点 public Node(int data) { this.data = data; this.next = null; } }二、链表的核心结构与类型
2.1 单链表（Singly Linked List）
单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。
public class SinglyLinkedList { // 节点定义 private static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } private ListNode head; // 头节点 private int size; // 链表长度 public SinglyLinkedList() { head = null; size = 0; } // 添加节点到头部 public void addAtHead(int val) { ListNode newNode = new ListNode(val); newNode.next = head; head = newNode; size++; } }这里我将调用addAtHead三次并且将其可视化表示出来
初始: head → null
addAtHead(5): head → [5|next] → null
addAtHead(3): head → [3|next] → [5|next] → null
addAtHead(1): head → [1|next] → [3|next] → [5|next] → null
2.2 双链表（Doubly Linked List）
双向链表 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
public class DoublyLinkedList { // 双向节点定义 class DListNode { int val; DListNode prev; // 指向前驱节点 DListNode next; // 指向后继节点 DListNode(int val) { this.val = val; } } private DListNode head; // 头节点 private DListNode tail; // 尾节点 private int size; // 添加节点到尾部 public void addAtTail(int val) { DListNode newNode = new DListNode(val); if (tail == null) { head = tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } size++; } }DListNode的构造函数大概图像表示是这样的
[prev|val|next]
↑ ↑ ↑
前驱节点 数据 后继节点
这里的成员变量为什么需要 tail？
- 在双向链表中维护
tail可以在尾部操作时达到 O(1) 时间复杂度 - 不需要遍历整个链表就能访问最后一个节点
双链表优势：
- 可以双向遍历
- 删除节点时不需要知道前驱节点
- 某些操作更高效
2.3 循环链表（Circular Linked List）
循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。
public class CircularLinkedList { class CListNode { int val; CListNode next; CListNode(int val) { this.val = val; } } private CListNode tail; // 指向尾节点，tail.next就是头节点 // 在循环链表中插入节点 public void insert(int val) { CListNode newNode = new CListNode(val); if (tail == null) { // 空链表 tail = newNode; tail.next = tail; // 指向自己形成循环 } else { newNode.next = tail.next; // 新节点指向头节点 tail.next = newNode; // 尾节点指向新节点 tail = newNode; // 更新尾节点 } } }核心区别：
- 普通链表：最后一个节点的
next指向null - 循环链表：最后一个节点的
next指向第一个节点，形成闭环
循环特性：
- 没有真正的"尾"和"头"的概念
- 可以从任意节点开始遍历整个链表
- 遍历时需要特殊终止条件（不能依赖
null）
调用了两次insert方法，一次insert(5)，一次insert(3)
大致图解（本人理解，有错可以和我提出来）
三、链表的CRUD操作详解
3.1 遍历链表
public class LinkedListTraversal { // 基本遍历 public void traverse(ListNode head) { ListNode current = head; while (current != null) { System.out.print(current.val + " -> "); current = current.next; } System.out.println("null"); } // 递归遍历 public void traverseRecursive(ListNode node) { if (node == null) { System.out.println("null"); return; } System.out.print(node.val + " -> "); traverseRecursive(node.next); } // 获取链表长度 public int getLength(ListNode head) { int length = 0; ListNode current = head; while (current != null) { length++; current = current.next; } return length; } }| 特性 | 基本遍历 | 递归遍历 |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(1) | O(n)（调用栈深度） |
| 可读性 | 简单直观 | 更优雅，但需要理解递归 |
| 性能 | 更好（无函数调用开销） | 函数调用有开销 |
| 适用场景 | 大部分情况 | 链表深度有限时 |
| 栈溢出风险 | 无 | 链表过长时可能溢出 |
3.2 插入操作
public class LinkedListInsertion { // 在链表头部插入 public ListNode insertAtHead(ListNode head, int val) { ListNode newNode = new ListNode(val); newNode.next = head; return newNode; // 新的头节点 } // 在链表尾部插入 public ListNode insertAtTail(ListNode head, int val) { ListNode newNode = new ListNode(val); if (head == null) { return newNode; } ListNode current = head; while (current.next != null) { current = current.next; } current.next = newNode; return head; } // 在指定位置插入 public ListNode insertAtPosition(ListNode head, int val, int position) { if (position <= 0) { return insertAtHead(head, val); } ListNode newNode = new ListNode(val); ListNode current = head; int index = 0; // 移动到插入位置的前一个节点 while (current != null && index < position - 1) { current = current.next; index++; } if (current == null) { // 位置超出链表长度，插入到尾部 return insertAtTail(head, val); } newNode.next = current.next; current.next = newNode; return head; } }在头部插入 (insertAtHead)
时间复杂度： O(1)
空间复杂度： O(1)
在尾部插入 (insertAtTail)
时间复杂度： O(n)，需要遍历整个链表
空间复杂度： O(1)
在指定位置插入 (insertAtPosition)
时间复杂度： O(n)，最坏情况需要遍历整个链表
空间复杂度： O(1)
3.3 删除操作
public class LinkedListDeletion { // 删除头节点 public ListNode deleteHead(ListNode head) { if (head == null) return null; return head.next; } // 删除尾节点 public ListNode deleteTail(ListNode head) { if (head == null || head.next == null) return null; ListNode current = head; while (current.next.next != null) { current = current.next; } current.next = null; return head; } // 删除指定值的节点（第一个匹配的） public ListNode deleteNode(ListNode head, int val) { // 处理头节点就是要删除的节点的情况 while (head != null && head.val == val) { head = head.next; } if (head == null) return null; ListNode current = head; while (current.next != null) { if (current.next.val == val) { current.next = current.next.next; // 注意：这里不移动current，因为新的current.next也可能是要删除的 } else { current = current.next; } } return head; } // 删除指定位置的节点 public ListNode deleteAtPosition(ListNode head, int position) { if (head == null || position < 0) return head; if (position == 0) { return head.next; } ListNode current = head; int index = 0; while (current != null && index < position - 1) { current = current.next; index++; } if (current == null || current.next == null) { return head; // 位置无效 } current.next = current.next.next; return head; } }删除头节点 (deleteHead)
时间复杂度： O(1)
空间复杂度： O(1)
删除尾节点 (deleteTail)
时间复杂度： O(n)，需要遍历到倒数第二个节点
空间复杂度： O(1)
为什么检查 current.next.next？
- 需要找到倒数第二个节点
- 检查
current.next会找到最后一个节点，但我们需要修改它前一个节点的引用
删除指定值的节点 (deleteNode)
时间复杂度： O(n)
空间复杂度： O(1)
关键点说明：
- 处理头部连续删除：使用while而不是if，处理连续相同值
- 使用current.next判断：方便修改前驱节点的引用
- 谨慎移动指针：删除后不立即移动，因为新节点也可能要删除
这里还有两个删除操作的核心技巧
哑节点技巧
双指针技巧
然后删除的节点会被GC（垃圾回收器）自动回收，但是小心循环引用
3.4 查找操作
public class LinkedListSearch { // 判断值是否存在 public boolean contains(ListNode head, int val) { ListNode current = head; while (current != null) { if (current.val == val) { return true; } current = current.next; } return false; } // 查找第k个节点 public ListNode findKthNode(ListNode head, int k) { if (head == null || k < 1) return null; ListNode current = head; int count = 1; while (current != null && count < k) { current = current.next; count++; } return current; } // 查找中间节点（快慢指针法） public ListNode findMiddle(ListNode head) { if (head == null) return null; ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } } 判断值是否存在 (contains)
时间复杂度： O(n)
空间复杂度： O(1)
查找第k个节点 (findKthNode)
时间复杂度： O(k)，最坏情况O(n)
空间复杂度： O(1)
查找中间节点 (findMiddle - 快慢指针法)
时间复杂度： O(n)
空间复杂度： O(1)
