线性表（linear list）

顺序表

元素类型相同，在内存里一块连续位置存储，这样的数据结构称为顺序表（sequence list）。

设首元素位置为 \operatorname{Loc}(a_0)，则 a_i 的位置是 \operatorname{Loc}(a_i) = a_0 + ic，其中 c 为单个元素的大小。

操作

插入和删除

为了保证线性表在内存上的连续性，需将插入和删除的后面部分整体后移或前移，最优时间复杂度 O(1)，最差时间复杂度 O(n)，平均时间复杂度 O(n)。

优缺点

优点

• 无需为顺序关系维护额外的关系结构
• 可以随机存取，快速取出第 i 个元素

缺点

• 插入、删除速度慢
• 表的容量固定，扩容困难
• 造成内存碎片化

链表

链表（linked list）可以看作一个一个独立节点构成的数据结构，运用指针记录下一个节点的位置。

链表包含多种变种，经典的链表就是单链表。

头节点

标记链表存在的节点，数据类型与链表的其他节点相同，但是不储存数据。头节点的 next 指向链表的第一个节点。当链表为空时，头节点的 next 为 nullptr。

引入头节点是为了统一插入和删除操作。例如当链表为空时，在链表开头插入节点不需要特判空链表。

优缺点

优点

• 插入、删除为常数复杂度
• 容易扩容

缺点

• 额外存储一个指针，线性表 较低

静态链表

使用数组来存储链表，数组的每个元素包含数据域 data 和“指针”域 next，next 指向下一个元素的下标。

静态链表通常需要维护另一个线性表（可以是链表、栈、队列等，只要能快速插入删除即可）以储存尚未使用（包括删除回收）的节点的下标（这一方法也可以用在堆内存、进程内存的管理上）

基本概念

随机存取和链式存取

随机存取指的是可以在一个结构中直接访问任意第 i 个元素。

顺序表可以随机存取，链表则不能随机存取。

静态和动态存储

顺序表（数组）在存储前需要预先分配内存，属于静态存储；而链表则在运行过程中临时申请新内存，属于动态存储。

存储密度

指的是一个节点中，数据占用的存储量占整个节点存储量的比例。

顺序表的存储密度为 1，链表需要多存一个指针，存储密度小于 1。

间接寻址

在线性表内存储指向元素的指针，称为间接寻址。