双向链表实现-开发者社区

今天学习双向为了方便理解，放个图：

head带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”

双向链表：解决单链表的单向痛点

一、为什么需要双向链表

单链表只有一个next指针，只能从头到尾单向遍历。如果想找某个结点的前驱结点，或者想从尾部往前倒序访问，单链表就只能从头开始遍历，时间复杂度直接变成 O (N)，在频繁需要双向操作的场景里效率很低。

双向链表就是在单链表的基础上，给每个结点多加了一个指向前驱的指针，让链表可以双向行走，补上了单链表的短板。

二、双向链表的结构

1. 结点组成

每个结点包含三部分：

数据域：存储具体的业务数据
next指针：指向后一个结点
prev指针：指向前一个结点

对应的 C 语言结构体定义：

typedef int LTDataType; typedef struct ListNode { struct ListNode* next; // 指向后一个结点 struct ListNode* prev; // 指向前一个结点 LTDataType data; // 存储的数据 } LTNode;

2. 实际最常用：带头双向循环链表

工程里几乎不会用裸的双向链表，最常用的是带头双向循环链表。这里有两个核心概念：

带头（哨兵位）：在链表最前面加一个不存有效数据的 “哨兵结点”。它的存在是为了简化边界操作，不用单独处理头插、头删时的空指针问题。
循环：链表尾结点的next指向哨兵位，哨兵位的prev指向尾结点，整个链表形成一个闭环。

这种结构看起来定义更复杂，但真正写代码的时候会发现，所有位置的插入、删除逻辑都完全统一了，不用区分头部、尾部、中间情况，反而实现起来更简洁。

三、双向链表的核心操作实现

下面以带头双向循环链表为例，梳理核心接口的实现思路。

1. 初始化

初始化就是创建一个哨兵位结点，让它的next和prev都指向自己，形成一个空的循环链表。

// 创造结点 listnode* creatnode(type x) { listnode* newnode = (listnode*)malloc(sizeof(listnode)); if (newnode == NULL) { perror("newnode"); exit(1); } newnode->date=x; newnode->next = newnode->prev = newnode; return newnode; }

2. 判空

判断链表有没有有效数据，只需要看哨兵位的next是不是还指向自己。

bool LTEmpty(LTNode* phead) { return phead->next == phead; }

3. 尾部插入

因为是循环结构，尾结点天然就是哨兵位的prev，所以直接在哨兵和原尾结点之间插入新结点即可，不需要遍历找尾。

void backinsert(listnode* phead, type x) { assert(phead); listnode* newnode = creatnode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; }

头插逻辑同理，在哨兵位和第一个有效结点之间插入即可，时间复杂度都是 O (1)。

4. 指定位置之后插入

双向链表的插入核心是修改四个指针：新结点的prev和next，以及前后两个结点的next和prev。

// 在pos结点之后插入x void posback(listnode* pos, type x) { assert(pos); listnode* newnode = creatnode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; }

有了这个通用插入函数，头插、尾插都可以直接复用：头插就是在哨兵位之后插，尾插就是在哨兵位的prev之后插。

5. 删除指定结点

删除pos结点，只需要把它前后两个结点直接连起来，然后释放pos即可。

void poserase(listnode* pos) { assert(pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; }

同样，头删、尾删都可以复用这个函数，不用单独写边界逻辑。

6. 查找与遍历

查找从哨兵位的下一个结点开始遍历，直到回到哨兵位即为遍历结束。

listnode* find(listnode* phead, type x) { assert(phead); listnode* pcur = phead->next; while (pcur != phead) { if (pcur->date == x) { return pcur; } pcur = pcur->next; } return NULL; }

7. 销毁链表

遍历释放所有有效结点，最后把哨兵位也释放掉。

void destroy(listnode** phead) { listnode* pcur = (*phead)->next; while (pcur != *phead) { listnode* next = pcur->next; free(pcur); pcur = next; } free(*phead); *phead = NULL; }

四、双向链表的特点总结

优势
- 支持双向遍历，找前驱和后继结点都很方便
- 带头循环结构下，头尾的插入、删除都是 O (1)，无需遍历
- 任意位置的插入删除逻辑统一，边界情况少，代码更简洁
不足
- 每个结点多了一个prev指针，相比单链表内存开销更大
- 仍然不支持随机访问，按下标查找元素依然需要遍历，时间复杂度 O (N)
适用场景
- 需要频繁在任意位置插入、删除元素
- 需要双向遍历链表的业务场景
- 对头部、尾部操作效率要求高的场

完整代码gittee:https://gitee.com/yang-mianmian-1/doubly-linked-list