链表

把相邻关系放进节点 ​

数组理路数组Array以连续整数下标支持随机访问的有限序列结构。通过连续位置与下标定位元素；链表把“下一个元素在哪里”直接存进节点。节点可以分散在内存中，只要链接保持正确，遍历就能按顺序到达它们。

因此，链表是一种实现线性序列理路序列Sequence以自然数为定义域的函数。的存储结构。抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。规定外部能执行哪些操作，链表规定内部怎样保存元素。栈和队列都可以用链表实现，但它们不同的出入顺序来自接口契约，而不是来自“使用了指针”这个事实。[1]

局部改接为什么能做到常数时间 ​

已知节点 p，要在它后面插入一个尚未加入链表的新节点 x，只需

x.next = p.next
p.next = x

先让新节点接住原来的后继，再让前驱指向新节点。顺序反过来且不保存旧后继，就可能把原链条丢掉，甚至让 x.next 指向自己。若 p 原来是尾节点，还要令 tail = x。[1]

插入前：p ─────────→ q
插入后：p → x → q

删除也要说明手里有什么。若已知待删节点的前驱 p，令 p.next = p.next.next 即可跳过目标；删尾节点还需把 tail 改为 p。若仅拿到单链表中待删节点自身，一般仍需找到前驱，尤其删除尾节点时不能凭这一个引用完成常数时间改接。

“把后继的值复制到当前节点，再删除后继”只能处理部分情况，也改变了被保留节点与值的对应关系；它不适用于尾节点，且在外部持有节点引用时可能违反原本的删除语义。不能用这个技巧无条件证明单链表删除已知节点为 $O(1)$。

不同操作的成本放在一起看 ​

下表假定引用访问和一次元素操作为 $O(1)$；链表维护必要的首尾指针。分配与回收器的额外成本另计。

双向链表为每个节点增加 prev。删除已知节点时，其前驱和后继都能直接找到，于是只需让两边互相跨过该节点；表头、表尾仍需要相应处理。

这张表解释了为什么“链表适合频繁插删”必须补上条件：操作已经定位到节点，而且查找不是主要成本。若每次都先按下标找到中间位置，再插入一项，整个操作仍然是线性的。

哨兵、遍历与内存布局 ​

哨兵是一个不承载普通元素的辅助节点，可以让“在表头前插入”等边界操作采用统一的链接规则。循环双向链表常用一个哨兵把首尾连起来，但此时停止条件应是“回到哨兵”，不能继续沿用“遇到空指针停止”。结构变化必须和遍历不变式一起说明。

修改链表时，还要保住后续遍历所需的引用。例如删除当前节点后再读取它的 next，在需要显式回收内存的实现中可能已不合法；顺序执行中先保存后继，再断链和回收，才保留了继续遍历的信息。

并发访问还要分开结构更新与生命周期。Harris非阻塞有序链表理路Harris 无锁有序链表Harris linked list · Harris non-blocking list用不可逆next标记分离逻辑删除与物理摘链，让插入、删除和帮助搜索共享可验证的CAS条件。先在待删节点的next字上标记，再让前驱跨过它，避免与插入竞争时丢掉新节点；Hazard Pointer理路Hazard Pointer 安全回收Hazard pointer · Hazard pointers · 危险指针回收先发布并验证节点保护，再按hazard扫描释放退休节点，关闭裸指针获取与回收之间的竞态。另行判断哪些已摘除节点仍被读者保护。只保存一个后继引用，并不能保证其他线程不会先释放后继。

链表可以避免搬动未删除的节点，但“节点地址稳定”依赖分配、移动与生命周期策略。每个节点也有额外链接与分配开销；逐指针跳转通常不如连续数组容易利用缓存。具体速度需要结合布局和访问模式比较，不能从 $O(1)$ 插入直接推导出整体程序更快。[1][2]

哪些接口能从这些链接获益 ​

在表头插入、删除就能实现栈理路栈Stack · LIFO stack以栈顶为唯一更新端、按后进先出规则组织元素的抽象数据类型；接口语义与具体表示的成本分别规定。。保存首尾指针，尾部加入、头部取出就能实现队列理路队列Queue · FIFO queue在队尾加入、从队首取出，并保持尚未离队元素的到达次序的抽象数据类型；循环数组和链表给出不同表示。。双向链表还适合在已知节点上调整位置，例如哈希表提供定位、链表维护最近使用顺序的 LRU 结构：快速查找来自哈希表，快速重排才来自链表。

不可变单链表可让多个版本共享尾部，从而构造持久数据结构理路持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。。跳表理路跳表skip list用独立几何高度建立多层稀疏链表，以期望对数时间支持有序字典操作。则额外建立稀疏的前进链接来加速搜索；其期望对数查找来自多层结构与随机化，而不是普通链表本身。把这些机制分开，才能判断一次优化实际消除了哪一项成本。