# 链之变体：单向、双向、循环、哑头的结构演进与初始化实现
链表不是单一的数据结构，而是一族以“结点+指针”为基本元素的容器家族。单向链表是起点，但工程实践中，**双向链表**解决逆向遍历难题，**循环链表**统一头尾边界，**哑头节点**消除空表特判。理解这些变体的设计动机，比背诵十种链表实现更有价值。本文从结构分类出发，聚焦双向链表的初始化与核心操作，呈现链表演进的逻辑脉络。
---
## 一、链表家族的四种基本形态
**单向链表**：每个结点仅存储后继指针。结构最简，内存最省，但删除结点需遍历前驱，逆向遍历无法实现。
**双向链表**：结点增加前驱指针`prev`。删除结点O(1)，支持双向遍历，代价是每个结点多占用一个指针空间。
**循环链表**：尾结点后继指向头结点（双向循环则头结点前驱指向尾结点）。**空表与非空表操作模式统一**，且从任一结点出发可访问全表。
**哑头节点**：在首元结点之前附加一个不存储数据的头结点。**插入、删除首元结点时无需修改头指针**，边界逻辑大幅简化。
四种特征可任意组合。工程中最常见的是**带头双向循环链表**——兼具双向遍历、循环访问、无边界特例三大优势。
---
## 二、双向链表的结点定义与初始化
双向链表结点包含数据域、前驱指针、后继指针：
```c
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
```
**初始化策略分两种流派**。
**流派A：不带头结点，头指针为空表示空表**
```c
DNode* list = NULL; // 空表
```
此风格节省一个结点空间，但插入删除首元结点时必须修改头指针本身，需传递二级指针。
**流派B：带头哑结点，头指针固定指向哑头**
```c
DNode* list_create(void) {
DNode* head = (DNode*)malloc(sizeof(DNode));
head->prev = head; // 前驱指向自身
head->next = head; // 后继指向自身
return head;
}
```
**初始化即成环**。空表状态并非`NULL`，而是**仅剩哑头结点的自环**。此设计使所有操作均无需判断`head == NULL`，且首尾操作代码完全对称。
---
## 三、带头双向循环链表的操作美学
**插入操作**：在指定结点`pos`之后插入新结点。
```c
void dlist_insert_after(DNode* pos, int val) {
DNode* node = (DNode*)malloc(sizeof(DNode));
node->data = val;
<"c8.a8k1.org.cn"><"y0.a8k1.org.cn"><"e4.a8k1.org.cn">
node->prev = pos;
node->next = pos->next;
pos->next->prev = node;
pos->next = node;
}
```
**四指针重连**是双向链表插入的标准步骤。顺序要点：**先处理新结点的前后指向，再断开原链关系**。若先修改`pos->next`，则丢失原后继地址。
**头插与尾插**：因链表循环且带头结点，头插即`dlist_insert_after(head, val)`，尾插即`dlist_insert_after(head->prev, val)`。**同一函数，两种语义**。
**删除操作**：删除指定结点。
```c
void dlist_remove(DNode* node) {
if (node->next == node) return; // 仅剩哑头？不应删除
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
```
**无需知道头指针**。结点自携带前驱后继信息，可从链中自解脱。这是双向链表对比单向的核心优势。
**遍历操作**：正向与逆向完全对称。
```c
void dlist_print_forward(DNode* head) {
for (DNode* p = head->next; p != head; p = p->next) {
printf("%d ", p->data);
}
}
void dlist_print_backward(DNode* head) {
for (DNode* p = head->prev; p != head; p = p->prev) {
printf("%d ", p->data);
}
}
```
**循环终止条件**：回到哑头即遍历结束。无论正向逆向，代码结构完全一致。
---
## 四、单向 vs 双向：取舍点与工程决策
| 操作 | 单向链表 | 双向链表 |
|--------------|------------------------|--------------------|
| 内存占用 | 1指针/结点 | 2指针/结点 |
| 逆向遍历 | 不可 | O(1) |
| 删除给定结点 | 需遍历前驱，O(n) | 直接操作，O(1) |
| 插入前后 | 需遍历定位前驱/后继 | 前后均O(1) |
| 实现复杂度 | 较低 | 稍高 |
**选型建议**：
- 仅需正向遍历、尾插为主 → 单向链表足够；
- 需频繁删除给定结点、需双向遍历 → 双向链表；
- 不确定时，**带头双向循环链表**是通用选择，灵活性最高。
---
## 五、从结构到容器：封装的意义
原始的双向链表操作直接暴露`prev`/`next`指针，使用者需自行维护四指针重连。工程化封装应将**结点操作收敛于接口内部**：
```c
typedef struct {
DNode* head;
size_t size;
} DList;
<"u6.a8k1.org.cn"><"g3.a8k1.org.cn"><"q7.a8k1.org.cn">
void dlist_init(DList* list) {
list->head = (DNode*)malloc(sizeof(DNode));
list->head->prev = list->head;
list->head->next = list->head;
list->size = 0;
}
void dlist_push_back(DList* list, int val) {
dlist_insert_after(list->head->prev, val);
list->size++;
}
```
将“哑头+循环+双向”的特征封装为`DList`容器，使用者操作`push_back`、`pop_front`、`size`，无需感知指针重连细节。**这是数据结构从“实现”走向“服务”的必经阶段**。
---
链表的演进史，是不断**消除边界、对称化操作、提升抽象层次**的过程。单向→双向，解决逆向问题；非循环→循环，统一头尾；无哑头→有哑头，抹平空表特例。每一次演进都在降低使用者的心智负担。
理解这四种变体，不是为了在代码中刻意选用最复杂的那一种，而是建立**结构适配需求**的设计直觉。当面对“需频繁删除结点”的需求时，自然选择双向；当面对“头尾操作均频繁”的场景时，自然选用循环。这是从“会用链表”到“善用链表”的认知分界。