02 线性表

📚 本文是数据结构的第 2 篇，相关系列见基础与理论。

线性表 = n 个元素的有限序列（一对一关系，有头有尾、有前驱后继）。它是栈、队列、串的爹——把线性表"限制得严格一点"就成了后面那些结构。本章核心是一次彻底的对比：顺序表 vs 链表，几乎所有考题都在考"什么时候选谁"。

一、顺序表：一段连续内存

#define MAXSIZE 50
typedef struct {
    int data[MAXSIZE];   // 静态分配
    int length;
} SqList;

要点：

按位序访问 O(1)：a[i] = 首地址 + i × 元素大小——这是连续内存送的礼物
插入/删除 O(n)：动一个位置，后面全要挪
存储密度 = 1（只存数据，无指针开销）
静态分配（数组，满即亡）vs 动态分配（malloc 数组，可再扩容——扩容是"搬家"，单次 O(n)）

手算插入/删除移动次数（408 必考）：

在第 i 个位置（1 ≤ i ≤ n+1）插入 → 需要移动 n − i + 1 个元素；等概率下平均 (n+1 处选点) = n/2
删除第 i 个元素（1 ≤ i ≤ n）→ 移动 n − i 个；平均 (n−1)/2

二、链表：指针串珠子

单链表

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

访问 O(n)（从头走），插入/删除 O(1)——但前提是已经站在那个位置（找到位置本身 O(n)）
两个经典技巧：头结点（第一个不存数据的哨兵，让"插在表头"和"插在中间"代码统一）、前驱指针 p、q 双指针（ q 走在前，p 跟在后面）

单链表五大必会手撕（面试与上机）

头插法建表（逆序）、尾插法建表（正序）
按序号/按值查找
插入：s->next = p->next; p->next = s;（顺序不能反——先接后断）
删除：p->next = p->next->next;（先留好后继再断）
双指针套路：找倒数第 k（快慢指针）、判环（快慢指针相遇）、找中点

双链表与循环链表

变体	结构	解决什么
双链表	`prior` + `data` + `next`	单链表不能 O(1) 找前驱的痛点
循环单链表	尾结点 next 指回头结点	从任意结点出发走全表；O(1) 找到表尾后可 O(1) 在头尾插（带尾指针时）
循环双链表	双向 + 成环	最灵活；判空不是 `head<mark>NULL` 而是 `head->next</mark>head`

⚠️ 循环链表判空/判尾别用单链表的老习惯：单链表判 p != NULL，循环链表判 p != head。

静态链表（一句话懂）

不使用指针，用数组下标当"指针"：data[] + next[] 两个数组，next 存下一个元素的数组下标。给不支持指针的语言（早期 Fortran）或需要序列化到文件/磁盘的场景用。408 只考概念。

三、顺序 vs 链式：一张表定生死

维度	顺序表	链表
访问第 i 个	O(1)	O(n)
插入/删除（已知位置）	O(n) 挪元素	O(1) 改指针
空间	预分配（可能浪费/溢出），存储密度 1	按需分配，密度 < 1（指针开销）
内存连续性	连续	分散
缓存友好性	极好（顺序访问命中 Cache 的空间局部性）	差（结点跳跃，每次可能 Cache miss）

💡 缓存友好性是真实世界的隐藏权重：理论复杂度说链表插入 O(1) 优于顺序表 O(n)，但现代 CPU 上顺序表依靠 Cache 预取，遍历常常快一个数量级——这就是为什么工程上 std::vector 几乎总是赢过 std::list。王道/408 不考这个，但面试聊性能一定用到，而且它直接连回 03-存储系统的局部性原理。

选型口诀：查多改少选顺序，插删频繁选链式；查"多"到极端就是有序顺序表 → 直接上折半查找（查找）。

四、线性表的应用与衍生物

多项式表示：稀疏多项式用链表（只存非零项）；稠密用顺序数组（下标即幂次）——经典应用题
有序表合并：双指针 O(m+n)（顺序表直接归并；链表用"断链重组"可 O(1) 空间）
逆置：顺序表双指针交换；链表头插法重建——上机必练
栈/队列/串：见 03-栈与队列、04-串与KMP

五、盲点自测

顺序表按位访问为什么 O(1)？（首地址 + i×元素长度，地址公式直接算）
第 i 位插入移动几个元素？平均多少？（n−i+1；n/2）
单链表插入的两步指针操作顺序反了会怎样？（后继丢失，断链）
循环双链表判空？（head->next == head）
静态链表的"指针"是什么？（数组下标）
为什么工程里 vector 常常碾压 list？（缓存友好性——顺序内存吃局部性红利）
带尾指针的循环单链表，在表头/表尾插入各多少时间？（都 O(1)：尾指针->next 即头）

六、动手玩

# 亲手实现一个带哨兵的单链表，练五大手撕
class Node:
    def __init__(self, data=None):
        self.data, self.next = data, None

class LinkedList:                      # head 是哨兵
    def __init__(self):
        self.head = Node()

    def insert_after(self, p, data):   # p 后插
        s = Node(data)
        s.next, p.next = p.next, s

    def to_list(self):                 # 遍历（头结点后开始）
        out, p = [], self.head.next
        while p:
            out.append(p.data)
            p = p.next
        return out

ll = LinkedList()
p = ll.head
for x in (1, 2, 3):                    # 尾插法
    ll.insert_after(p, x); p = p.next
print(ll.to_list())                    # [1, 2, 3]

# 快慢指针找中点（偶数个取后半第一个）
slow = fast = ll.head
while fast and fast.next:
    slow, fast = slow.next, fast.next.next
print(slow.data)                       # 2

参考资料

王道《数据结构考研复习指导》第 2 章
CSAPP 深化：顺序访问与 Cache（第 5、6 章）——解释"缓存友好性"的理论根源
刷题理模型——链表双指针模板题单

⬅️ 绪论与复杂度 🏠 00-基础与理论 ➡️ 栈与队列

02-线性表