链表
链表（Linked List）是最基础的线性数据结构之一——用一组分散在内存各处的节点（node）通过指针（pointer/next）串成一条链，靠「头节点 → next → next → …」逐级跳转访问。与数组「连续内存 + 下标」相反，链表用指针连接换来了已知节点处的 O(1) 增删，代价是失去随机访问（按下标 a[i] 要从头遍历 O(n)）。它分为三种形态：单链表（每个节点一个 next 指针，只能单向走）、双链表（多一个 prev 指针，可双向走）、循环链表（尾节点指回头节点，形成环）。链表是手写数据结构的入门门槛，也是面试高频考点——反转、环检测、找中点、合并、相交，几乎全是**双指针（快慢、间隔）**的套路应用。
链表的全部考点都源于一个物理事实：节点分散 + 指针连接 ⇒ O(1) 增删（已知节点）+ O(n) 访问。由此衍生三大主题：①链表的形态与操作（单/双/循环、虚拟头节点 dummy、哨兵技巧）；②双指针套路（快慢指针判环/找中点、间隔指针找倒数第 k、对齐起点找交点）；③经典算法（反转迭代+递归、合并有序链表、回文判定、LRU 中的双向链表）。其中双指针是链表的灵魂——数组上的双指针是优化技巧，链表上的双指针几乎是唯一武器（因为不能随机访问，只能靠指针配合在 O(n) 内做原本要 O(n²) 的事）。**虚拟头节点（dummy）**则是工程上消除「头节点特殊处理」的通用技巧。
评价
优点
- O(1) 增删（已知节点）：插入/删除只需改前后节点的
next/prev指针，不搬移元素——这是链表区别于数组的核心优势 - 内存按需分配：节点分散存储，无需预先申请大块连续内存，天然支持大小动态变化且无扩容开销
- 头部增删极快：头插头删都是 O(1)，适合做栈、队列（双端操作）的底层结构
- 灵活拼接：两条链表可直接靠指针接上/断开，无需拷贝
缺点
- 不支持随机访问：按下标访问第 i 个元素要从头遍历 O(n)——这是链表最大的硬伤，也因此不能二分查找
- 缓存不友好：节点分散在堆各处，CPU 缓存行命中率极低，顺序遍历比数组慢得多（即使两者大 O 相同）
- 额外内存开销：每个节点要多存 1 个（单链表）或 2 个（双链表）指针，对小元素（如存 int）内存翻倍
- 实现易错：大量指针操作，断链、空指针、边界条件极易写错，调试困难
本叶地图
- 入门 —— 节点与指针模型、单/双/循环链表、O(1) 增删 vs O(n) 访问、与数组对比、内存模型、虚拟头节点/哨兵技巧
- 链表经典算法 —— 反转（迭代+递归）、环检测（Floyd 快慢）、找中点、倒数第 k（双指针间隔）、合并有序链表、相交链表
- 进阶操作 —— 虚拟头节点 dummy、删除倒数第 k、回文链表、随机节点、LRU 双向链表、JS/Java/Python 链表工程实现
- 参考 —— 链表复杂度表、各语言链表对照、双指针套路清单、易错点清单
交互演示
- 链表可视化演示 —— 链表的节点连接与指针操作