线性表
线性表是由零个或多个同类型元素组成的有限序列。除首元素外，每个元素有且仅有一个直接前驱；除尾元素外，每个元素有且仅有一个直接后继。成绩列表、待办事项和一行字符都可抽象为线性表。
逻辑结构与存储结构
线性表描述的是元素间的逻辑关系，不限定内存中的摆放方式。顺序表以连续内存保存元素；链表通过节点中的链接关系组织元素，节点可以分散存放。两种实现的操作代价不同，应按主要操作选择。
顺序存储
顺序表将元素连续放入内存。若首元素地址为 Loc(a₁)、每个元素占 d 个存储单元，第 i 个元素地址为 Loc(aᵢ)=Loc(a₁)+(i-1)d。因此可在 O(1) 时间按下标随机访问；但在中间插入或删除时，后续元素必须移动，时间为 O(n)。
链式存储
链表节点保存数据域和后继节点的位置（双向链表还保存前驱）。已知目标节点或其前驱时，插入、删除只需修改链接，为 O(1)；按序号访问必须从头逐个遍历，为 O(n)。节点链接还会带来额外存储开销和较差的缓存局部性。
| 操作 | 顺序表 | 链表 |
|---|---|---|
| 按下标访问 | O(1) | O(n) |
| 已知位置插删 | O(n) | O(1) |
| 存储特点 | 连续、缓存友好 | 节点可分散、含链接开销 |
需要频繁随机访问时通常选择数组或 vector；需要在已知位置频繁局部修改时，链表更合适。
