线性表（Linear List）

线性表是具有相同数据类型的 n 个数据元素的有序序列。除第一个和最后一个外，每个元素都有且仅有一个直接前驱和一个直接后继。

两种典型存储

1. 顺序存储（顺序表）

• 用一段连续内存顺序存放各元素（通常是数组）。
• 访问第 (i) 个元素时间复杂度 (O(1))；在中间位置插入/删除平均代价 (O(n))。

// 在顺序表 a[0..n-1] 的位置 i 插入 x（0 <= i <= n < MAXN）
int insert(int a[], int *n, int i, int x) {
    if (i < 0 || i > *n) return 0;
    for (int k = *n; k > i; --k) a[k] = a[k-1];
    a[i] = x; (*n)++;
    return 1;
}

2. 链式存储（链表）

• 各元素存放在不连续的结点中，通过指针链接。
• 单链表、双向链表、循环链表等；在已知结点处插入/删除为 (O(1))，但按位访问需遍历 (O(n))。

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

// 在 p 结点后插入新结点，值为 x
void insert_after(Node *p, int x) {
    Node *s = (Node*)malloc(sizeof(Node));
    s->val = x;
    s->next = p->next;
    p->next = s;
}

基本运算

• 按位（或按值）查找、插入、删除、长度、判空、清空、遍历。
• 顺序表适合随机访问频繁、删除插入少的场景；链表适合频繁插入/删除或空间不连续的场景。

复杂度对比（要点）

• 访问第 (i) 个元素：顺序表 (O(1))，链表 (O(n))
• 插入/删除（已知位置）：顺序表 (O(n))，链表 (O(1))
• 空间：顺序表需连续空间；链表额外指针开销但更灵活

备考建议：能熟练实现顺序表和链表的基本操作，并理解二者的适用场景与复杂度差异。