顺序表与链表详解：线性表的两种存储方案

线性表描述“一对一”的前后关系，顺序表和链表则是它的两种典型存储方案：前者把元素连续地放进数组，后者用指针把分散的节点串起来。二者没有绝对优劣，真正的选择依据是访问模式、插入删除位置、内存开销和缓存局部性。

1. 线性表

线性表是由 $n$ 个具有相同性质的数据元素组成的有限序列。除首元素和尾元素外，每个元素有且仅有一个直接前驱和一个直接后继。

线性表是逻辑结构，而顺序表、链表是存储实现。栈、队列和字符串也都可以看作受到额外操作约束的线性表。

2. 顺序表

顺序表使用一段连续内存依次保存元素。它可以分为：

  • 静态顺序表：内部使用定长数组，容量在编译期或初始化时固定；
  • 动态顺序表：容量不足时重新分配更大空间，类似 C++ 的 std::vector。

一个动态顺序表需要维护三个状态：数据地址、有效元素数和容量。

1
2
3
4
5
typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} SeqList;

它的核心不变量是：

1
2
3
0 <= size <= capacity
capacity == 0 时 data 可以为 NULL
capacity > 0 时 data 指向至少 capacity 个 int 的可用空间

2.1 常见操作复杂度

操作 时间复杂度 原因
按下标访问 $O(1)$ 地址可直接计算
查找指定值 $O(n)$ 无序时需要逐个比较
尾部插入 均摊 $O(1)$，最坏 $O(n)$ 扩容时需要搬移元素
头部或中间插入 $O(n)$ 后续元素需要后移
头部或中间删除 $O(n)$ 后续元素需要前移

2.2 一份可运行的动态顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} SeqList;

static void seq_init(SeqList *list)
{
    assert(list != NULL);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

static bool seq_reserve(SeqList *list, size_t min_capacity)
{
    assert(list != NULL);
    if (list->capacity >= min_capacity) {
        return true;
    }

    size_t new_capacity = list->capacity == 0 ? 4 : list->capacity;
    while (new_capacity < min_capacity) {
        if (new_capacity > SIZE_MAX / 2) {
            return false;
        }
        new_capacity *= 2;
    }
    if (new_capacity > SIZE_MAX / sizeof(*list->data)) {
        return false;
    }

    int *new_data = realloc(list->data, new_capacity * sizeof(*new_data));
    if (new_data == NULL) {
        return false; /* 原 list 仍保持有效 */
    }
    list->data = new_data;
    list->capacity = new_capacity;
    return true;
}

static bool seq_insert(SeqList *list, size_t pos, int value)
{
    assert(list != NULL);
    if (pos > list->size || !seq_reserve(list, list->size + 1)) {
        return false;
    }
    for (size_t i = list->size; i > pos; --i) {
        list->data[i] = list->data[i - 1];
    }
    list->data[pos] = value;
    ++list->size;
    return true;
}

static bool seq_erase(SeqList *list, size_t pos)
{
    assert(list != NULL);
    if (pos >= list->size) {
        return false;
    }
    for (size_t i = pos + 1; i < list->size; ++i) {
        list->data[i - 1] = list->data[i];
    }
    --list->size;
    return true;
}

static void seq_destroy(SeqList *list)
{
    assert(list != NULL);
    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
}

int main(void)
{
    SeqList list;
    seq_init(&list);
    assert(seq_insert(&list, 0, 10));
    assert(seq_insert(&list, 1, 30));
    assert(seq_insert(&list, 1, 20));
    assert(seq_erase(&list, 0));
    assert(list.size == 2 && list.data[0] == 20 && list.data[1] == 30);
    printf("%d %d\n", list.data[0], list.data[1]);
    seq_destroy(&list);
    return 0;
}

这里使用临时指针接收 realloc 的结果。如果直接写 list->data = realloc(...)，分配失败时会丢失原指针，造成内存泄漏。

2.3 扩容为什么是均摊 $O(1)$

若容量按 2 倍增长，插入 $n$ 个元素时发生的搬移量最多约为：

$$
1+2+4+\cdots+\frac{n}{2}<n
$$

因此连续 $n$ 次尾插的总成本是 $O(n)$，平均到每次为均摊 $O(1)$。这不改变触发扩容的那一次仍为 $O(n)$ 的事实。

3. 链表

链表的节点不要求物理连续，逻辑顺序由指针表达。根据三个维度可组合出多种形式：

  • 单向或双向；
  • 带哨兵头节点或不带头节点；
  • 循环或非循环。

最常见的学习模型是无哨兵单链表；工程中带哨兵的双向循环链表也很常见，因为它能统一大量边界操作。

3.1 无哨兵单链表

1
2
3
4
typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;

头插只需修改两个链接，时间为 $O(1)$；尾插若只有头指针，需要遍历到尾部，时间为 $O(n)$。如果额外维护尾指针，尾插可降为 $O(1)$，但删除最后一个节点时仍需要找到它的前驱，除非改用双向链表。

3.2 完整的单链表常用操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;

static bool list_push_front(ListNode **head, int value)
{
    assert(head != NULL);
    ListNode *node = malloc(sizeof(*node));
    if (node == NULL) {
        return false;
    }
    node->value = value;
    node->next = *head;
    *head = node;
    return true;
}

static bool list_erase_value(ListNode **head, int value)
{
    assert(head != NULL);
    ListNode **link = head;
    while (*link != NULL && (*link)->value != value) {
        link = &(*link)->next;
    }
    if (*link == NULL) {
        return false;
    }
    ListNode *victim = *link;
    *link = victim->next;
    free(victim);
    return true;
}

static ListNode *list_reverse(ListNode *head)
{
    ListNode *prev = NULL;
    while (head != NULL) {
        ListNode *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

static void list_destroy(ListNode **head)
{
    assert(head != NULL);
    while (*head != NULL) {
        ListNode *next = (*head)->next;
        free(*head);
        *head = next;
    }
}

int main(void)
{
    ListNode *head = NULL;
    assert(list_push_front(&head, 3));
    assert(list_push_front(&head, 2));
    assert(list_push_front(&head, 1));
    assert(list_erase_value(&head, 2));
    head = list_reverse(head);
    assert(head != NULL && head->value == 3);
    printf("%d %d\n", head->value, head->next->value);
    list_destroy(&head);
    assert(head == NULL);
    return 0;
}

ListNode **link 指向“当前链接本身”，因此删除头节点和删除普通节点可以使用同一套逻辑，无需单独分支。

3.3 带哨兵的双向循环链表

哨兵节点不保存业务数据。空表时，哨兵的 next 和 prev 都指向自己：

1
2
sentinel.next == &sentinel
sentinel.prev == &sentinel

在已知节点 pos 前插入新节点时：

1
2
3
4
node->prev = pos->prev;
node->next = pos;
pos->prev->next = node;
pos->prev = node;

删除一个非哨兵节点时：

1
2
3
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);

由于头、尾和中间位置都邻接两个有效链接，插入删除逻辑非常统一。

4. 顺序表与链表对比

维度 顺序表 链表
物理内存 连续 通常分散
按下标访问 $O(1)$ $O(n)$
已知位置后的插入删除 可能移动元素，$O(n)$ 修改链接，$O(1)$
查找插入位置 $O(n)$ $O(n)$
扩容 可能整体搬迁 单节点按需分配
额外开销 可能有未使用容量 每节点有指针和分配元数据
缓存局部性 通常较好 通常较差
迭代器/指针稳定性 扩容或移动会失效 未删除节点通常较稳定

“链表任意位置插入删除都是 $O(1)$”缺少前提：必须已经持有该位置或相邻节点。若按值查找、按序号定位，查找本身仍为 $O(n)$。

5. 高频算法思路

5.1 删除数组中的指定值

使用快慢指针：快指针扫描所有元素，慢指针指向下一个保留位置。时间 $O(n)$、额外空间 $O(1)$，且能保持剩余元素的相对顺序。

5.2 链表中点

快指针每次走两步，慢指针每次走一步。快指针到达末尾时，慢指针位于中点。若长度为偶数，具体返回前一个还是后一个中点要在循环条件中明确约定。

5.3 判断链表是否有环

Floyd 快慢指针算法使用 $O(1)$ 额外空间：若存在环，快慢指针最终会在环内相遇。相遇后让一个指针回到头部，两指针每次各走一步，再次相遇的位置就是入环点。

5.4 合并两个有序链表

使用哨兵节点保存结果链表起点，每次从两个表头选择较小节点接到尾部。每个节点只处理一次，时间 $O(m+n)$，额外空间 $O(1)$（复用原节点时）。

6. 常见错误

  • 插入前没有检查 pos <= size，删除前没有检查 pos < size；
  • 扩容乘法发生整数溢出；
  • realloc 失败时覆盖原指针；
  • 删除链表节点后继续访问该节点；
  • 反转链表时没有先保存 next，导致后续节点丢失；
  • 删除最后一个队列节点后只更新头指针，没有同步清空尾指针；
  • 把链表的理论 $O(1)$ 插入理解为实际一定比数组快，忽略缓存和分配成本。

7. 选择建议

如果数据需要频繁按下标访问、规模相对稳定、重视遍历性能，优先考虑顺序表。只有在节点需要稳定地址、已知位置插入删除非常频繁，或结构本身依赖链接关系时，链表才更合适。

真正的判断标准不是“谁的 Big-O 更小”，而是应用最常执行哪些操作、数据规模多大、是否需要连续内存，以及能否接受额外指针和动态分配成本。