2.3 双链表、循环链表与静态链表

双向指针带来的便利与代价、循环链表的判空条件、静态链表的游标机制，以及顺序表与链表的全面比较。

双链表

单链表只能从前往后遍历，要访问某结点的前驱只能从头开始，时间 $O(n)$。双链表在结点中增加一个指向前驱的指针 prior，访问前驱和后继都是 $O(1)$。

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;   // 前驱和后继指针
} DNode, *DLinkList;

插入与删除

双链表的按值查找、按位查找与单链表相同；但插入和删除要同时修改 prior 和 next 两个方向的指针，指针修改的顺序是选择题的高频考点。

1// 在 p 结点之后插入 s 结点
2bool InsertNextDNode(DNode *p, DNode *s) {
3    s->next = p->next;          // ①
4    if (p->next != NULL)
5        p->next->prior = s;     // ②
6    s->prior = p;               // ③
7    p->next = s;                // ④
8    return true;
9}

在 p 之前插入、删除 p 本身等操作，都可以借助 p->prior 转化为”在某结点之后操作”。

循环链表

循环单链表

表中最后一个结点的指针不是 NULL，而是指向头结点，整个链表形成一个环。

• 判空条件：L->next == L（头结点的 next 指向自己）。
• 判断 p 是否为尾结点：p->next == L。
• 从任意一个结点出发都能访问到链表中的每一个结点。
• 若只设尾指针 r，则头结点为 r->next，在表头、表尾插入都只需 $O(1)$——因此循环单链表常常只设尾指针。

循环双链表

头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点。

判空条件：L->next == L && L->prior == L。

静态链表

静态链表借助数组来描述线性表的链式存储结构：结点有数据域 data 和指针域 next，但这里的”指针”是结点在数组中的相对地址（数组下标），又称游标。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;          // 下一个元素的数组下标
} SLinkList[MaxSize];

上图中，从头结点（下标 0）出发，next = 2，于是第一个元素是 data[2] = a；data[2] 的 next = 1，第二个元素是 data[1] = b……直到 next == -1 表示表尾。可见元素在数组中的物理顺序与逻辑顺序无关。

• 与顺序表一样需要预先分配一块连续的内存空间；
• 插入、删除只需修改游标，不需要移动元素；
• 不能随机存取，只能从头结点开始依次往后查找；
• 适用于不支持指针的高级语言（如早期的 Basic），或数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）。

顺序表 vs 链表

怎样选择？

• 难以估计线性表的长度或存储规模时，用链表；
• 经常做按序号访问、很少插入删除时，用顺序表；
• 频繁插入删除时，用链表；
• 顺序表基于数组，实现简单、任何语言都支持；链表基于指针。

即时练习