单链表
入门链表把"相邻关系"存进指针里，而不是连续内存里。
// 算法讲解
单链表
这组示例会演示遍历、插入以及单向改链删除。
待机
速度 中
待机 ⌨1struct Node {
2 int value;
3 Node* next;
4 Node(int v) : value(v), next(nullptr) {}
5};
6
7Node* find(Node* head, int target) {
8 for (Node* cur = head; cur != nullptr; cur = cur->next) {
9 if (cur->value == target) return cur;
10 }
11 return nullptr;
12}
13
14void insertAfter(Node* prev, int value) {
15 if (prev == nullptr) return;
16 Node* node = new Node(value);
17 node->next = prev->next;
18 prev->next = node;
19}
20
21void removeAfter(Node* prev) {
22 if (prev == nullptr || prev->next == nullptr) return;
23 prev->next = prev->next->next;
24}
复杂度分析
时间 访问 O(n) / 头插 O(1)
空间 O(n)
最优 头部操作 O(1)
最坏 按位访问 O(n)
算法讲解
单链表由一串节点组成，每个节点保存当前值以及指向下一个节点的指针，因此节点在内存里不要求连续。
它非常适合练习插入、删除时如何只改局部连接关系；代价是无法像数组那样 O(1) 随机访问第 k 个元素。
教学时最值得盯住三件事：头节点是否变化、前驱节点是谁、断链和接链的顺序是否安全。
很多更复杂的数据结构，本质上都建立在"节点 + 指针关系"的思维上。