链表基础：单链表与双链表的操作
侧重：链表的内存模型、单/双链表增删查改操作、时间复杂度分析、指针操作技巧
核心原理：链表的内存模型
1. 链表 vs 数组
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分布 | 连续内存空间 | 分散的内存块 |
| 访问方式 | O(1) 随机访问（索引计算） | O(N) 顺序访问（遍历指针） |
| 扩容 | 需重新分配 + 复制（O(N)） | 无需扩容，随时添加节点 |
| 内存效率 | 可能浪费连续空间 | 高效利用零散内存 |
链表的本质：元素可以分散在内存的任何位置，通过每个节点上的 next/prev 指针串联起来。
2. 单链表 vs 双链表
单链表节点：
class ListNode {
int val;
ListNode next; // 只有后继指针
}
双链表节点：
class Node<E> {
E val;
Node<E> next; // 后继指针
Node<E> prev; // 前驱指针
}
| 特性 | 单链表 | 双链表 |
|---|---|---|
| 指针数量 | 1个（next） | 2个（prev + next） |
| 遍历方向 | 单向（只能向后） | 双向（可前可后） |
| 操作复杂度 | 较简单 | 稍复杂（需维护两个指针） |
| 删除尾节点 | O(N)（需找前驱） | O(1)（有直接前驱指针） |
基本操作与时间复杂度
单链表操作
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查/改（给定索引） | O(N) | 必须从头遍历 |
| 头部插入 | O(1) | 新节点指向原头结点，更新头指针 |
| 尾部插入 | O(N) | 需遍历到尾部 |
| 中间插入 | O(N) | 需先找到前驱节点 |
| 头部删除 | O(1) | 直接移动头指针 |
| 尾部删除 | O(N) | 需找到倒数第二个节点 |
| 中间删除 | O(N) | 需先找到前驱节点 |
关键操作示例（中间插入）：
// 在第3个节点后插入新节点66
ListNode p = head;
for (int i = 0; i < 2; i++) {
p = p.next; // p指向第3个节点（前驱）
}
ListNode newNode = new ListNode(66);
newNode.next = p.next; // 新节点指向原第4个节点
p.next = newNode; // 前驱节点指向新节点
双链表操作
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查/改（给定索引） | O(N) | 可从头或尾开始遍历 |
| 头部插入 | O(1) | 新节点成为头，维护prev/next |
| 尾部插入 | O(N)* | 若持有尾引用则为O(1) |
| 中间插入 | O(N) | 需先找到插入位置 |
| 头部删除 | O(1) | 更新头指针，清理旧头结点 |
| 尾部删除 | O(N)* | 若持有尾引用则为O(1) |
| 中间删除 | O(N) | 若已知节点引用则为O(1) |
关键操作示例（删除节点）：
// 删除第4个节点（已知前驱节点p）
DoublyListNode toDelete = p.next;
p.next = toDelete.next; // 前驱跳过待删除节点
toDelete.next.prev = p; // 后继的前驱指回前驱
toDelete.next = null; // 清理指针（好习惯）
toDelete.prev = null;
虚拟头结点技巧
文章提到将在下一篇中使用**虚拟头结点（Dummy Head）**技巧：
- 统一头部、尾部、中间的操作逻辑
- 避免处理头尾指针为空的边界情况
- 是链表算法的常见技巧
相关实体
- labuladong：算法学习平台作者
原理总结
链表的核心在于分散内存 + 指针连接，通过牺牲随机访问能力（O(N)）换取高效的内存利用和灵活的增删操作。双链表通过额外维护前驱指针，支持双向遍历，但操作稍复杂。掌握指针操作是理解链表的关键。