引言
在前面的文章中，我们详细讲解了单向链表。单向链表虽然结构简单，但存在一个天然缺陷：只能单向遍历，无法从后往前访问。这在某些场景下（如需要双向查找、在任意位置前后插入删除）会造成不便。
双向链表（Doubly Linked List）通过为每个节点增加一个prev指针，实现了向前和向后两个方向的遍历能力。本文将系统讲解双向循环链表的原理与实现，并对比单向链表与双向链表的设计差异。
第一部分：双向循环链表的设计原理
一、数据结构定义
// 节点结构体 typedef struct DuList { int val; // 数据域 struct DuList* prev; // 前驱指针 struct DuList* next; // 后继指针 } DuList; // 链表管理结构体（带头结点） typedef struct DuLinkList { struct DuList* head; // 头结点指针 size_t cursize; // 元素个数 } DuLinkList;二、关键设计：循环结构
空链表的状态：
有元素的状态：
三、判空条件
// 双向循环链表的判空 bool IsEmpty(const DuLinkList* dps) { return dps->head->next == dps->head; // 或者 // return dps->head->prev == dps->head; // 或者 // return dps->cursize == 0; }| 链表类型 | 空表判断 |
|---|---|
| 单向不带头结点 | head == NULL |
| 单向带头结点 | head->next == NULL |
| 双向循环带头结点 | head->next == head |
第二部分：初始化与节点管理
一、创建节点
DuList* Buynode(ElemType val) { DuList* p = (DuList*)malloc(sizeof(DuList)); if (p == NULL) return NULL; p->prev = NULL; p->next = NULL; p->val = val; return p; }二、初始化链表
void InitDuLinkList(DuLinkList* dps) { assert(dps != NULL); // 创建头结点（存储的值可任意，一般存 0） DuList* head = Buynode(0); if (head == NULL) return; // 循环指向自己 head->next = head; head->prev = head; dps->cursize = 0; dps->head = head; }初始化后的状态：
第三部分：插入操作
一、核心插入逻辑：在指定节点前插入
双向链表的插入有一个通用操作：在指定节点ptr前插入新节点。掌握了这个操作，头插、尾插都可以通过它来实现。
bool InsertElem(DuLinkList* dps, DuList* ptr, ElemType val) { assert(dps != NULL && ptr != NULL); // 1. 创建新节点 DuList* newnode = Buynode(val); if (newnode == NULL) return false; // 2. 找到 ptr 的前驱节点 DuList* prev = ptr->prev; // 3. 连接新节点的前后指针 newnode->next = ptr; newnode->prev = prev; // 4. 更新前后节点对新节点的引用 ptr->prev = newnode; prev->next = newnode; dps->cursize++; return true; }插入过程图解：
二、头插法
// 在头结点之后插入（成为第一个实际元素） bool PushFront(DuLinkList* dps, ElemType val) { return InsertElem(dps, dps->head->next, val); }逻辑：在head->next前插入，也就是插入到第一个实际元素之前。
三、尾插法
// 在头结点之前插入（成为最后一个实际元素） bool PushBack(DuLinkList* dps, ElemType val) { return InsertElem(dps, dps->head, val); }逻辑：在head前插入。因为头结点是循环的，在头结点前插入就相当于在链表的末尾插入。
四、插入操作的对比总结
| 操作 | 调用方式 | 插入位置 |
|---|---|---|
| 头插 | InsertElem(dps, head->next, val) | 第一个实际元素之前 |
| 尾插 | InsertElem(dps, head, val) | 头结点之前（即末尾） |
| 任意位置 | InsertElem(dps, ptr, val) | 指定节点之前 |
设计优点：所有插入操作都复用同一个函数，无需为头插尾插编写重复代码。
第四部分：删除操作
一、删除指定节点（核心）
双向链表删除节点的优势在于：不需要找前驱，直接通过ptr->prev和ptr->next就能完成。
bool EraseNode(DuLinkList* dps, DuList* ptr) { assert(dps != NULL && ptr != NULL); // 不能删除头结点 if (ptr == dps->head) return false; // 1. 获取前后节点 DuList* prev = ptr->prev; DuList* next = ptr->next; // 2. 绕过 ptr，连接前后节点 prev->next = next; next->prev = prev; // 3. 释放 ptr free(ptr); ptr = NULL; dps->cursize--; return true; }删除过程图解：
二、头删
bool PopFront(DuLinkList* dps) { assert(dps != NULL); if (dps->head->next == dps->head) return false; // 空表 return EraseNode(dps, dps->head->next); }三、尾删
bool PopBack(DuLinkList* dps) { assert(dps != NULL); if (dps->head->prev == dps->head) return false; // 空表 return EraseNode(dps, dps->head->prev); }四、删除操作对比
| 链表类型 | 删除指定节点 | 需要找前驱 | 时间复杂度 |
|---|---|---|---|
| 单向链表 | 需要前驱指针 | ✅ 需要 | O(n) |
| 双向链表 | 只需节点本身 | ❌ 不需要 | O(1) |
第五部分：遍历操作
一、正向遍历（从头到尾）
void PrintDuList(const DuLinkList* dps) { assert(dps != NULL); // 从第一个实际节点开始，遍历直到回到头结点 for (DuList* p = dps->head->next; p != dps->head; p = p->next) { printf("%d ", p->val); } printf("\n"); }遍历路径：
二、反向遍历（从尾到头）
void PrintReversely(const DuLinkList* dps) { assert(dps != NULL); // 从最后一个实际节点开始，反向遍历直到回到头结点 for (DuList* p = dps->head->prev; p != dps->head; p = p->prev) { printf("%d ", p->val); } printf("\n"); }遍历路径：
这是双向链表相比单向链表的独特优势——可以反向遍历。
第六部分：双向链表 vs 单向链表对比
一、核心对比表
| 对比项 | 单向链表 | 双向链表 |
|---|---|---|
| 节点结构 | data + next | data + prev + next |
| 内存开销 | 每节点 1 个指针 | 每节点 2 个指针 |
| 正向遍历 | ✅ O(n) | ✅ O(n) |
| 反向遍历 | ❌ 不支持 | ✅ O(n) |
| 在指定节点后插入 | O(1) | O(1) |
| 在指定节点前插入 | O(n)（需找前驱） | O(1)（直接 prev） |
| 删除指定节点 | O(n)（需找前驱） | O(1)（直接 prev） |
| 实现复杂度 | 简单 | 稍复杂 |
二、何时选择双向链表
第八部分：完整实现
头文件
// Dulist.h #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int ElemType; typedef struct DuList { ElemType val; struct DuList* prev; struct DuList* next; } DuList; typedef struct DuLinkList { DuList* head; size_t cursize; } DuLinkList; // 函数声明 void InitDuLinkList(DuLinkList* dps); bool InsertElem(DuLinkList* dps, DuList* ptr, ElemType val); void PrintDuList(const DuLinkList* dps); void PrintReversely(const DuLinkList* dps); bool EraseNode(DuLinkList* dps, DuList* ptr); bool PushFront(DuLinkList* dps, ElemType val); bool PushBack(DuLinkList* dps, ElemType val); bool PopFront(DuLinkList* dps); bool PopBack(DuLinkList* dps); bool IsEmpty(const DuLinkList* dps); size_t GetSize(const DuLinkList* dps); void Clear(DuLinkList* dps); void Destroy(DuLinkList* dps);c文件
// Dulist.c #include "Dulist.h" // 创建节点 DuList* Buynode(ElemType val) { DuList* p = (DuList*)malloc(sizeof(DuList)); if (p == NULL) return NULL; p->prev = NULL; p->next = NULL; p->val = val; return p; } // 初始化 void InitDuLinkList(DuLinkList* dps) { assert(dps != NULL); DuList* head = Buynode(0); if (head == NULL) return; head->next = head; head->prev = head; dps->cursize = 0; dps->head = head; } // 判空 bool IsEmpty(const DuLinkList* dps) { assert(dps != NULL); return dps->head->next == dps->head; } // 获取大小 size_t GetSize(const DuLinkList* dps) { assert(dps != NULL); return dps->cursize; } // 核心：在指定节点前插入 bool InsertElem(DuLinkList* dps, DuList* ptr, ElemType val) { assert(dps != NULL && ptr != NULL); DuList* newnode = Buynode(val); if (newnode == NULL) return false; // 直接通过 ptr->prev 获取前驱节点（核心优势） DuList* prev = ptr->prev; newnode->next = ptr; newnode->prev = prev; ptr->prev = newnode; prev->next = newnode; dps->cursize++; return true; } // 头插 bool PushFront(DuLinkList* dps, ElemType val) { return InsertElem(dps, dps->head->next, val); } // 尾插 bool PushBack(DuLinkList* dps, ElemType val) { return InsertElem(dps, dps->head, val); } // 删除指定节点 bool EraseNode(DuLinkList* dps, DuList* ptr) { assert(dps != NULL && ptr != NULL); if (ptr == dps->head) return false; // 不能删除头结点 DuList* prev = ptr->prev; DuList* next = ptr->next; prev->next = next; next->prev = prev; free(ptr); dps->cursize--; return true; } // 头删 bool PopFront(DuLinkList* dps) { assert(dps != NULL); if (IsEmpty(dps)) return false; return EraseNode(dps, dps->head->next); } // 尾删 bool PopBack(DuLinkList* dps) { assert(dps != NULL); if (IsEmpty(dps)) return false; return EraseNode(dps, dps->head->prev); } // 正向打印 void PrintDuList(const DuLinkList* dps) { assert(dps != NULL); for (DuList* p = dps->head->next; p != dps->head; p = p->next) { printf("%d ", p->val); } printf("\n"); } // 反向打印 void PrintReversely(const DuLinkList* dps) { assert(dps != NULL); for (DuList* p = dps->head->prev; p != dps->head; p = p->prev) { printf("%d ", p->val); } printf("\n"); } // 清空（保留头结点） void Clear(DuLinkList* dps) { assert(dps != NULL); while (!IsEmpty(dps)) { EraseNode(dps, dps->head->next); } } // 销毁（释放所有节点，包括头结点） void Destroy(DuLinkList* dps) { Clear(dps); free(dps->head); dps->head = NULL; dps->cursize = 0; }总结
一、双向链表的核心原理
二、双向链表的两大优势
| 优势 | 说明 |
|---|---|
| O(1) 删除 | 不需要找前驱，直接通过ptr->prev完成 |
| 双向遍历 | 既可以正向也可以反向遍历 |
三、关键记忆点
| 操作 | 实现方式 | 时间复杂度 |
|---|---|---|
| 初始化 | 创建头结点，prev/next 指向自己 | O(1) |
| 头插 | InsertElem(dps, head->next, val) | O(1) |
| 尾插 | InsertElem(dps, head, val) | O(1) |
| 删除 | EraseNode(dps, ptr) | O(1) |
| 头删 | EraseNode(dps, head->next) | O(1) |
| 尾删 | EraseNode(dps, head->prev) | O(1) |
| 判空 | head->next == head | O(1) |
| 遍历 | for(p=head->next; p!=head; p=p->next) | O(n) |
四、一句话记忆
双向循环链表让头结点的 next 和 prev 都指向自己形成闭环，插入时通过调整前后节点的 prev/next 指针完成，删除时直接通过ptr->prev获取前驱节点，实现了 O(1) 的删除操作。
