Sherfiter's wiki for fun

第 2 章 · 线性表

面试里有道经典题:「数组和链表都是线性表,什么时候用谁?」很多人背得出「数组随机访问快、链表插入删除快」,再追问一句「真的吗?数组的中间插入不是也要 O(n) 吗?链表插入之前不是也要 O(n) 找位置吗?」就开始含糊了。这章不背结论,把两种实现放同一台机器上跑分,你会发现真实差距比教材的表格更夸张,而且胜负手经常和理论预期不一样(剧透:链表输得比理论更惨,原因在第 12 章的内存视角,但这里先埋个线头)。

2.1 顺序表:数组的正经用法

顺序表就是「一段连续内存 + 长度计数」,是数组的工程化封装:

typedef struct {
    int *data;   // 指向堆上的连续块
    int len;     // 当前元素数
    int cap;     // 容量
} SeqList;

随机访问 data[i] 一步到位(地址 = 首地址 + i × 元素大小,纯算术);插入删除要整体搬家。看中间插入的真实动作:

void insert_at(SeqList *L, int i, int v) {
    if (i < 0 || i > L->len || L->len == L->cap) return;
    for (int k = L->len; k > i; k--)    // 从尾往前,整体后移一位
        L->data[k] = L->data[k - 1];
    L->data[i] = v;
    L->len++;
}

平均要搬一半元素,O(n)。但注意两个不搬的特例:尾插 O(1)(在末尾直接放,容量满了才扩容,第 1 章的摊还分析算过,均摊还是 O(1))和头删要搬全部。这两个特例解释了大量工程习惯:用数组时尽量「往尾部追加」,遍历删除时「倒着删」避免边删边搬。

2.2 链表:指针串成的表

链表把元素拆成散落在堆上的节点,靠指针连:

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

Node *push_front(Node *head, int v) {   // 头插,O(1)
    Node *n = malloc(sizeof *n);
    n->val = v;
    n->next = head;                     // 新节点接管旧头
    return n;                           // 新头
}

头插 O(1)、删除已知前驱时 O(1),理论上「频繁增删」是它的主场。变体三兄弟:单链表(只有 next,删节点要先把前驱找到)、双向链表(加 prev,删除已知节点 O(1),代价每节点多 8 字节)、循环链表(tail 接回头,约瑟夫环这类「转圈」问题天然适配)。画内存图是理解链表的最好方式,第 12 章会专门画到缓存行级别,这里先看逻辑图:

head → [3|•] → [7|•] → [1|•] → [9|∅]

2.3 跑分:理论表之外的真相

把复杂度表先摆出来(它没错,只是不够):

操作顺序表链表
按下标访问O(1)O(n)
尾插(摊还)O(1)O(n)(无尾指针)/ O(1)(有)
中间插入(已知位置)O(n) 搬一半O(1) 改指针
按值查找O(n)O(n)
额外空间预留浪费每节点多一个指针

然后是同一台机器实测「往一百万个元素的表里顺序插入一百万次」(顺序表用动态数组,链表用 2.2 的实现):

顺序表:   8 ms     (memcpy 式搬家,极快)
链表:   850 ms     (一百万次 malloc,散落堆上)

理论只差「常数」,实测差了百倍。原因:顺序表搬家是 memcpy(连续内存,一次拷一大块,第 12 章讲缓存行时会细说为什么快);链表每次 malloc 要找堆、每次访问节点都可能 cache miss(第 7 章的局部性原理)。这组数字带来一条工程铁律:现代硬件上,顺序表是默认选择,链表只在你真的需要 O(1) 头插、或节点必须在内存里搬动/重连的场景出现(比如 LRU 缓存、内存池的空闲链)。

2.4 经典手感题:快慢指针

链表的操作代码短,但边界条件多(空表、单节点、删头),所以它的「手感」全靠几个经典题练。最值得吃透的是快慢指针:

找中点:两个指针从头出发,快的一次走两步,慢的一次一步,快指针到头时慢指针正好在中点(O(n) 时间、O(1) 空间)。

判环:快慢指针同速追,链表有环,两者必在环内相遇(相对速度 1,迟早套圈);无环,快指针先到 NULL。这就是 Floyd 判圈,操作系统课讲过它还能找内存泄漏的引用环。

int has_cycle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

删第 n 个节点:标准做法是「虚头(dummy)节点」:临时造一个假头指向真头,删除逻辑统一处理(不用特判删的是不是头节点),结束返回 dummy->next。多一个节点,少一半 if,这是链表代码里最划算的一笔交易。

常见错误

  • malloc 完不检查就解引用。堆满时 malloc 返回 NULL,直接 n->val = v 就是空指针解引用(C 指针课第 9 章的坑)。
  • 改指针传一级指针。void push(Node *head, int v) 改的是副本,真头永远不变;要改调用者的 head,传 Node **。C 指针课第 10 章的二重指针就是为这类场景准备的。
  • free 后继续用 next。遍历删除时先存 next 再 free 当前节点,顺序反了 free 完读 p->next 就是 use-after-free。

练习

  1. 实现:双向链表的 delete_node(Node *n),要求 O(1)(利用 prev 直接摘除),并与单链表版本对比代码量。
  2. 手算:Floyd 判圈,若环外长 a、环长 b,快慢指针相遇时快指针走了几步?由此推出「找环入口」的第二次相遇算法。
  3. 动手:复现 2.3 的跑分(链表插一百万),再把链表改成「每次 malloc 16 个节点的块」的简易内存池,看看能快多少。体会局部性对链表的杀伤力。
  4. 思考:操作系统内核里到处是链表(Linux 的 task_struct 挂在多条链上),为什么内核不用数组?提示:想想「进程数不可预知」和「节点要在多条全局链上同时出现」两个需求,顺序表哪个做不到?
豫ICP备2026027944号