数据结构篇（四）：线性表——链表——双链表

前言上一篇讲了单链表单链表虽然解决了顺序表头部插入删除效率低的问题但它自身也有痛点不支持逆向遍历尾插尾删效率是O(N)很多操作都要先找前驱节点。为了解决这些问题带头双向循环链表登场了——它是链表结构中最复杂但实际工程中最常用的一种C STL中的list底层就是它。本文将系统讲解它的结构与实现。一、什么是双链表双链表Doubly Linked List的每个节点除了数据域还有两个指针域一个指向前一个节点prev一个指向后一个节点next。本文实现的是带头双向循环链表它有三个关键特征带头有一个不存储有效数据的哨兵头节点哨兵位头节点永远存在即使链表为空双向每个节点既能找到前驱也能找到后继循环最后一个节点的next指向头节点头节点的prev指向最后一个节点形成一个环。带头双向循环链表看起来结构复杂但正因为头节点永远存在所以插入删除时不需要对链表是否为空做特殊判断代码反而比单链表更简单统一这是它的一大优势。二、双链表的结构定义​typedef int LTDataType; typedef struct ListNode { LTDataType data; // 数据域 struct ListNode* prev; // 指向前一个节点 struct ListNode* next; // 指向后一个节点 } ListNode;由于是带头循环结构整个链表只需要一个头节点指针即可代表不再需要像单链表那样用二级指针传参。三、双链表的基本操作3.1 创建新节点ListNode* BuyListNode(LTDataType x) { ListNode* newNode (ListNode*)malloc(sizeof(ListNode)); if (newNode NULL) { perror(malloc fail); exit(-1); } newNode-data x; newNode-prev NULL; newNode-next NULL; return newNode; }3.2 初始化创建带头节点的空链表ListNode* ListInit() { ListNode* head BuyListNode(0); // 哨兵位data值无意义 head-next head; head-prev head; return head; }3.3 头插void ListPushFront(ListNode* phead, LTDataType x) { assert(phead ! NULL); ListNode* newNode BuyListNode(x); ListNode* first phead-next; // 新节点插入头节点和原第一个节点之间 phead-next newNode; newNode-prev phead; newNode-next first; first-prev newNode; }3.4 头删void ListPopFront(ListNode* phead) { assert(phead ! NULL); assert(phead-next ! phead); // 链表不能为空 ListNode* first phead-next; ListNode* second first-next; phead-next second; second-prev phead; free(first); }3.5 尾插得益于循环结构phead-prev永远指向最后一个节点所以尾插不需要遍历直接是O(1)——这是双链表相比单链表最大的效率提升。void ListPushBack(ListNode* phead, LTDataType x) { assert(phead ! NULL); ListNode* newNode BuyListNode(x); ListNode* last phead-prev; last-next newNode; newNode-prev last; newNode-next phead; phead-prev newNode; }3.6 尾删void ListPopBack(ListNode* phead) { assert(phead ! NULL); assert(phead-next ! phead); ListNode* last phead-prev; ListNode* newLast last-prev; newLast-next phead; phead-prev newLast; free(last); }3.7 查找ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead ! NULL); ListNode* cur phead-next; while (cur ! phead) { if (cur-data x) { return cur; } cur cur-next; } return NULL; // 没找到 }3.8 在指定位置之前/之后插入有了prev指针双链表可以在O(1)时间内完成任意已知位置的插入不再需要像单链表那样遍历找前驱。// 在pos之前插入xO(1) void ListInsert(ListNode* pos, LTDataType x) { assert(pos ! NULL); ListNode* newNode BuyListNode(x); ListNode* prev pos-prev; prev-next newNode; newNode-prev prev; newNode-next pos; pos-prev newNode; } // 在pos之后插入xO(1) void ListInsertAfter(ListNode* pos, LTDataType x) { assert(pos ! NULL); ListNode* newNode BuyListNode(x); ListNode* next pos-next; pos-next newNode; newNode-prev pos; newNode-next next; next-prev newNode; }3.9 删除指定位置节点void ListErase(ListNode* pos) { assert(pos ! NULL); ListNode* prev pos-prev; ListNode* next pos-next; prev-next next; next-prev prev; free(pos); }3.10 打印链表void ListPrint(ListNode* phead) { assert(phead ! NULL); printf(head - ); ListNode* cur phead-next; while (cur ! phead) { printf(%d - , cur-data); cur cur-next; } printf(head\n); }3.11 销毁链表void ListDestroy(ListNode* phead) { assert(phead ! NULL); ListNode* cur phead-next; while (cur ! phead) { ListNode* next cur-next; free(cur); cur next; } free(phead); // 别忘了释放头节点自己 }四、完整测试代码int main() { ListNode* plist ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPrint(plist); // head - 1 - 2 - 3 - head ListPushFront(plist, 0); ListPrint(plist); // head - 0 - 1 - 2 - 3 - head ListNode* pos ListFind(plist, 2); if (pos) { ListInsert(pos, 100); } ListPrint(plist); // head - 0 - 1 - 100 - 2 - 3 - head ListPopFront(plist); ListPopBack(plist); ListPrint(plist); // head - 1 - 100 - 2 - head ListDestroy(plist); return 0; }五、时间复杂度分析操作时间复杂度说明头插/头删O(1)直接操作头节点尾插/尾删O(1)有prev指针无需遍历指定位置插入/删除O(1)已知位置即可直接操作查找O(N)仍需遍历随机访问下标O(N)不支持真正的随机访问可以看到除了查找和随机访问双链表的增删操作全部是O(1)这是它相比单链表和顺序表最大的优势。六、双链表 vs 单链表 vs 顺序表特性顺序表单链表双链表带头循环存储方式物理地址连续物理地址不连续物理地址不连续随机访问O(1)O(N)O(N)头部插入删除O(N)O(1)O(1)尾部插入删除O(1)均摊O(N)O(1)任意位置插入删除O(N)O(N)需找前驱O(1)已知位置逆向遍历支持不支持支持空指针判断不需要需要频繁判断头节点恒存在几乎不需要空间开销可能有扩容冗余一个指针两个指针可以看出双链表几乎在所有增删操作上都做到了O(1)代价是每个节点多了一个prev指针的空间开销空间换时间以及实现相对更复杂。这也是为什么STL选择用带头双向循环链表实现list——用少量的额外空间换取了全方位的高效增删。七、总结双链表尤其是带头双向循环链表是链表结构的完全体因为带头插入删除不用特判链表是否为空因为双向可以O(1)找到任意节点的前驱也支持逆向遍历因为循环phead-prev天然就是尾节点尾插尾删也能做到O(1)。理解了双链表的实现原理再回头看STL的list、unordered_map的哈希桶等结构会更加得心应手。链表和顺序表是线性表的两种典型实现方式二者各有优劣没有绝对的孰优孰劣需要根据实际的业务场景是否频繁随机访问、是否频繁增删、数据规模是否已知来做选择。理解透单链表的指针操作尤其是二级指针的使用、边界条件的处理是后续学习双向链表、栈、队列乃至STL中list容器的重要基础。如果这篇文章对你有帮助欢迎点赞收藏后续会继续更新栈、队列、二叉树等数据结构内容