Lecture 5：线性表的链式实现

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

5.1 单链表的实现

NOTE · 代码口径本文沿用 408 教材常见的 C++ 接口写法（bool、引用参数 &L），并保留 malloc/free 以便与课件对照。实际工程中应包含 <cstdlib> 并保证 malloc 与 free 成对，或统一改用 new/delete、智能指针和容器。若写纯 C，应把引用参数改成相应的指针或二级指针接口。

5.1.1 顺序表和单链表对比

顺序表

优点：
- 可以随机存取；
- 存储密度高。
缺点：
- 要求大片连续空间；
- 改变容量不方便；
- 插入、删除需要移动大量元素。

单链表

优点：
- 不要求大片连续空间；
- 改变容量比较方便；
- 插入、删除时不需要整体移动元素。
缺点：
- 不可随机存取；
- 需要额外空间存放指针。

理解

顺序表靠“地址连续”体现逻辑关系。
单链表靠“指针”体现逻辑关系。
顺序表适合按位查找，单链表适合频繁插入删除。

5.1.2 单链表结点定义

定义：#单链表结点

描述：单链表的每个结点通常由数据域和指针域组成，数据域存放元素值，指针域指向下一个结点。

代码

struct LNode {
    ElemType data;       // 数据域：存放一个数据元素
    struct LNode *next;  // 指针域：指向下一个结点
};

解释

data 保存当前结点的数据。
next 保存下一个结点的地址。
如果当前结点是最后一个结点，则：

p->next == NULL

5.1.3 typedef 写法

重命名语法

typedef <数据类型> <别名>;

教材常用写法

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

解释

LNode 表示结点类型。
LinkList 表示指向结点的指针类型。
也就是说：

LinkList L;

等价于：

LNode *L;

5.1.4 申请一个新结点

代码

struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

解释

malloc 在内存中申请一个结点大小的空间。
p 指向新申请的结点。
若申请失败，p 可能为 NULL，实际写代码时应判断。

5.2 不带头结点的单链表

5.2.1 初始化

定义：#不带头结点

描述：不带头结点的单链表中，头指针直接指向第一个数据结点；若链表为空，则头指针为 NULL。

代码

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

bool InitList(LinkList &L) {
    L = NULL;
    return true;
}

解释

空表没有任何结点，所以头指针为 NULL。
第一个数据结点就是头指针指向的结点。

5.2.2 判空

写法 1

bool Empty(LinkList L) {
    if (L == NULL) {
        return true;
    } else {
        return false;
    }
}

写法 2

bool Empty(LinkList L) {
    return (L == NULL);
}

解释

不带头结点时： $$ L=NULL $$ 表示空表。

5.3 带头结点的单链表

5.3.1 头指针和头结点

定义：#头指针

描述：头指针是指向链表第一个结点的指针，是链表的必要元素。

定义：#头结点

描述：头结点是放在第一个数据结点之前的附加结点，通常不存储有效数据，用于统一插入和删除操作。

区别

头指针：
- 必须存在；
- 用来标识整条链表；
- 链表为空时也存在。
头结点：
- 可有可无；
- 位于第一个数据结点之前；
- 数据域可以不存储任何信息；
- 主要作用是让表头插入和删除更方便。

带头结点空表

无论链表是否为空，头指针都指向头结点。
空表中，头结点的指针域为空：

L->next == NULL

为什么推荐带头结点

不带头结点时，插入第一个结点和插入其他结点的代码不同。
带头结点后，空表和非空表、表头和非表头位置的处理更统一。

5.4 单链表的插入

5.4.1 按位序插入：带头结点

定义：#按位序插入

描述： ListInsert(&L,i,e) 表示在链表 $L$ 的第 $i$ 个位置插入元素 $e$。

核心思路

找到第 $i-1$ 个结点。
将新结点插入到第 $i-1$ 个结点之后。

代码

bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }

    LNode *p = L;  // p 指向头结点
    int j = 0;     // 头结点是第 0 个结点

    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }

    if (p == NULL) {
        return false;
    }

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }

    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

解释

p=L：从头结点开始扫描。
j=0：头结点视为第 0 个结点。
循环结束时，若合法，则 p 指向第 $i-1$ 个结点。
插入的关键两步：

s->next = p->next;
p->next = s;

注意

两行顺序不能颠倒。
如果先写：

p->next = s;

则原来 p 后面的链会断掉。

图示解读

图中先找到第 $i-1$ 个结点 $p$，新结点 $s$ 保存元素 $e$。
先令 s->next=p->next 保存原后继，再令 p->next=s 把新结点接入链中；图中的两条新指向正对应这两步。

5.4.2 按位序插入：不带头结点

特点

不带头结点时，插入第 1 个结点需要特殊处理。
因为插入第 1 个结点会改变头指针。

代码

bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }

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

    LNode *p = L;
    int j = 1;

    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }

    if (p == NULL) {
        return false;
    }

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }

    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

结论

不带头结点的代码更麻烦。
推荐使用带头结点的单链表。

5.4.3 后插操作

定义：#后插操作

描述：后插操作是在已知结点 $p$ 后面插入新结点 $s$。

代码

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

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }

    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度

已知结点 $p$，只需修改指针： $$ O(1) $$

5.4.4 前插操作

定义：#前插操作

描述：前插操作是在已知结点 $p$ 前面插入元素 $e$。

普通思路

单链表无法直接找到 $p$ 的前驱。
若从头开始找 $p$ 的前驱，时间复杂度为： $$ O(n) $$

巧妙写法：后插 + 交换数据

在 $p$ 后面插入新结点 $s$；
把 $p$ 的数据复制到 $s$；
把 $e$ 放入 $p$ 的数据域；
逻辑效果等价于在 $p$ 前面插入 $e$。

代码

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

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;
    }

    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

时间复杂度

已知结点 $p$，用“后插 + 交换数据”实现前插： $$ O(1) $$

注意

这种方法改变的是结点中的数据内容，而不是实际把新结点放到 $p$ 的物理前面。
在只关心线性表逻辑顺序时，效果是正确的。

5.5 单链表的删除

5.5.1 按位序删除：带头结点

定义：#按位序删除

描述： ListDelete(&L,i,&e) 表示删除表 $L$ 中第 $i$ 个位置的元素，并用 $e$ 返回被删除元素的值。

核心思路

找到第 $i-1$ 个结点 $p$。
令 $q=p->next$ 指向被删除结点。
让 $p$ 跳过 $q$。
释放 $q$。

代码

bool ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1) {
        return false;
    }

    LNode *p = L;
    int j = 0;

    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }

    if (p == NULL || p->next == NULL) {
        return false;
    }

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

解释

p 指向第 $i-1$ 个结点。
q 指向第 $i$ 个结点，也就是要删除的结点。
p->next=q->next 将 $q$ 从链中断开。
free(q) 释放被删除结点。

5.5.2 删除指定结点 p

普通思路

单链表删除结点 $p$，需要找到 $p$ 的前驱。
如果 $p$ 是最后一个结点，只能从表头开始查找前驱。
时间复杂度： $$ O(n) $$

特殊技巧：删除 p 的后继并交换数据

如果 $p$ 不是最后一个结点，可以将后继结点的数据复制到 $p$ 中，再删除后继结点。

代码

bool DeleteNode(LNode *p) {
    if (p == NULL || p->next == NULL) {
        return false;
    }

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

时间复杂度

若 $p$ 不是最后一个结点： $$ O(1) $$
若 $p$ 是最后一个结点，必须找前驱： $$ O(n) $$

注意

这个技巧不能直接删除最后一个结点，因为最后一个结点没有后继。

5.6 单链表的查找

5.6.1 按位查找

定义：#GetElem

描述：按位查找是查找链表中第 $i$ 个结点。

带头结点代码

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

    LNode *p = L;
    int j = 0;

    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }

    return p;
}

解释

当 $i=0$ 时，返回头结点。
当 $i=1$ 时，返回第一个数据结点。
单链表不能随机访问，只能从头开始顺序查找。

时间复杂度 $$ O(n) $$

5.6.2 按值查找

定义：#LocateElem

描述：按值查找是在链表中查找数据域等于 $e$ 的结点。

代码

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;

    while (p != NULL && p->data != e) {
        p = p->next;
    }

    return p;
}

解释

从第一个数据结点开始查找。
找到则返回该结点指针。
找不到则返回 NULL。

时间复杂度 $$ O(n) $$

5.6.3 求表长

定义：#Length

描述：求表长是统计单链表中数据结点的个数。

代码

int Length(LinkList L) {
    int len = 0;
    LNode *p = L;

    while (p->next != NULL) {
        p = p->next;
        len++;
    }

    return len;
}

解释

p=L 从头结点开始。
每经过一个数据结点，len++。
当 p->next==NULL 时，说明已经到达尾结点。

时间复杂度 $$ O(n) $$

5.7 单链表的建立

5.7.1 尾插法

定义：#尾插法

描述：尾插法每次把新结点插入到链表尾部，可以正向建立单链表。

代码

LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));

    LNode *s;
    LNode *r = L;  // r 始终指向表尾结点

    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;

        r->next = s;
        r = s;

        scanf("%d", &x);
    }

    r->next = NULL;
    return L;
}

解释

r 是表尾指针。
每输入一个新元素，就把新结点接到 r 后面。
然后令 r=s，让 r 继续指向新的尾结点。
最后尾结点指针域置空：

r->next = NULL;

特点

建立出来的链表顺序与输入顺序一致。
时间复杂度： $$ O(n) $$

5.7.2 头插法

定义：#头插法

描述：头插法每次把新结点插入到头结点之后，因此建立出来的链表顺序与输入顺序相反。

代码

LinkList List_HeadInsert(LinkList &L) {
    int x;
    LNode *s;

    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;

        s->next = L->next;
        L->next = s;

        scanf("%d", &x);
    }

    return L;
}

解释

新结点总是插在头结点后面。
后输入的结点在前面。
因此头插法可以用于链表逆置。

时间复杂度 $$ O(n) $$

注意

PDF 中强调：头插法得到的是链表的逆置。

5.8 双链表

5.8.1 双链表结点定义

定义：#双链表

描述：双链表的每个结点有两个指针域，分别指向前驱结点和后继结点。

代码

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

解释

prior 指向前驱结点。
next 指向后继结点。
双链表可以向后遍历，也可以向前遍历。

5.8.2 双链表初始化：带头结点

代码

bool InitDLinkList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }

    L->prior = NULL;
    L->next = NULL;
    return true;
}

解释

带头结点的空双链表中，头结点存在。
头结点没有前驱。
头结点后面暂时没有数据结点。

5.8.3 双链表插入

定义：#双链表插入

描述：在双链表中，可以在已知结点 $p$ 后面插入结点 $s$。

图示解读

插入前，$p$ 的后继为 $c$；插入后应形成 $p\leftrightarrow s\leftrightarrow c$。
必须维护四个方向关系：s->next 指向 $c$，$c$ 的 prior 指向 $s$，s->prior 指向 $p$，$p$ 的 next 指向 $s$。

代码

bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) {
        return false;
    }

    s->next = p->next;

    if (p->next != NULL) {
        p->next->prior = s;
    }

    s->prior = p;
    p->next = s;
    return true;
}

解释

如果 $p$ 有后继，则需要修改后继结点的 prior。
插入时要同时维护：
- 前驱方向；
- 后继方向。
代码顺序很重要，避免断链。

5.8.4 双链表删除后继结点

图示解读

删除 $p$ 的后继 $q$ 后，应让 $p$ 与 $q$ 的后继 $c$ 重新双向相连：p->next=c，且当 $c$ 存在时令 c->prior=p。
两条实线表示删除前的相邻关系，虚线表示绕过 $q$ 后需要建立的新关系。

代码

bool DeleteNextDNode(DNode *p) {
    if (p == NULL) {
        return false;
    }

    DNode *q = p->next;
    if (q == NULL) {
        return false;
    }

    p->next = q->next;

    if (q->next != NULL) {
        q->next->prior = p;
    }

    free(q);
    return true;
}

解释

删除 $p$ 的后继结点 $q$。
如果 $q$ 后面还有结点，则要让后继结点的 prior 指回 $p$。

5.8.5 销毁双链表

代码

void DestroyList(DLinkList &L) {
    while (L->next != NULL) {
        DeleteNextDNode(L);
    }
    free(L);
    L = NULL;
}

解释

循环释放各个数据结点。
最后释放头结点。
头指针置为 NULL。

5.8.6 双链表遍历

后向遍历

while (p != NULL) {
    // 对结点 p 做相应处理
    p = p->next;
}

前向遍历

while (p != NULL) {
    // 对结点 p 做相应处理
    p = p->prior;
}

前向遍历：跳过头结点

while (p->prior != NULL) {
    p = p->prior;
}

PDF 笔误修正

PDF 中出现 while(p!==NULL)，C/C++ 中应写为：

while (p != NULL)

5.9 循环单链表

5.9.1 循环单链表的定义

定义：#循环单链表

描述：循环单链表的尾结点 next 指针不再指向 NULL，而是指向头结点。

初始化

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

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L->next = L;
    return true;
}

判空

bool Empty(LinkList L) {
    if (L->next == L) {
        return true;
    } else {
        return false;
    }
}

解释

普通单链表空表：

L->next == NULL

循环单链表空表：

L->next == L

5.9.2 判断尾结点

代码

bool isTail(LinkList L, LNode *p) {
    if (L != NULL && p != NULL && p != L && p->next == L) {
        return true;
    } else {
        return false;
    }
}

解释

带头结点的循环单链表中，非空表尾数据结点的后继是头结点；空表只有头结点，不能把它误判为数据尾结点。
因此，只有 p != L && p->next == L 时，$p$ 才是数据尾结点。

5.10 循环双链表

5.10.1 循环双链表的定义

定义：#循环双链表

描述：循环双链表中，头结点的 prior 指向尾结点，尾结点的 next 指向头结点。

结点定义

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

初始化

bool InitDLinkList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }

    L->prior = L;
    L->next = L;
    return true;
}

判空

bool Empty(DLinkList L) {
    if (L->next == L) {
        return true;
    } else {
        return false;
    }
}

解释

空的循环双链表中，头结点的前驱和后继都指向自己。
即： $$ L->prior=L,\quad L->next=L $$

图示解读

普通双链表两端以 NULL 为边界：头结点的 prior=NULL，尾结点的 next=NULL。
循环双链表没有 NULL 端点：头结点的 prior 指向尾结点，尾结点的 next 指向头结点；空表则退化为头结点的两个指针都指向自身。

5.10.2 循环双链表插入

代码

bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) {
        return false;
    }

    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

解释

循环双链表中，$p$ 的后继一定存在。
因此通常不需要判断 p->next != NULL。

5.10.3 循环双链表删除

代码

bool DeleteNextDNode(DLinkList L, DNode *p) {
    if (L == NULL || p == NULL || p->next == L) {
        return false;
    }

    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

注意

这里额外传入头指针 L，以便在空表或 p 为尾结点时拒绝删除 p->next 指向的头结点；若沿用原 PDF 只传 p 的代码，必须由调用者保证后继不是头结点，否则会释放哨兵并留下悬空指针。
上述插入、删除代码都假定 p 是本表内有效结点；插入时 s 还应是未链接到任何链表的独立新结点。
做题时要关注：
- 如何判断链表是否为空；
- 如何判断结点是否为头结点；
- 如何判断结点是否为尾结点；
- 如何在表头、表尾、中间进行插入和删除。

5.11 静态链表

5.11.1 静态链表的定义

定义：#静态链表

描述：静态链表是用数组来模拟链表的一种存储结构，结点中用游标 next 表示下一个元素的数组下标。

代码

#define MaxSize 10

struct Node {
    ElemType data;
    int next;
};

typedef struct Node SLinkList[MaxSize];

解释

data 存储数据元素。
next 存储下一个元素的数组下标。
SLinkList 相当于一个长度为 MaxSize 的 Node 型数组。

5.11.2 静态链表的特点

优点

不需要指针。
适用于不支持指针的低级语言。
可以用数组模拟链式结构。

缺点

不能随机存取。
只能从头结点开始依次往后查找。
容量固定不变。

适用场景

不支持指针的低级语言。
最大容量预先确定、但仍希望在数组内部灵活插入和删除的场景。
操作系统中的文件分配表 FAT 可作为理解例子。

注意

静态链表要同时约定“链尾”和“空闲单元”的游标标记，具体取值由实现决定，不能把普通数组下标当作标记值。
例如可约定 -1 表示链尾、-2 表示空闲单元： $$ \text{next}=-1\Rightarrow\text{链尾},\qquad \text{next}=-2\Rightarrow\text{空闲} $$
插入时从空闲单元中取一个结点并修改游标；删除后把该数组位置重新标为空闲。若实现维护备用链表，也可以用另一套游标规则。

图示解读

静态链表的结点在数组中物理连续，但逻辑次序由 next 游标决定。图中逻辑链为 $0\to2\to1\to6\to3$，并不等于数组下标顺序。
游标保存的是“下一个结点的数组下标”，作用类似普通链表中的地址指针，因此静态链表仍不能按逻辑位序随机存取。

5.12 本节复盘

必须掌握

单链表结点由数据域和指针域组成。
带头结点可以统一表头和非表头位置的插入删除。
单链表按位查找、按值查找、求表长的时间复杂度都是： $$ O(n) $$
已知结点 $p$ 后插，时间复杂度是： $$ O(1) $$
双链表比单链表多一个 prior 指针，可以向前查找。
循环链表的尾结点不指向 NULL，而是指回头结点。
静态链表用数组下标模拟指针。

易错点

头指针必须存在，头结点可有可无。
不带头结点时，插入第一个结点要单独处理。
单链表插入时：

s->next = p->next;
p->next = s;

顺序不能反。

删除结点后要释放空间：

free(q);

单链表不能随机存取。
循环单链表判空不是 L->next == NULL，而是：

L->next == L

代码题抓手

单链表按位插入：先找第 $i-1$ 个结点。
单链表按位删除：先找第 $i-1$ 个结点，再删它的后继。
尾插法：正向建表，关键是维护尾指针 r。
头插法：逆向建表，可以用于链表逆置。
双链表插入删除：必须同时维护 prior 和 next。

5.1 单链表的实现

5.1.1 顺序表和单链表对比

5.1.2 单链表结点定义

定义：#单链表结点

5.1.3 typedef 写法

5.1.4 申请一个新结点

5.2 不带头结点的单链表

5.2.1 初始化

定义：#不带头结点

5.2.2 判空

5.3 带头结点的单链表

5.3.1 头指针和头结点

定义：#头指针

定义：#头结点

5.4 单链表的插入

5.4.1 按位序插入：带头结点

定义：#按位序插入

5.4.2 按位序插入：不带头结点

5.4.3 后插操作

定义：#后插操作

5.4.4 前插操作

定义：#前插操作

5.5 单链表的删除

5.5.1 按位序删除：带头结点

定义：#按位序删除

5.5.2 删除指定结点 p

5.6 单链表的查找

5.6.1 按位查找

定义：#GetElem

5.6.2 按值查找

定义：#LocateElem

5.6.3 求表长

定义：#Length

5.7 单链表的建立

5.7.1 尾插法

定义：#尾插法

5.7.2 头插法

定义：#头插法

5.8 双链表

5.8.1 双链表结点定义

定义：#双链表

5.8.2 双链表初始化：带头结点

5.8.3 双链表插入

定义：#双链表插入

5.8.4 双链表删除后继结点

5.8.5 销毁双链表

5.8.6 双链表遍历

5.9 循环单链表

5.9.1 循环单链表的定义

定义：#循环单链表

5.9.2 判断尾结点

5.10 循环双链表

5.10.1 循环双链表的定义

定义：#循环双链表

5.10.2 循环双链表插入

5.10.3 循环双链表删除

5.11 静态链表

5.11.1 静态链表的定义

定义：#静态链表

5.11.2 静态链表的特点

相关知识

5.12 本节复盘