数据结构之双链表

本篇目标1. 学会关于双链表的相关操作2. 了解链表和顺序表的区别和优点一、双链表接口实现1. 双向链表的结构• 单链表的结点中保存了指向后继结点的地址所以单链表中找当前结点的后继结点很容易但要获取当前结点的前驱结点就很麻烦就只能从头开始往后遍历获取时间复杂度为 O(n)所以单链表中只有当前结点的指针 pos 时没有头指针想要在 pos 之前插入结点和删除 pos 位置结点都是无法实现的。• 双向链表相比单链表最大的特征是每个结点中多了一个前驱指针一些场景需要获取当前结点前驱结点的场景中就需要用双链表实现如倒着遍历、删除当前结点、在当前结点前插入结点等。• 双向链表的一些不足是找尾结点依旧不是很方便另外呢头尾插入删除考虑的边界依旧比较多。后面的带头双向循环链表可以很好地解决这个问题。代码块typedef int DCLDataType; // 双向循环链表结点 typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 } DCListNode;如图• 实践中链表最常见的操作并非在第 i 个位序插入删除数据而是在头尾插入删除数据前面的单链表头插头删效率高可以做到时间复杂度 O(1)但是尾插尾删需要找到尾结点时间复杂度为 O(N)也就是说单链表结构适合头插头删这个在后面单链表作为复杂数据结构的子结构中可以看到主要就使用它的头插头删。• 双向链表头插头删效率高确定某个结点位置以后插入删除效率也很高均可以做到时间复杂度 O(1)但是同样尾插尾删需要增加一个尾指针相对麻烦所以这里我们引用一个新的结构循环链表可以解决这里的问题。如图• 下图是单向循环链表和双向循环链表单向循环链表就是让尾结点的 next 指向头结点双向循环链表就是尾结点的 next 指向头结点同时头结点的 prev 指向尾结点。• 实践中双向循环链表非常实用C 标准库STL中 list 就是使用的这个结构实现因为它可以通过头结点的 prev 指针找到尾结点轻松实现尾插尾删。也就是说这个结构头尾插入删除效率都是 O(1)确定某个结点位置以后的插入删除也是。下面我们会重点实现这个结构。2. 接口函数定义#pragma once #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; // 双向循环链表结点 typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 } DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表中位序为 i 的结点 DCListNode* DCListGetElem(DCListNode* L, int i); // 在 pos 位置后插入值为 x 的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除 pos 位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);我们实现的是带头双向链表。2.1. 初始化初始化时我们需要先创建一个头节点并且前后指针要指向自己。// 创建一个结点 DCListNode* BuyDCListNode(DCLDataType x) { DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (newNode NULL) { perror(malloc failed); return NULL; } newNode-data x; newNode-prev NULL; newNode-next NULL; return newNode; } // 链表初始化 DCListNode* DCListInit() { // 创建哨兵头结点 DCListNode* head BuyDCListNode(-1); if (head NULL) { return NULL; } // 空链表中头结点的前驱和后继都指向自己 head-next head; head-prev head; return head; }2.2. 打印链表打印双链表其实与单链表的过程差不多。// 打印链表中的元素 void DCListPrint(DCListNode* L) { assert(L ! NULL); DCListNode* cur L-next; printf(头结点-); while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(头结点\n); }流程图2.3. 销毁链表销毁双链表其实与单链表的过程差不多但是要记得结尾删除头节点。// 销毁链表 void DCListDestroy(DCListNode* L) { assert(L ! NULL); DCListNode* cur L-next; // 依次释放所有数据结点 while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } // 最后释放哨兵头结点 free(L); }2.4. 查找节点查找节点时我们需要返回这个节点这是为了方便后面增删操作。// 获取链表中位序为 i 的结点 // i 从 0 开始i 0 表示第一个数据结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L ! NULL); assert(i 0); DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } // 如果 cur L说明 i 超出了链表范围 assert(cur ! L); return cur; }流程图2.5. 插入• 在 pos 结点之后插入一个新结点 newNode这里要改四个指针的链接关系要注意的是一定不能先动 pos-next newNode否则就会找不到 pos 的后继结点。建议把 pos-next newNode; 放到最后就不会出乱子。• pos 可以指向任意结点包括头结点不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表非循环要注意的是pos 为尾结点时需要考虑 pos-next 为空的情况并且 pos 不能为头结点。如图// 在 pos 结点后插入值为 x 的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos ! NULL); DCListNode* newNode BuyDCListNode(x); assert(newNode ! NULL); DCListNode* next pos-next; // 将新结点连接到 pos 和 next 之间 pos-next newNode; newNode-prev pos; newNode-next next; next-prev newNode; }有了这个插入那么头插和尾插就变得比较简单了如代码// 头插 void DCListPushFront(DCListNode* L, DCLDataType x) { assert(L ! NULL); DCListInsert(L, x); } // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x) { assert(L ! NULL); DCListInsert(L-prev, x); }2.6. 删除• 这里改动两个指针链接关系即可注意一定要画图捋清楚指针间的关系否则很容易乱这两个链接指针关系没有前后顺序。• pos 可以指向除了头结点以外的任意结点不需要考虑 pos 前一个或者后一个为空的情况。如果是双向链表非循环要注意的是 pos 为尾结点时需要考虑 pos-next 为空的情况。// 删除 pos 结点 // 注意pos 必须是有效数据结点不能是哨兵头结点 void DCListDelete(DCListNode* pos) { assert(pos ! NULL); assert(pos-prev ! NULL); assert(pos-next ! NULL); DCListNode* prev pos-prev; DCListNode* next pos-next; // 将 pos 的前驱和后继直接连接 prev-next next; next-prev prev; // 避免留下无效连接 pos-prev NULL; pos-next NULL; free(pos); }有了这个删除那么头删和尾删就变得比较简单了如代码// 头删 void DCListPopFront(DCListNode* L) { assert(L ! NULL); // 空链表不执行删除 if (L-next L) { return; } DCListDelete(L-next); } // 尾删 void DCListPopBack(DCListNode* L) { assert(L ! NULL); // 空链表不执行删除 if (L-prev L) { return; } DCListDelete(L-prev); }2.7. 测试代码#include DCList.h int main() { // 初始化链表 DCListNode* L DCListInit(); // 头插 DCListInsert(L, 1); DCListInsert(L, 2); DCListInsert(L, 3); DCListInsert(L, 4); DCListPrint(L); // 尾插 DCListInsert(L-prev, 5); DCListInsert(L-prev, 6); DCListInsert(L-prev, 7); DCListInsert(L-prev, 8); DCListPrint(L); // 头删 DCListDelete(L-next); DCListDelete(L-next); DCListPrint(L); // 尾删 DCListDelete(L-prev); DCListDelete(L-prev); DCListPrint(L); // 中间插入 DCListInsert(DCListGetElem(L, 2), 100); DCListPrint(L); // 中间删除 DCListDelete(DCListGetElem(L, 2)); DCListPrint(L); // 销毁链表 DCListDestroy(L); return 0; }二、顺序表和链表的比较1. 对比顺序表和链表都属于线性表它们的逻辑结构都是线性结构。二者最大的区别在于存储结构也就是物理结构不同。顺序表使用一段连续的物理空间存储数据链表中的结点可以分散存储在任意位置各个结点通过指针连接起来。1.顺序表优点支持下标随机访问访问任意位置元素的时间复杂度为O(1)。适合排序、二分查找、堆和优先级队列等操作。数据连续存储CPU 缓存命中率较高。通常不会产生大量零散的内存碎片。缺点在中间或头部插入、删除数据时需要移动后面的元素时间复杂度通常为O(N)。只有尾插和尾删在不扩容等理想情况下时间复杂度可以达到O(1)。空间不足时需要扩容扩容时通常需要申请新空间并复制原有数据。扩容后可能会存在一定的空间浪费。2.链表优点按需申请和释放结点空间不需要像顺序表一样整体扩容。在已经确定插入或删除位置的情况下双向链表可以在O(1)时间内完成插入和删除。插入和删除时不需要整体移动其他元素。缺点不支持下标随机访问访问第i个结点通常需要从头遍历时间复杂度为O(N)。每个结点需要额外保存指针会增加空间开销。结点在内存中不连续CPU 缓存命中率通常低于顺序表。频繁申请和释放小块内存可能产生内存碎片。需要特别注意一句链表的插入和删除是O(1)前提是已经找到了对应结点。对比项顺序表链表物理存储连续不连续随机访问O(1)O(N)中间插入删除O(N)已知位置时O(1)扩容需要不需要整体扩容额外空间较少需要保存指针缓存命中率较高较低总结大量随机访问、排序和尾插时更适合顺序表频繁在已知位置插入和删除时更适合链表。