1. 单链表的初始化#

带头结点与个带头结点的单链表在初始化时有所不同。带头结点的单链表初始化时，需创建一个头结点，并令头指针L指向该头结点，其next指针初始化为NULL。

1
bool InitList(LinkList &L){         //带头结点的单链表初始化
2
    L=(LNode*)malloc(sizeof(LNode));//创建头结点
3
    L->next=NULL;                   //头结点之后暂无数据结点
4
    return true;
5
}

不带头结点的单链表初始化时，只需将头指针 L 初始化为 NULL。

1
bool InitList(LinkList &L) {        //不带头结点的单链表初始化
2
    L=NULL;
3
    return true;
4
}

NOTE

设 p 为指向链表结点的结构体指针，则*p 表示该结点本身。可通过 p->data 或 (*p).data 访问其数据域，二者完全等价。成员运算符 (.) 左侧应为结构体变量，指向运算符 (->) 左侧应为结构体指针。例如，p->next->data 等价于 (*(*p).next).data，表示当前结点后继结点的数据。

2. 求表长操作#

求表长是指统计单链表中数据结点的个数(不包括头结点)。从第一个数据结点开始依次遍历，为此需要设置一个计数变量，每访问一个结点，其值加1，直到遇到NULL。

1
int Length(LinkList L) {
2
    int len=0;              //计数变量，初始为0
3
    LNode *p=L;
4
    while (p->next != NULL) {
5
        p=p->next;
6
        len++;              //每访问一个节点，计数加1
7
    }
8
    return len;
9
}

求表长操作的时间复杂度为 $O(n)$。

另外，需要注意的是，由于表长不包含头结点，带头结点与不带头结点的实现细节略有不同。

3. 按序号查找结点#

从单链表的第一个数据结点开始，沿 next 指针逐个查找，返回第 i 个结点的指针；若 i 超出表长，则返回 NULL。

1
LNode *GetElem(LinkList L, int i) {
2
    LNode *p = L;                   //指针 p 指向当前扫描结点
3
    int j = 0;                      //j 记录当前位序，头结点为第 0 个结点
4
    while (p != NULL & & j < i) {   //循环找到第 i 个结点
5
        p = p->next;
6
        j++;
7
    }
8
    return p;                       //返回第 i 个结点的指针或 NULL
9
}

按序号查找操作的时间复杂度为 $O(n)$。

4. 按值查找表结点#

从单链表的第一个数据结点开始，依次比较各结点的数据域，若等于给定值 e，则返回该结点指针；否则返回 NULL。

1
LNode *LocateElem(LinkList L,ElemType e){
2
    LNode *p=L->next;
3
    while(p!=NULL&&p->data!=e)  //从第一个结点开始查找数据域为e的结点
4
        p=p->next;
5
    return p;                   //找到后返回该结点指针，否则返回 NULL
6
}

按值查找操作的时间复杂度为 $O(n)$。

5. 插入结点操作#

将值为 e 的新结点插入到第 i 个位置(成为新的第 i 个数据结点)。先检查 i 的合法性，然后找到第 i-1 个结点(前驱)，再在其后插入新结点。假设找到的第 i-1 个结点为*p，然后令新结点*s 的 next 指向*p 的后继，再令*p 的 next 指向*s。

1
bool ListInsert(LinkList &L, int i, ElementType e) {
2
    LNode *p = L;                       //p 指向当前扫描结点
3
    int j = 0;                          //j 记录当前位序，头结点为第 0 个结点
4
    while (p != NULL & &j < i - 1) {    //循环找到第 i-1 个结点
5
        p = p->next;
6
        j++;
7
    }
8
    if (p == NULL)                      //i 值不合法
9
        return false;
10
    LNode *s = (LNode*)malloc(sizeof(LNode));
11
    s -> data = e;
12
    s -> next = p -> next;              //步骤1
13
    p -> next = s;                      //步骤2
14
    return true;
15
}

步骤1和2的顺序不可颠倒。若先执行 p->next=s，则原后继地址丢失，导致 s->next=p->next 实际变为 s->next=s，形成自环。该操作的时间复杂度为 $O(n)$，主要开销在于查找前驱结点。若已知某结点指针，则在其后插入新结点的时间复杂度为 $O(1)$。注意，当插入位置 i=1 时，不带头结点的单链表需要更新头指针 L 指向新首结点，而带头结点的则无须特殊处理。

扩展：对某个结点进行前插操作。

前插操作是指在某结点前插入一个新结点，与后插操作相反。任何前插操作均可转化为后插操作：只需从头结点开始顺序查找其前驱，时间复杂度为 $O(n)$。若对给定结点进行前插，则还可采用另一种技巧(适用于数据可复制的情况)：将新结点 *s 插入目标结点 *p 之后，再交换 *p 与 *s 的数据域。这种技巧逻辑上等效于前插，且时间复杂度为 $O(1)$。主要代码片段如下：

1
s->next=p->next;    //修改指针域，不能颠倒
2
p->next=s;
3
temp=p->data;       //交换数据域部分
4
p->data=s->data;
5
s->data=temp;

6. 删除结点操作#

删除单链表的第 i 个数据结点。先检查 i 的合法性，然后找到第 i-1 个结点(前驱)，再删除其后继结点，并释放内存。假设找到的第 i-1 个结点为*p，其后继为被删结点*q，先将*p 的 next 指向*q 的后继结点，然后释放*q 的存储空间。

1
bool ListDelete(LinkList &L, int i, ElemType &e) {
2
    LNode *p = L;                           //指针p指向当前扫描到的结点
3
    int j = 0;                              //记录当前结点的位序，头结点是第0个结点
4
    while (p->next != NULL && j < i - 1) {  //循环找到第 i-1 个结点
5
        p = p->next;
6
        j++;
7
    }
8
    if (p->next == NULL || j > i - 1)       //i 值不合法
9
        return false;
10
    LNode *q = p->next;                     //令q指向被删除的结点
11
    e = q->data;                            //用e返回元素的值
12
    p->next = q->next;                      //把*q结点从链中断开
13
    free(q);                                // 释放结点的存储空间
14
    return true;
15
}

类似于插入操作，该操作的主要耗时也在查找操作上，时间复杂度为 $O(n)$。

当链表不带头结点时，需判断被删结点是否为首结点，若是，则要做特殊处理，将头指针 L 指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

扩展：删除给定结点 *p。

常规方法需要从头遍历找到*p 的前驱，时间复杂度为 $O(n)$。若允许修改结点内容，则可采用一种 $O(1)$ 的技巧：将*p 的后继结点的数据复制到*p 中，然后删除其后继结点。该方法的局限性在于不能用于删除尾结点(因其无后继)。主要代码片段如下：

1
LNode *q=p->next;       //令 q 指向*p 的后继结点
2
p->data=p->next->data;  //用后继结点的数据域覆盖
3
p->next=q->next;        //将*q 结点从链中“断开”
4
free(q);                //释放后继结点的存储空间

7. 采用头插法建立单链表#

该方法从一个空表开始，生成新结点*s，并将读取的数据存入其数据域。然后，令 s->next 指向头结点当前 next 所指的结点，再将头结点的 next 指向*s。重复此过程，新结点始终成为第一个数据结点，最终链表中的元素顺序与输入顺序相反。

1
LinkList List_HeadInsert(LinkList &L){  //逆向建立单链表
2
    LNode *s; int x;                    //设元素类型为整型
3
    L=(LNode*)malloc(sizeof(LNode));    //创建头结点
4
    L->next=NULL;                       //初始为空链表
5
    scanf("%d",&x);                     //输入结点的值
6
    while (x!=9999){                    //输入9999表示结束
7
        s=(LNode*)malloc(sizeof(LNode));//创建新结点
8
        s->data=x;
9
        s->next=L->next;
10
        L->next=s;                      //将新结点插入表中，L为头指针
11
        scanf("%d",&x);
12
    }
13
    return L;
14
}

每插入一个结点的时间复杂度为 $O(1)$，总时间复杂度为 $O(n)$。

NOTE

若单链表不带头结点，则上述代码中哪些地方需要修改？

8. 采用尾插法建立单链表#

若希望输入顺序与链表中的元素顺序一致，则可采用尾插法。该方法将新结点插入当前链表的表尾。为此，需要维护一个尾指针 r，并且始终指向当前的尾结点；插入时，令 r -> next 指向新结点 *s，再将 r 更新为 s，使其继续指向新的尾结点。

1
LinkList List_TailInsert(LinkList &L){  //正向建立单链表
2
    int x;                              //设元素类型为整型
3
    L=(LNode*)malloc(sizeof(LNode));    //创建头结点
4
    LNode *s, *r = L;                   //r 为表尾指针
5
    scanf("%d", &x);                    //输入结点的值
6
    while (x != 9999) {                 //输入 9999 表示结束
7
        s = (LNode *)malloc(sizeof(LNode));
8
        s -> data = x;
9
        r -> next = s;
10
        r = s;                          //r 指向新的表尾结点
11
        scanf("%d", &x);
12
    }
13
    r -> next = NULL;                   //尾结点指针置空
14
    return L;
15
}

因为附设了一个尾指针，故无须遍历查找尾部，总时间复杂度仍为 $O(n)$。

NOTE

单链表是链式存储结构的基础，建议读者熟练掌握其基本操作。在设计算法时，可先通过画图理清指针变化逻辑，再编写代码，有助于避免常见错误(如指针丢失、内存泄漏等)。

1. 双链表的插入操作#

在双链表的结点*p之后插入新结点*s。代码片段如下：

1
s -> next = p -> next;      //将结点*s插入到结点*p之后
2
p -> next -> prior = s;
3
s -> prior = p;
4
p -> next = s;

上述语句的执行顺序并不是任意的：步骤1必须在步骤4之前，否则 p->next 被覆盖后，无法访问原后继结点，导致指针丢失，插入失败。其余步骤可在保证逻辑正确的前提下适当调整(例如3可在1前执行)。若问题改成要求在结点*p之前插入结点*s，则要如何处理？请读者自行推导操作步骤。

2. 双链表的删除操作#

删除双链表中结点 *p 的后继结点 *q。

1
p->next=q->next;    //步骤1
2
q->next->prior=p;   //步骤2
3
free(q);            //释放结点空间

若问题改成要求删除结点 *q 的前驱结点 *p，请读者尝试写出对应的操作步骤。

建立双链表时，同样可以采用类似单链表的头插法或尾插法，但要注意：每次插入新结点时，要同时正确设置 next 和 prior 两个指针，以维持双向链接的完整性。

1. 循环单链表#

循环单链表与普通单链表的主要区别在于：表中最后一个结点的next域不再为NULL，而是指向头结点，从而使整个链表形成一个环。这种结构使得从任意一个结点出发均可遍历整个循环单链表，而不仅限于从表头开始。

尾结点 *r 的 next 指向头结点，因此链表中不存在 next 为 NULL 的结点。判空条件不再是检查头指针 L 是否为空，而是检查头结点的 next 是否指向自身(L->next==L)。

循环单链表的插入和删除操作与普通单链表基本相同，但有一个关键差异：在表尾进行操作时，需要特别处理以维持链表的循环特性。然而，正是因为循环单链表是一个环，在任何位置上的插入和删除操作都是等价的，因此无须判断是否到达表尾。

为了提高效率，循环单链表有时不设头指针，而仅设置尾指针 $\mathbf{r}$。此时，在表头或表尾插入元素的时间复杂度均为 $O(1)$。若使用头指针，则表尾插入需要遍历整个链表，时间复杂度为 $O(n)$。例如，在表尾插入新结点 $\star$ s 时，需要执行以下步骤：令 $s \rightarrow \text{next} = \text{r} \rightarrow \text{next}$(使新结点的后继指向头结点，以维持环状结构)；将 $\mathbf{r} \rightarrow \text{next}$ 指向新结点 *s；更新 $\mathbf{r}$ 为新结点 *s。

2. 循环双链表#

基于循环单链表的概念，不难推导出循环双链表。不同之处在于：循环双链表中的每个结点不仅包含指向下一个结点的next域，还包含指向前一个结点的prior域。特别地，头结点的prior需要指向表尾结点，从而形成一个完整的环形结构。

图2.13 循环双链表

设尾结点为*p，则 p->next 应指向头结点 L；同时，L->prior 应指向*p。当循环双链表为空时，其头结点 L 的 prior 和 next 都指向自身(L->prior == L 且 L->next == L)。

1. 存取(读/写)方式#

顺序表支持随机存取，可通过下标直接访问任意位置元素，时间复杂度为 $O(1)$，同时也支持顺序存取。链表仅支持顺序存取，必须从头结点开始逐个遍历。例如，访问第 i 个元素时，顺序表只需一次操作；而链表需要遍历 i 个结点，平均时间复杂度为 $O(n)$。

2. 逻辑结构与物理结构#

顺序存储中，逻辑上相邻的元素在物理内存中也连续存放，其邻接关系由地址自然体现；链式存储中，逻辑相邻的元素在物理上未必相邻，其逻辑关系通过指针显式维护。

3. 查找、插入和删除操作#

对于按值查找，若表无序，则两者的时间复杂度均为 $O(n)$；若表有序，则顺序表可以采用折半查找，时间复杂度为 $O(\log_{2}n)$。对于按序号查找，顺序表的时间复杂度为 $O(1)$，链表则为 $O(n)$。对于插入/删除操作，顺序表平均需移动约一半的元素，开销较大；链表只需修改指针，无须移动元素，但前提是已知操作位置(否则仍需 $O(n)$ 的时间定位)。

4. 空间分配#

顺序表在静态分配下需预先设定容量：过大造成内存浪费，过小则易在插入时溢出。动态分配虽支持运行时扩容，但需要申请新的连续内存块并复制全部原有数据，不仅耗时，还可能因系统缺乏足够连续空闲空间而失败。相比之下，链表采用动态结点分配，按需扩展，灵活性高，但每个结点需额外存储指针域，导致存储密度小于1，空间利用率较低。

在实际应用中，该如何选择合适的存储结构呢？

1. 基于存储的考虑#

当线性表的长度或规模难以预估时，顺序表因需预先分配固定容量而不适用；而链表无须预设容量，可按需动态扩展，但每个结点需额外存储指针，带来一定的空间开销。

2. 基于运算的考虑#

若应用中频繁进行按序号访问(随机访问)，顺序表具有 O(1) 的优势，明显更高效；而对于以插入和删除为主的操作，链表在定位目标位置后仅需调整指针，开销较小。尽管定位过程本身仍需 O(n) 时间，但在增删密集的场景下，链表的整体性能通常更优。

3. 基于环境的考虑#

顺序表基于数组实现，几乎所有高级语言都支持，实现简单；链表则依赖指针操作，在部分环境中实现较为复杂。因此，开发语言和运行环境也是重要的考量因素。

综上所述，两种结构各有优劣。对于规模稳定、以随机访问为主的场景，宜采用顺序存储；而动态性强、频繁进行插入和删除操作的场景，则更适合链式存储。

NOTE

只有熟练掌握线性表的顺序存储和链式存储，才能深刻理解它们的优缺点。