第 2 章 · 线性表

线性表 = 一串同类型元素，有「前驱/后继」关系；两种底层：顺序表（连续内存）、链表（指针串联）。

2.1 顺序表：数组的封装

顺序表 = 一段连续内存 + 一个记录长度的变量。随机访问 O(1)，但插入/删除要搬元素。

typedef struct {
    int *data;   // 堆上分配的连续块
    int len;
    int cap;
} SeqList;

// 下标 i 处插入 v：i..len-1 整体后移一位
void insert(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++;
}

2.2 链表：指针串联

每个节点存值 + 指向下一节点的指针。节点离散分布在堆上，靠 next 连成链。

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

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

// 尾插 O(n)：必须先走到链尾（若维护 tail 指针则 O(1)）
void push_back(Node **head, int v) {
    Node *n = malloc(sizeof(*n));
    if (!n) return;
    n->val = v; n->next = NULL;
    if (!*head) { *head = n; return; }
    Node *p = *head;
    while (p->next) p = p->next;
    p->next = n;
}

2.3 单链表 / 双向 / 循环

变体	节点指针	特点
单链表	一个 next	只能向后走，删前驱要另找
双向链表	prev + next	可前可后，删除 O(1)，多一个指针开销
循环链表	尾指向头	从任意点遍历全表，用于约瑟夫环等

双向链表删除已知节点是 O(1)，因为能直接拿到前驱；单链表删除已知节点仍需先找到它的前驱，是 O(n)。（见第 12 章的指针串联图）

2.4 增删查改复杂度一览

操作	顺序表	单链表
按下标访问	O(1)	O(n)
头插/头删	O(n)	O(1)
尾插/尾删	O(1)（摊销）	O(n)（无尾指针）
中间插入	O(n)	O(n)（先定位）
查找	O(n)	O(n)

对比：顺序表 vs 链表——

维度	顺序表	链表
内存	连续一块，缓存友好	节点离散，每节点多 8 字节指针
随机访问	O(1)，按下标	O(n)，只能顺指针走
插入/删除	O(n)，搬元素	O(1)（已知位置）
空间	可能预留 cap 浪费	按需分配，但指针有开销
扩容	需重新 malloc + 拷贝	无此问题

取舍一句话：频繁随机访问选顺序表，频繁头尾增删选链表。

2.5 与内存模型的关系

顺序表 = 一段连续内存；链表 = malloc 分散节点用指针连起（见 C 指针第 2、9 章）。