双向链表：高效遍历与插入删除

引言在前面的文章中我们详细讲解了单向链表。单向链表虽然结构简单但存在一个天然缺陷只能单向遍历无法从后往前访问。这在某些场景下如需要双向查找、在任意位置前后插入删除会造成不便。双向链表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 nextdata 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 headO(1)遍历for(phead-next; p!head; pp-next)O(n)四、一句话记忆双向循环链表让头结点的 next 和 prev 都指向自己形成闭环插入时通过调整前后节点的 prev/next 指针完成删除时直接通过ptr-prev获取前驱节点实现了 O(1) 的删除操作。