第 5 讲 · 线性表与链表

线性表是有限序列 L=(a1,a2,…,an)L=(a_1,a_2,\ldots,a_n)。它规定元素的逻辑次序，却没有规定元素必须怎样存。顺序表和链表是同一逻辑结构的两种实现。

线性表允许哪些操作

常见操作包括初始化、判空、求长度、按位置取值、按值查找、插入、删除、遍历、复制和销毁。选择实现时应先看最频繁的操作，而不是笼统地问哪一种结构“更好”。

顺序表

顺序表用数组保存元素。第 ii 个元素可以 O(1)O(1) 定位；若表有序，还能做 O(log⁡n)O(\log n) 的折半查找。

在第 ii 个位置插入，需要把原来第 ii 到第 nn 个元素依次后移，移动 n−i+1n-i+1 个元素；删除第 ii 个元素，需要把后面的 n−in-i 个元素前移。等概率位置下，平均都要移动约一半元素，因此是 O(n)O(n)。

移动方向很关键：插入时从后向前搬，避免覆盖尚未保存的元素；删除时从前向后搬。

单链表

单链表结点保存数据和后继指针：

typedef struct Node {
    int data;
    struct Node *next;
} Node;

头指针指向第一个结点；空表常用 NULL 表示。若引入不保存实际元素的头结点，很多首结点操作可以统一为普通结点操作。

遍历

for (Node *p = head; p != NULL; p = p->next) {
    /* 访问 p->data */
}

循环不变量是：p 始终指向当前尚未处理的结点，p == NULL 表示链已走完。

在 p 后插入 q

q->next = p->next;
p->next = q;

第一句先让新结点接住原来的后半条链；第二句再让 p 指向新结点。顺序反过来会丢失原后继地址。

删除 p 后的结点

Node *q = p->next;
if (q != NULL) {
    p->next = q->next;
    free(q);
}

必须先保存被删结点，接好剩余链后再释放。

建表方式影响次序

  • 头插法每次把新结点放在最前面，最终次序与输入相反；
  • 尾插法维护尾指针，把新结点接到末尾，最终次序与输入相同。

尾插时空表需要同时更新头、尾；非空表更新原尾结点的 next，再移动尾指针。

有序链表合并

合并两条递增链表时，始终比较两条未处理链的首元素，把较小者接到结果尾部。循环不变量是：结果链已经有序，并且恰好包含两条输入链中已经取走的元素。

每个结点最多访问一次，时间 O(m+n)O(m+n)，若复用原结点，额外空间 O(1)O(1)。

循环链表

普通单链表与尾结点回指表头的循环链表

循环单链表最后一个结点不指向 NULL，而指回首结点。它适合需要循环访问的问题，例如约瑟夫环。

遍历时不能再用 p != NULL 作为终止条件，而应保存起点，在回到起点时停止。空表、单结点自环尤其容易漏判。

双向链表

双向结点同时保存前驱和后继。已知结点时可向两个方向移动，删除当前结点也不必另找前驱，但插入或删除时要维护四条相关链接。

在结点 q 前插入 p：

p->prev = q->prev;
p->next = q;
q->prev->next = p;
q->prev = p;

应先把 p 的两条链接接好，再让原邻居改指向 p。

怎样选择

需求顺序表链表
按序号随机访问O(1)O(1)O(n)O(n)
已知位置后插入、删除通常 O(n)O(n)O(1)O(1)
存储开销无指针域每结点有链接开销
内存布局连续可分散
容量变化需扩容或预留按需申请

链表所谓“插入删除快”有一个前提：位置已经找到。若先按值查找结点，整体仍可能是 O(n)O(n)。

评论