线性表

概念

线性表是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列。除首尾外，每个元素有且仅有一个前驱和一个后继。

它描述的是逻辑结构（元素之间一对一），与"用什么方式存"无关。存储方式有两种：

• 顺序存储 → 顺序表（数组）
• 链式存储 → 链表（指针）

一句话区分：顺序表是"排队"，链表是"寻宝"——前者靠位置直接找到人，后者靠每个人手里的线索找下一个。

原理

顺序表：逻辑相邻 = 物理相邻

用一段地址连续的存储单元依次存放元素。第 i 个元素的地址可以直接算出来：

$$Loc(a_i)=Loc(a_1)+(i-1)\times sizeof(ElemType)$$

所以顺序表是随机存取：给定下标，O(1) 就能定位。

但插入/删除要搬动元素：在第 i 个位置插入，要把第 i 个到第 n 个全部后移一位。

链表：靠指针串起来

每个结点 = 数据域 + 指针域。插入/删除只需改指针，不用搬元素，但找第 i 个结点必须从头往后数，是顺序存取。

常见变体：

类型	指针域	特点
单链表	只有后继指针	找前驱要从头遍历
双链表	前驱 + 后继	可双向走，删结点 O(1)（已知该结点）
循环链表	尾指向头	从任一结点可遍历全表
静态链表	数组下标代替指针	无指针语言里实现链表，408 考过

头结点是链表第一个元素之前的那个空结点，它的存在让"在第一个元素前插入"和"在其他位置插入"变成同一种操作，代码不必分情况——这是写链表代码时最省事的一个技巧。

示例

C 语言：顺序表插入

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

/* 在下标 i（0-based）处插入元素 e，成功返回 1，失败返回 0 */
int listInsert(SqList *L, int i, int e) {
    if (i < 0 || i > L->length || L->length >= MAXSIZE) return 0;
    for (int j = L->length; j > i; j--) {
        L->data[j] = L->data[j - 1];   /* 从最后一个开始后移 */
    }
    L->data[i] = e;
    L->length++;
    return 1;
}

int main(void) {
    SqList L = {{1, 2, 4, 5}, 4};
    listInsert(&L, 2, 3);              /* 在值为 4 的位置插入 3 */
    for (int i = 0; i < L.length; i++) printf("%d ", L.data[i]);
    printf("\nlength=%d\n", L.length);
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出：1 2 3 4 5，length=5。

C 语言：单链表头插法建表

#include <stdio.h>
#include <stdlib.h>

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

/* 头插法：每次把新结点插到头结点之后，结果顺序与输入相反 */
Node *createByHead(int a[], int n) {
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    for (int i = 0; i < n; i++) {
        Node *s = (Node *)malloc(sizeof(Node));
        s->data = a[i];
        s->next = head->next;
        head->next = s;
    }
    return head;
}

int main(void) {
    int a[] = {1, 2, 3, 4};
    Node *head = createByHead(a, 4);
    for (Node *p = head->next; p; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输入 1 2 3 4，头插法输出 4 3 2 1——逆序是头插法的标志，尾插法才是正序。

Python 对照

# Python 的 list 就是动态顺序表，插入同样是搬元素
lst = [1, 2, 4, 5]
lst.insert(2, 3)        # 在下标 2 处插入 3
print(lst, len(lst))    # [1, 2, 3, 4, 5] 5

# 链表用 deque 或手写；这里手写单链表体会指针操作
class Node:
    def __init__(self, data, nxt=None):
        self.data, self.next = data, nxt

head = Node(None)       # 头结点
for x in [1, 2, 3, 4]:  # 头插法
    head.next = Node(x, head.next)

p, out = head.next, []
while p:
    out.append(p.data)
    p = p.next
print(out)              # [4, 3, 2, 1]

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 移动次数（必会算）

在长度为 n 的顺序表第 i 个位置（1-based）插入，需后移 n - i + 1 个元素； 删除第 i 个元素，需前移 n - i 个元素。

若在任意位置插入/删除的概率相等，则期望移动次数：

• 插入：$\sum _{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{n}{2}$
• 删除：$\sum _{i=1}^n\frac{1}{n}(n-i)=\frac{n-1}{2}$

2. 时间复杂度对比表（几乎年年考）

操作	顺序表	单链表（已知位置）
按序号查找	O(1)	O(n)
按值查找	O(n)	O(n)
插入/删除（已知位置）	O(n)（搬元素）	O(1)（改指针）
插入/删除（要先找位置）	O(n)	O(n)（查找占大头）

注意陷阱：链表的插入本身是 O(1)，但找到那个位置是 O(n)，题目问"插入一个元素"通常指整体，答案仍是 O(n)。

3. 易错点

• 顺序表的下标从 0 还是 1 开始，题目与代码常常不一致，算移动次数时先统一。
• 双链表删结点：若已知该结点 p，O(1) 可删；若只知道值，仍要 O(n) 查找。
• 静态链表用数组下标充当指针，游标为 -1 表示表尾，插入删除不改物理位置只改游标。
• "链式存储一定比顺序存储省空间"是错的：链表每个结点还要额外存指针。

小结

• 线性表是逻辑结构，顺序表和链表是它的两种存储实现。
• 顺序表胜在随机存取，链表胜在插入删除不改物理位置。
• 判据很直接：查多改少用顺序表，改多查少用链表。
• 408 里这一章的分数基本出在"移动次数计算 + 复杂度对比 + 静态链表"这三处。

下一篇：栈与队列