文章目录
- 前言
- 一、双向链表的基本概念
- 1.1 链表与数组的对比
- 1.2 双向链表的结构特点
- 二、双向链表的实现(加注释)
- 三、性能分析及常见问题
- 3.1 时间复杂度比较
- 3.2 内存管理与泄露
- 3.3 常见调试技巧和注意事项
- 四、顺序表与双向链表的优缺点对比
- 总结
前言
在 C 语言中，数据结构的选择直接影响代码的性能与灵活性。顺序表（数组）虽然支持随机访问，但在频繁的插入和删除场景下效率较低；而链表结构则正好弥补了这一不足。
尤其是 双向链表 不仅具备链表灵活插入删除的优点，还支持双向遍历，使得在某些应用场景下（如浏览器的前进、后退操作、LRU 缓存实现等）具有独特优势。
一、双向链表的基本概念
1.1 链表与数组的对比
-
数组（顺序表）：
- 存储在连续的内存空间中，支持快速随机访问（O(1)）。
- 插入和删除操作需要大量元素移动（O(n)）。
-
链表：
- 内存不一定连续，每个结点通过指针连接。
- 插入和删除操作只需修改指针，效率较高（O(1)），但随机访问效率较低（O(n)）。
1.2 双向链表的结构特点
与单向链表相比，双向链表的每个结点包含两个指针：
- prev：指向前驱结点
- next：指向后继结点
这使得双向链表可以双向遍历，即从任一结点都可以向前或向后查找。这种设计在很多应用中非常有用。
二、双向链表的实现(加注释)
Doublylinkedlists.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int doutype;//定义双链表
typedef struct DouLlist
{doutype date;struct DouLlist* pre;struct DouLlist* next;
}DouNode;//建立节点
DouNode* douBuyNode();//初始化双链表
void InitDou();//尾插
void pushBack(DouNode* phead, doutype x);//头插
void pushFront(DouNode* phead, doutype x);//尾删
void popBack(DouNode** pphead);//头删
void popFront(DouNode** pphead);//查找
DouNode* findDou(DouNode* phead, doutype x);//在指定位置之后插入
void pushPos(DouNode* phead, DouNode* pos, doutype x);//删除指定位置的数据
void popPos(DouNode* pos);//销毁
void destroy(DouNode** pphead);//打印
void printDou(DouNode* phead);Doublylinkedlists.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Doublylinkedlists.h" // 包含双向链表相关的头文件/** 函数：douBuyNode* 作用：创建一个新的双向链表结点，并初始化它的数值和指针* 参数：x —— 结点中存储的数据，类型为 doutype* 返回值：新创建的结点指针*/
DouNode* douBuyNode(doutype x)
{DouNode* newNode = { 0 }; // 初始化新结点指针变量（此处可省略，后续会重新赋值）// 分配内存，申请一个 DouNode 大小的空间DouNode* Node = (DouNode*)malloc(sizeof(DouNode));// 检查内存分配是否成功if (Node == NULL){perror("malloc"); // 输出错误信息exit(1); // 退出程序}newNode = Node; // 将分配到的内存地址赋给 newNodenewNode->date = x; // 初始化数据域，存储传入的数值 xnewNode->next = NULL; // 初始化后继指针为空newNode->pre = NULL; // 初始化前驱指针为空return newNode; // 返回新创建的结点指针
}/** 函数：InitDou* 作用：初始化一个空的循环双向链表，并带有头结点（哨兵结点）* 参数：newNode —— 指向链表头结点指针的地址* 说明：头结点的 date 值通常为 0，且其 next 和 pre 都指向自身，表示链表为空时的循环结构*/
void InitDou(DouNode** newNode)
{*newNode = douBuyNode(0); // 创建头结点，数据为 0(*newNode)->next = *newNode; // 头结点的 next 指向自身，形成循环(*newNode)->pre = *newNode; // 头结点的 pre 也指向自身
}/** 函数：pushBack* 作用：在循环双向链表尾部添加一个新结点* 参数：* phead —— 链表的头结点（哨兵结点）* x —— 新结点中的数据* 说明：* - phead->pre 指向链表最后一个有效结点* - 插入新结点后，新结点的 next 指向头结点 phead*/
void pushBack(DouNode* phead, doutype x)
{assert(phead); // 保证链表非空DouNode* newNode = douBuyNode(x); // 创建新结点，存储数据 x// 将新结点插入链表尾部：newNode->pre = phead->pre; // 新结点的前驱指向原链表最后一个结点newNode->next = phead; // 新结点的后继指向头结点newNode->pre->next = newNode; // 原链表最后一个结点的 next 指向新结点phead->pre = newNode; // 更新头结点的 pre 指针，指向新结点
}/** 函数：pushFront* 作用：在循环双向链表头部添加一个新结点（插入到头结点后面）* 参数：* phead —— 链表的头结点（哨兵结点）* x —— 新结点中的数据* 说明：* - 头结点后面的结点为链表第一个有效结点*/
void pushFront(DouNode* phead, doutype x)
{assert(phead); // 保证链表非空DouNode* newNode = douBuyNode(x); // 创建新结点，存储数据 xnewNode->pre = phead; // 新结点的前驱指向头结点newNode->next = phead->next; // 新结点的后继指向原第一个结点phead->next->pre = newNode; // 原第一个结点的前驱更新为新结点phead->next = newNode; // 头结点的 next 指向新结点，即成为新的第一个有效结点
}/** 函数：printDou* 作用：输出循环双向链表中的所有有效结点数据* 参数：* phead —— 链表的头结点（哨兵结点）* 说明：* - 从头结点的 next 开始依次打印，直到再次回到头结点为止*/
void printDou(DouNode* phead)
{DouNode* cur = phead; // 使用 cur 作为遍历指针while (cur->next != phead) // 遍历直到回到头结点{printf("%d->", cur->next->date); // 打印有效结点的数据（跳过头结点）cur = cur->next; // 移动到下一个结点}printf("\n"); // 输出换行符
}/** 函数：popBack* 作用：删除循环双向链表尾部的一个有效结点* 参数：* pphead —— 指向头结点指针的地址* 说明：* - 若链表只有头结点，则认为链表为空，输出错误信息*/
void popBack(DouNode** pphead)
{assert(pphead && *pphead); // 保证链表指针有效DouNode* cur = (*pphead)->pre; // 获取链表最后一个有效结点（头结点的前驱）// 如果最后一个结点正好是头结点，则链表为空if (cur == *pphead){perror("双链表为空");return;}// 重新链接，将倒数第二个结点与头结点相连cur->pre->next = *pphead;(*pphead)->pre = cur->pre;free(cur); // 释放删除的结点内存cur = NULL; // 将指针置空，防止野指针
}/** 函数：popFront* 作用：删除循环双向链表头部的一个有效结点（头结点后面的结点）* 参数：* pphead —— 指向头结点指针的地址* 说明：* - 如果链表只有头结点，则认为链表为空，输出错误信息*/
void popFront(DouNode** pphead)
{assert(pphead && *pphead); // 保证链表指针有效DouNode* cur = (*pphead)->next; // 获取第一个有效结点（头结点的 next）// 如果第一个结点是头结点，说明链表为空if (cur == *pphead){perror("双链表为空");return;}// 将头结点与第二个有效结点相连(*pphead)->next = cur->next;cur->next->pre = *pphead;free(cur); // 释放删除结点内存cur = NULL; // 避免悬挂指针
}/** 函数：findDou* 作用：在循环双向链表中查找数据等于 x 的结点* 参数：* phead —— 链表的头结点（哨兵结点）* x —— 要查找的数据* 返回值：* 找到则返回对应的结点地址，否则返回 -1（此处返回 -1 并不合适，一般应返回 NULL）*/
DouNode* findDou(DouNode* phead, doutype x)
{assert(phead); // 保证链表非空DouNode* Node = phead->next; // 从第一个有效结点开始查找while (Node != phead) // 遍历整个链表直到回到头结点{if (Node->date == x) // 找到数据匹配的结点时返回该结点{return Node;}Node = Node->next; // 移动到下一个结点}return -1; // 没找到返回 -1（建议改为返回 NULL 表示未找到）
}/** 函数：pushPos* 作用：在指定结点 pos 之后插入一个数据为 x 的新结点* 参数：* phead —— 链表的头结点（用来保证链表有效）* pos —— 插入新结点的位置，插入在 pos 后面* x —— 新结点中要存储的数据*/
void pushPos(DouNode* phead, DouNode* pos, doutype x)
{assert(phead); // 保证链表有效DouNode* newNode = douBuyNode(x); // 创建新结点newNode->pre = pos; // 新结点的前驱指向 posnewNode->next = pos->next; // 新结点的后继指向 pos 的下一个结点pos->next->pre = newNode; // pos 后一个结点的前驱指针更新为新结点pos->next = newNode; // pos 的 next 指针指向新结点
}/** 函数：popPos* 作用：删除指定的结点 pos* 参数：* pos —— 要删除的结点* 说明：* - 删除前，将 pos 的前驱与后继链接起来，再释放 pos 的内存*/
void popPos(DouNode* pos)
{assert(pos); // 保证 pos 非空DouNode* node1 = pos->pre; // pos 的前一个结点DouNode* node2 = pos->next; // pos 的后一个结点node1->next = node2; // 前一个结点的 next 指向 pos 的后一个结点node2->pre = node1; // 后一个结点的 pre 指向 pos 的前一个结点free(pos); // 释放 pos 的内存pos = NULL; // 将 pos 置空，防止野指针（函数内变量，实际调用者的指针不变）
}/** 函数：destroyDou* 作用：销毁整个循环双向链表，释放所有结点内存* 参数：* pphead —— 指向头结点指针的地址* 说明：* - 从头结点的 next 开始依次释放，直到回到头结点*/
void destroyDou(DouNode** pphead)
{assert(pphead && *pphead); // 保证链表指针有效DouNode* Node = (*pphead)->next; // 从第一个有效结点开始DouNode* Cur = Node->next; // 保存下一个结点地址，便于释放当前结点后继续遍历while (Node != *pphead) // 遍历所有非头结点{free(Node); // 释放当前结点内存Node = NULL; // 将当前指针置空（便于调试，实际已释放内存）Node = Cur; // 移动到下一个结点if (Node == *pphead) // 如果回到了头结点，则所有有效结点均已释放{printf("双链表已销毁完毕\n");// 重置头结点的指针，指向自身，保持循环结构不变Node->next = Node;Node->pre = Node;return;}Cur = Cur->next; // 更新 Cur 指向下一个结点}
}三、性能分析及常见问题
3.1 时间复杂度比较
-
插入与删除：
双向链表插入或删除一个结点（在已定位结点的情况下）时间复杂度为 O(1)。但如果需要定位待删除或插入位置，则可能需要 O(n) 时间遍历查找。 -
遍历：
无论正向还是反向遍历都需要 O(n) 的时间。 -
查找：
由于链表不支持随机访问，按照下标查找时间复杂度为 O(n)。
3.2 内存管理与泄露
- 每次调用
malloc都必须配合free释放内存。 - 尤其在删除操作中或程序结束时，务必调用
freeList释放所有分配内存。 - 检查
malloc的返回值，可避免因内存不足而产生异常。
3.3 常见调试技巧和注意事项
- 调试小技巧：在关键操作前后打印链表状态，有助于发现指针更新错误。
- 边界条件：特别注意空链表、单个结点链表、头/尾结点操作时的特殊处理。
- 内存泄漏检测：可以使用工具（如 Valgrind）检测程序是否存在内存泄露问题。
四、顺序表与双向链表的优缺点对比
| 特性 | 顺序表（数组） | 双向链表 |
|---|---|---|
| 内存结构 | 连续内存，利用率高 | 非连续内存，需要额外空间存储指针 |
| 插入/删除效率 | 低（插入或删除时需移动大量元素） | 高（操作时只需修改相邻结点的指针） |
| 随机访问 | 高效，支持直接下标访问 | 低效，只能依次遍历查找 |
| 动态扩展 | 需要预分配或动态扩容 | 每次插入动态分配内存，扩展灵活 |
| 双向遍历 | 不支持 | 支持正向和反向遍历 |
实际应用中：
- 当数据量固定、查找频繁时推荐使用顺序表。
- 当数据频繁增删、需要双向遍历时双向链表更合适。
总结
本文详细介绍了 C 语言中双向链表的基本概念与实现方法，从结点结构定义、各项操作（创建、插入、删除、遍历）到内存释放、性能分析均做了深入解析。
学会双向链表不仅能帮助你理解链表的底层实现逻辑，更是学习其他复杂数据结构（如双向循环链表、双端队列等）的基础。
提示：
- 在编码过程中，多结合图示和调试输出帮助理解指针关系；
- 注意边界条件和内存管理，掌握调试工具（如 Valgrind）以确保程序稳定性。
- 可尝试扩展，如增加按位置插入或删除的操作、构造双向循环链表，进一步加深理解。
