---
title: "02-线性表"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 02 线性表

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 2 篇，相关系列见 [[00-基础与理论|基础与理论]]。

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

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

```c
#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**

## 二、链表：指针串珠子

### 单链表

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

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

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

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

### 双链表与循环链表

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

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

### 静态链表（一句话懂）

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

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

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

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

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

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

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

## 五、盲点自测

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

## 六、动手玩

```python
# 亲手实现一个带哨兵的单链表，练五大手撕
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-刷题理模型|刷题理模型]]——链表双指针模板题单

⬅️ [[01-绪论与复杂度|绪论与复杂度]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[03-栈与队列|栈与队列]]