链表

数组通过连续地址与地址算术快速跳到任意位置，链表则把序列的相邻关系、“下一个在哪里”显式存成指针。已知节点位置时，插入或删除只改常数个链接；代价是不能通过下标直接跳到第 $i$ 个元素，遍历还具有较差的缓存局部性。抽象接口中的“位置”若只是索引，寻找该位置仍需线性时间，不能把查找成本藏起来。

在已知节点 $x$ 后插入 $y$，只需令 $y.next=x.next$、$x.next=y$。若只给键值而未给节点位置，仍需线性搜索，所以“链表删除 $O(1)$”有前提。单链表删除当前节点通常还需前驱，除非可采用复制后继等特定技巧且语义允许。链表每节点有指针开销，局部性差，实际遍历常慢于数组；循环链表还需防止无限遍历。

双链表可常数时间删除已知节点，但多一个反向指针并需维护双向一致性。空表、尾指针、循环链表和迭代中删除都会改变边界不变式；悬空指针与所有权问题属于实现正确性的核心。

链表常实现栈、队列、双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。、LRU 链和邻接表；B+ 树公理库B+ 树B+ tree · B-plus tree将全部记录保存在等深叶层、以内部路由键和叶链同时支持单键与范围访问的多路搜索树。还用叶链支持范围扫描。不可变链表可通过共享尾部构造持久版本公理库持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。。与数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。相比，它以随机访问和局部性换取稳定节点地址及局部结构修改，具体 ADT 的操作次序仍应由接口而非指针布局规定。

跳表公理库跳表skip list用独立几何高度建立多层稀疏链表，以期望对数时间支持有序字典操作。在底层全量链表之上随机建立稀疏快车道，以期望对数搜索换额外指针；Move-to-Front公理库List Update 与 Move-to-Frontlist update problem · move-to-front · MTF在经典列表访问模型中把被访问项免费移到表头，并用两份排列之间的逆序数证明 2-竞争性。按访问重排链表，用竞争分析而非最坏查找界评价。两者都不是普通链表常数插删性质的直接推论。指针机模型公理库指针机模型Pointer machine model · 指针机器只允许从已持有记录沿显式指针导航、修改常数字段并比较原子键，而不允许把地址当整数计算的数据结构模型。只允许沿指针导航，不能把数组下标或 Word-RAM 位操作默认为常数，这正是链式结构下界与设计的模型边界。