链表是什么（节点 + 指针）
链表是一种线性数据结构，由一系列节点组成。每个节点包含两部分：数据和指针（或引用）。指针指向下一个节点，从而将节点串联起来。就像寻宝游戏，每个线索（节点）告诉你下一个线索的位置，而不是把所有线索排成一排。
指针 / 引用怎么理解
指针可以理解为地址或箭头，它指向内存中的某个位置。在链表中，每个节点存储一个指针，指向下一个节点的内存地址。你可以把指针想象成朋友家的门牌号：你拿着这个门牌号就能找到朋友家，而朋友家又放着下一个朋友的门牌号。
插入删除为什么 O(1)，访问为什么 O(n)
在链表中插入或删除节点，只需修改相邻节点的指针，不需要移动其他元素，所以时间复杂度是 O(1)（前提是已经知道插入或删除的位置）。但访问某个位置的元素时，必须从头节点开始，顺着指针一个一个找，平均需要遍历一半的节点，因此是 O(n)。
改指针的顺序为什么关键
修改指针时，顺序错误会导致链表断裂或丢失后续节点。例如在插入节点时，必须先将新节点的指针指向后一个节点，再将前一个节点的指针指向新节点。如果反过来，前一个节点的指针先指向新节点，就会丢失对后一个节点的引用，造成内存泄漏或数据丢失。
数组 vs 链表对照表
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续内存 | 分散内存（通过指针连接） |
| 访问元素 | O(1)（随机访问） | O(n)（顺序访问） |
| 插入/删除（已知位置） | O(n)（需移动元素） | O(1)（改指针） |
| 空间开销 | 小（仅数据） | 大（额外指针） |
| 缓存友好性 | 高（空间局部性） | 低 |
链表的三种类型
- 单向链表：每个节点只有一根
next指针，最常见、最省空间。 - 双向链表：再加一根
prev指向前一个节点，可前后双向遍历；代价是插入、删除要多维护一根指针。Java 的LinkedList、LRU 缓存常用它。 - 循环链表：尾节点的
next指回头节点，首尾相连成环，从任意节点都能遍历一整圈。
链表的典型应用
- 单向链表：实现栈 / 队列；哈希表用「拉链法」解决冲突。
- 双向链表：LRU 缓存、浏览器前进/后退、双端队列等。
- 循环链表：CPU 时间片轮转调度、约瑟夫问题、环形缓冲区。