掌握单链表的头结点、插入删除和建表方法，并比较双向链表、循环链表、静态链表与顺序表的结构特征和适用场景。

# 一、线性表的链式表示

# 1. 单链表与头结点

单链表的每个结点包含数据域和指针域。指针域保存逻辑后继结点的地址，最后一个结点的 next 为 NULL。

#include <stdbool.h>
#include <stdlib.h>

typedef int ElemType;

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

带头结点的单链表中，head 指向一个不存放有效数据的头结点，首个数据结点为 head->next。空表时 head->next == NULL。头结点能统一首元素插入、删除和空表的边界处理。

flowchart LR
    H[head：头结点] --> A["数据 a1"]
    A --> B["数据 a2"]
    B --> C["数据 a3"]
    C --> N[NULL]

不带头结点时，空表的头指针本身为 NULL，首元素操作必须单独修改头指针。带头结点并非必须，但考试代码通常采用它以减少特判。

# 2. 单链表的基本操作

初始化和按位查找如下。第 $i$ 个数据结点从 head->next 开始计数，故要沿 next 走 $i$ 次才能到达第 $i$ 个数据结点。

LinkList ListInit(void) {
    LinkList head = malloc(sizeof(LNode));
    if (head != NULL) {
        head->next = NULL;
    }
    return head;
}

LNode *GetNode(LinkList head, int i) {
    if (i < 0) {
        return NULL;
    }

    LNode *p = head;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

其中 GetNode (head, 0) 返回头结点，GetNode (head, i) 返回第 $i$ 个数据结点。按位查找需要顺链扫描，时间复杂度为 $O(n)$ 。

在已知前驱结点 p 时，后插新结点 s 的两条赋值顺序不能颠倒：

bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }

    LNode *s = malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

若先执行 p->next = s，就会丢失原后继结点的地址。按位插入时，先查找第 $i-1$ 个结点，再后插：

bool ListInsert(LinkList head, int i, ElemType e) {
    LNode *p = GetNode(head, i - 1);
    return InsertNextNode(p, e);
}

删除 p 的后继结点同样只改动相邻指针；释放前必须暂存被删结点地址。

bool DeleteNextNode(LNode *p, ElemType *e) {
    if (p == NULL || p->next == NULL) {
        return false;
    }

    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

bool ListDelete(LinkList head, int i, ElemType *e) {
    LNode *p = GetNode(head, i - 1);
    return DeleteNextNode(p, e);
}

按位插入和删除的定位阶段为 $O(n)$ ；若 p 已知，InsertNextNode 和 DeleteNextNode 均为 $O(1)$ 。按值查找也必须从首结点逐个比较，最坏为 $O(n)$ 。

# 3. 头插法与尾插法

创建单链表时常见两种方法：

头插法：每次把新结点插在头结点之后，单次插入为 $O(1)$ ，最终元素顺序与输入顺序相反。
尾插法：维护尾指针 tail，每次在 tail 后插入并更新 tail，单次插入为 $O(1)$ ，最终顺序与输入顺序相同。

若尾插法没有维护尾指针，每次都从 head 遍历到表尾，构造 $n$ 个结点会退化为 $O(n^2)$ 。

# 二、其他链式结构

# 1. 双向链表

双向链表的结点含有 prev 和 next 两个链域，既能向前也能向后遍历。带头结点的循环双链表尤其常用：空表时 head->next == head 且 head->prev == head。

typedef struct DNode {
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
} DNode, *DLinkList;

把新结点 s 插入结点 p 之前，应先接好 s 的两个方向，再修改两侧结点：

void InsertPriorNode(DNode *p, DNode *s) {
    s->prior = p->prior;
    s->next = p;
    p->prior->next = s;
    p->prior = s;
}

删除已知结点 p 时，前驱和后继必须分别绕过 p：

void DeleteNode(DNode *p) {
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
}

若 p 已知，双链表删除 p 不需额外寻找前驱；单链表通常必须先得到 p 的前驱。双链表的代价是每个结点多一个指针域。

# 2. 循环链表

循环链表让尾结点不再指向 NULL，而是指向头结点或首数据结点。单循环链表只能沿 next 方向循环；双向循环链表则可以双向循环。

循环单链表若只保存尾指针 r，则首结点为 r->next；对表头和表尾进行插入或删除常可在 $O(1)$ 时间内完成。遍历时不能以 NULL 作为结束条件，而应判断是否回到起始结点。

# 3. 静态链表

静态链表使用结构体数组模拟链表。数组下标代替指针，next 的值保存后继结点的下标；某个约定值，例如 -1，表示链尾。

#define MAX_SIZE 100

typedef struct {
    ElemType data;
    int next;
} SNode;

SNode space[MAX_SIZE];

静态链表适合不支持指针或动态分配的环境。它仍具有链式结构 “修改链接而非移动元素” 的特点，但结点总数受数组容量限制。

# 三、顺序表与链表的选择

需求	更合适的表示	原因
高频按下标访问	顺序表	地址公式可在 $O(1)$ 时间定位
已知位置附近频繁插删	链表	改变少量链接即可完成
数据规模可预估且重视缓存局部性	顺序表	连续存储、指针额外开销小
数据规模变化大且难预估	链表或动态顺序表	可按需增长
需要双向移动或已知结点删除	双向链表	可直接利用 prior 找到前驱

选择结构不能只背 “顺序表查找快、链表插删快”，必须写清查找的是按位还是按值，插删前是否已经取得相关结点，容量是否受限，以及是否考虑缓存与指针开销。

# 四、考场检查清单

线性表位置从 1 还是数组下标从 0，必须统一。
顺序表插入从后向前搬移，删除从前向后搬移。
单链表插入先保存原后继，再接入新结点；删除先保存被删结点，再断链并释放。
头插法逆序，尾插法顺序；尾插应维护尾指针。
链表按位操作先定位，整体往往是 $O(n)$ ；已知结点或前驱后的改链才是 $O(1)$ 。
循环链表的结束条件不是 NULL；双向链表要同时维护两个方向的链接。