跳到主要内容数据结构之带头双向循环链表 | 极客日志C算法
数据结构之带头双向循环链表
本文详细讲解了带头双向循环链表的原理与 C 语言实现。内容包括链表节点结构定义、初始化、增删改查（尾插、尾删、头插、头删、查找、插入、删除）、打印及销毁等核心接口的代码编写与逻辑解析，并对比了顺序表与链表的特点。
1 双向循环链表的介绍
有了单链表的基础，要实现这个双向循环带头链表其实并不难。下面我们先来了解一下什么是双向循环带头链表。
这就是双向循环带头链表的结构图，可以很清晰的看到，这个链表需要两个指针，一个指向后继结点，一个指向前驱节点，其次还需要一个头结点。只是这个头结点并不需要存储有效数据。
2 双向循环链表的实现
2.1 双向循环带头链表的定义
typedef int LDataType;
typedef struct ListNode{
LDataType val;
struct ListNode* next;
struct ListNode* prev;
} LTNode;
2.2 双向循环带头链表的接口
LTNode* ListInit();
void ListPrint(LTNode* plist);
void ListPushBack(LTNode* phead, LDataType x);
void ListPopBack(LTNode* phead);
void ListPushFront(LTNode* phead, LDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LDataType x);
;
;
;
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
void
ListInsert
(LTNode* pos, LDataType x)
void
ListErase
(LTNode* pos)
void
ListDestroy
(LTNode* phead)
2.2.1 初始化链表
LTNode* ListInit(){
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if(phead == NULL){
printf("malloc fail\n");
exit(-1);
}
phead->next = phead;
phead->prev = phead;
return phead;
}
2.2.2 创建新节点
LTNode* BuyListNode(LDataType x){
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if(newnode == NULL){
printf("malloc fail\n");
exit(-1);
}
newnode->val = x;
newnode->prev = newnode->next = NULL;
return newnode;
}
2.2.3 链表尾插
void ListPushBack(LTNode* phead, LDataType x){
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
通过 phead->prev 就可以找到链表的尾节点，增加的节点 newnode->prev 应该链接链表尾节点，链表的尾节点链接 newnode, newnode->next 应该链接链表的头结点，链表的头结点的 prev 保存 newnode 的地址，使 newnode 成为链表新的尾节点。
2.2.4 链表头插
void ListPushFront(LTNode* phead, LDataType x){
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* pheadNext = phead->next;
phead->next = newnode;
newnode->prev = phead;
pheadNext->prev = newnode;
newnode->next = pheadNext;
}
先创建一个指针指向头结点的后继结点，再让 newnode->next 保存该节点的地址，该节点的 prev 保存 newnode 的地址，phead->next 保存 newnode 的地址，newnode->prev 保存头结点的地址。
2.2.5 链表尾删
void ListPopBack(LTNode* phead){
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
}
通过 phead->prev 找到链表尾节点，再通过尾节点的 prev 找到尾节点的前驱节点，让该前驱节点的 next 指向 phead, phead->prev 指向该前驱节点，最后释放尾节点。
2.2.6 链表头删
void ListPopFront(LTNode* phead){
assert(phead);
assert(phead->next != phead);
LTNode* head = phead->next;
LTNode* next = head->next;
next->prev = phead;
phead->next = next;
free(head);
}
首先通过 phead->next 找到链表头结点的后继结点，再通过该后继结点找到下一个节点，使该节点的 prev 保存头结点的地址，头结点的 next 保存该节点的地址，最后释放该后继结点。
2.2.7 链表的查找
LTNode* ListFind(LTNode* phead, LDataType x){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
if(cur->val == x){
return cur;
}else{
cur = cur->next;
}
}
return NULL;
}
从头结点的后继结点开始遍历查找，找到了就返回该节点的地址，找不到返回 NULL（当再一次遍历到头结点时，说明未找到）。
2.2.8 从 pos 位置之前插入
void ListInsert(LTNode* pos, LDataType x){
assert(pos != NULL);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
首先找到 pos 位置的前驱节点，再让 newnode->prev 指向该前驱节点，该前驱节点的 next 指向 newnode, pos->prev 指向 newnode, newnode->next 指向 pos。
2.2.9 删除 pos 位置
void ListErase(LTNode* pos){
assert(pos != NULL);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
找到 pos 位置的前驱节点和后继结点，让该前驱节点的 next 指向该后继结点，该后继结点的 prev 指向该前驱节点。
2.2.10 链表的打印
void ListPrint(LTNode* phead){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
从头结点的后继结点开始遍历链表，当节点不是头结点时就打印该节点的值。
2.2.11 销毁链表
void ListDestroy(LTNode* phead){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
LTNode* tmp = cur;
cur = cur->next;
free(tmp);
tmp = NULL;
}
cur = NULL;
phead = NULL;
}
从头结点的后继结点开始销毁，先记录该后继结点的下一个节点，再销毁该后继结点。重复上述操作，直到再一次回到头结点的位置，此时销毁该头结点。
3 完整代码的实现
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LDataType;
typedef struct ListNode{
LDataType val;
struct ListNode* next;
struct ListNode* prev;
} LTNode;
LTNode* ListInit();
void ListPrint(LTNode* plist);
void ListPushBack(LTNode* phead, LDataType x);
void ListPopBack(LTNode* phead);
void ListPushFront(LTNode* phead, LDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LDataType x);
void ListInsert(LTNode* pos, LDataType x);
void ListErase(LTNode* pos);
void ListDestroy(LTNode* phead);
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
LTNode* ListInit(){
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if(phead == NULL){
printf("malloc fail\n");
exit(-1);
}
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListPrint(LTNode* phead){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
void ListDestroy(LTNode* phead){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
LTNode* tmp = cur;
cur = cur->next;
free(tmp);
tmp = NULL;
}
cur = NULL;
phead = NULL;
}
LTNode* BuyListNode(LDataType x){
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if(newnode == NULL){
printf("malloc fail\n");
exit(-1);
}
newnode->val = x;
newnode->prev = newnode->next = NULL;
return newnode;
}
void ListPushBack(LTNode* phead, LDataType x){
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
void ListPopBack(LTNode* phead){
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
}
void ListPushFront(LTNode* phead, LDataType x){
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* pheadNext = phead->next;
phead->next = newnode;
newnode->prev = phead;
pheadNext->prev = newnode;
newnode->next = pheadNext;
}
void ListPopFront(LTNode* phead){
assert(phead);
assert(phead->next != phead);
LTNode* head = phead->next;
LTNode* next = head->next;
next->prev = phead;
phead->next = next;
free(head);
}
LTNode* ListFind(LTNode* phead, LDataType x){
assert(phead);
LTNode* cur = phead->next;
while(cur != phead){
if(cur->val == x){
return cur;
}else{
cur = cur->next;
}
}
return NULL;
}
void ListInsert(LTNode* pos, LDataType x){
assert(pos != NULL);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(LTNode* pos){
assert(pos != NULL);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
void ListTest1(){
LTNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
ListPrint(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPrint(plist);
ListPushFront(plist, 6);
ListPushFront(plist, 7);
ListPushFront(plist, 8);
ListPushFront(plist, 9);
ListPushFront(plist, 10);
ListPrint(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPrint(plist);
LTNode* pos = ListFind(plist, 2);
if(NULL != pos){
printf("找到了\n");
}else{
printf("找不到\n");
}
ListInsert(pos, 10);
ListPrint(plist);
pos = ListFind(plist, 1);
ListErase(pos);
ListPrint(plist);
ListDestroy(plist);
plist = NULL;
}
int main(){
ListTest1();
return 0;
}
4 顺序表与链表的对比
| 特性 | 顺序表 | 链表 |
|---|
| 内存分配 | 连续空间 | 非连续空间 |
| 随机访问 | O(1) | O(n) |
| 插入删除 | 需移动元素 | 只需修改指针 |
| 扩容成本 | 高 | 低 |
