数据结构与算法 / 系统课时
单向链表
单向链表
单向链表用节点之间的 next 引用连接数据,不要求元素在内存中连续存放。本课将实现遍历、查找、头部插入和按值删除,并重点理解删除节点时为什么必须修改前驱节点的链接。
学习目标
- 理解头节点、数据域和
next引用组成的链式结构。 - 实现单向链表的遍历、查找、头部插入与节点删除。
- 分析不同操作的边界条件及时间、空间复杂度。
知识导图
单向链表
├── 节点
│ ├── value:保存数据
│ └── next:指向后继节点
├── head
│ └── 指向第一个节点
├── 基本操作
│ ├── 头部插入
│ ├── 顺序遍历
│ ├── 按值查找
│ └── 按值删除
└── 边界
├── 空链表
├── 删除头节点
└── 目标不存在问题背景或应用场景
动态数组依赖连续存储,扩容时需要复制元素,在中间插入或删除时还要搬移后续数据。链表把每个元素封装为独立节点,通过引用建立顺序,因此局部修改不需要搬移其他元素。删除非头节点时要拿到指向它的前驱链接,仅知道目标节点引用通常仍需从头查找前驱。
这种结构适合频繁修改连接关系、元素数量变化明显且不强调随机访问的场景。它也为后续学习栈、队列、哈希桶和图的邻接表提供基础。代价是无法通过下标直接定位元素,查找通常必须从头节点开始逐个访问。
核心原理
单向链表由一个 head 引用和若干 Node 节点组成。每个节点保存当前值与后继引用,最后一个节点的 next 为 null。空链表的 head 也是 null。

头部插入只需执行两个链接动作:新节点的 next 指向原 head,然后让 head 指向新节点。无论链表有多少元素,这两步都固定,因此时间复杂度为 。若先保存原 head,也可随后更新引用。关键是覆盖之前保留原入口,避免把新节点的 next 指向它自己。
查找需要从 head 开始,沿 next 逐个比较,直到找到目标或走到 null。最坏情况下访问全部 个节点,因此时间复杂度为 。
删除按值匹配的第一个节点时有两个分支。若目标位于头部,直接执行 head = head.next;否则必须保留前驱节点 current,找到满足 current.next.value == target 的位置后执行 current.next = current.next.next。链接修改本身是 ,但定位目标仍是 。
| 操作 | 时间复杂度 | 关键条件 |
|---|---|---|
| 头部插入 | 先连接旧头节点,再更新 head |
|
| 遍历 | 每个节点访问一次 | |
| 按值查找 | 最坏遍历完整链表 | |
| 按值删除首个匹配节点 | 定位前驱后修改一条引用 |
这里保存 n 个节点和 n 个后继槽位,总空间为 Θ(n)。每节点通常有额外的对象和引用成本,具体字节数由运行时决定。查找和删除只需常数额外状态,toString 还要构建返回字符串。
基础用法
遍历链表时使用临时变量 current,不要直接移动 head。循环条件通常是 current != null,每轮先处理当前节点,再令 current = current.next。
删除操作需要先处理空链表和头节点两个边界。进入普通循环后,检查的是 current.next,因为真正要修改的是前驱节点保存的引用;循环条件必须保证 current.next != null,避免访问空引用。
完整可运行示例
将以下代码保存为 SinglyLinkedListDemo.java。示例使用 Java 17,可直接编译运行。
public class SinglyLinkedListDemo {
static class SinglyLinkedList {
private static class Node {
private final int value;
private Node next;
private Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
private Node head;
private int size;
void addFirst(int value) {
head = new Node(value, head);
size++;
}
boolean contains(int target) {
Node current = head;
while (current != null) {
if (current.value == target) {
return true;
}
current = current.next;
}
return false;
}
boolean removeFirstOccurrence(int target) {
if (head == null) {
return false;
}
if (head.value == target) {
head = head.next;
size--;
return true;
}
Node current = head;
while (current.next != null) {
if (current.next.value == target) {
current.next = current.next.next;
size--;
return true;
}
current = current.next;
}
return false;
}
int size() {
return size;
}
@Override
public String toString() {
StringBuilder result = new StringBuilder("[");
Node current = head;
while (current != null) {
result.append(current.value);
current = current.next;
if (current != null) {
result.append(", ");
}
}
return result.append("]").toString();
}
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.addFirst(30);
list.addFirst(20);
list.addFirst(10);
System.out.println("初始链表: " + list);
System.out.println("包含 20: " + list.contains(20));
System.out.println("包含 99: " + list.contains(99));
System.out.println("删除 20: " + list.removeFirstOccurrence(20));
System.out.println("删除后: " + list);
System.out.println("删除头节点 10: " + list.removeFirstOccurrence(10));
System.out.println("当前链表: " + list);
System.out.println("删除不存在的 99: " + list.removeFirstOccurrence(99));
System.out.println("size = " + list.size());
}
}运行命令如下。
javac -encoding UTF-8 SinglyLinkedListDemo.java
java SinglyLinkedListDemo预期输出
初始链表: [10, 20, 30]
包含 20: true
包含 99: false
删除 20: true
删除后: [10, 30]
删除头节点 10: true
当前链表: [30]
删除不存在的 99: false
size = 1三次 addFirst 会让后插入的元素位于更靠前的位置,因此最终顺序是 10、20、30。删除 20 时修改节点 10 的 next,删除 10 时直接更新 head,删除不存在的 99 不改变链表和 size。每次成功修改后,从 head 沿 next 应恰好访问 size 个节点并到达 null,且不能重复访问同一节点。重复值与重复节点身份要分开核对。
Tips
- 画出节点和箭头再调试删除逻辑,重点标记当前节点、前驱节点和目标节点。
- 遍历时只移动局部变量
current,避免意外丢失head。 - 修改链接和更新
size应在同一成功分支内完成,查找失败时不能改变长度。 - 单向链表无法从当前节点直接回到前驱节点;需要反向移动时,应考虑双向链表或额外保存前驱引用。
常见错误
1. 头部插入时丢失原链表
如果先让 head 指向新节点,再尝试从新 head 获取旧头节点,原入口已经不可达。正确做法是构造节点时把原 head 作为 next,随后一次性更新 head。
2. 删除时只移动局部变量
把 current 直接改为 current.next 只会改变临时引用,不会修改链表结构。真正删除中间节点必须更新前驱节点的 next,使它跳过目标节点并指向目标的后继。
3. 忽略删除头节点
普通删除循环依赖前驱节点,但头节点没有前驱。若不单独处理 head.value == target,目标位于首节点时就无法删除,或者会触发空引用错误。
4. 使用 current.next.value 前未检查空引用
当 current 位于尾节点时,current.next 为 null。循环条件应先保证 current.next != null,再读取后继节点的字段。
本课练习
- 增加
addLast(value)方法。空链表时更新head,非空链表时找到尾节点并连接新节点;验收时连续追加 10、20、30,输出顺序必须保持一致。 - 增加
removeAll(target)方法,删除所有匹配节点并返回删除数量。要求正确处理连续多个头节点都匹配、链表中间连续匹配以及目标不存在三种情况。 - 实现
get(index),下标从 0 开始。要求非法下标抛出IndexOutOfBoundsException,并分析该方法为什么不能达到动态数组的 随机访问性能。
本课总结
- 单向链表通过节点的
next引用维持顺序,数据不需要连续存储。 - 头部插入是 ,遍历、查找和按值删除通常是 。
- 删除头节点与删除中间节点的链接方式不同,边界处理决定实现是否可靠。
下一课预告
下一课先增加前驱和尾引用,说明双向链表怎样支持从两端定位。随后再学习栈与队列。