数据结构——双向循环链表

目录

前言

一、链表的分类

二、双向循环链表

2.1 开辟新的节点

2.2 链表初始化

2.3 打印链表

2.4 链表的尾插

2.5 链表的头插

2.6 链表的尾删

2.7 链表的头删

2.8 查找链表

2.9 在pos位置之后插入数据

2.10 删除pos位置的数据

三、完整代码实现

四、顺序表和双向链表的优缺点分析

总结

---

前言

我们之前讲了顺序表和单链表，它们但是线性表的一种，今天我们来讲链表中的双向循环链表。

---

一、链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

其中分为：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构： 单链表 和 双向带头循环链表

1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结

构的子结构，如哈希图、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都

是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带

来很多优势，实现反而简单了。

二、双向循环链表

我们之前讲了单链表，今天我们来实现双向带头循环链表。

接口实现：

//list.h//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//尾插 在最后有效节点或者哨兵位前插入都是尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插 在第一个有效节点之前插入
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos后面插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的数据
void LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);

在实现代码前，我们要先用结构体来定义链表的类型。由于是循环链表，所以我们需要两个指针，分别指向节点的前驱节点和后继节点。

typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;

2.1 开辟新的节点

在初始化之前，我们来实现开辟新的节点

//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}

2.2 链表初始化

链表的初始化我们可以有两种写法：

//写法一 传入头节点的地址
void LTInit(LTNode** pphead) {assert(pphead);//哨兵位*pphead = LTBuyNode(-1);
}

//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}

我们给哨兵位的值赋为-1(任意都可以，哨兵位不作为有效数据)。

我们更推荐使用第二种方法，因为保持接口的一致性。

2.3 打印链表

如果我们往链表中插入数据，可以通过打印知道是否插入成功

void LTPrint(LTNode* phead) {assert(phead);//从哨兵位下一个节点开始打印LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

其中要注意的是循环开始是从哨兵位下一个节点开始的，结束条件是pcur走到哨兵位，即遍历了整个链表。

2.4 链表的尾插

void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//要插入的新的节点LTNode* newNode = LTBuyNode(x);//phead phead->prev newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}

尾插入一个节点，我们要改变的是哨兵位，哨兵位的前驱节点(即尾节点)，新节点三个节点的指向

2.5 链表的头插

void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//插入的新节点LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}

头插入一个节点，我们要改变的是哨兵位，哨兵位的后继节点(即第一个有效数据节点)，新节点三个节点的指向

2.6 链表的尾删

void LTPopBack(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}

尾部删除一个节点，我们要改变的是删除元素的前驱节点，哨兵位的指向，最后释放删除节点

2.7 链表的头删

void LTPopFront(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}

头部删除一个节点，我们要改变的是哨兵位，删除节点的后继节点，最后释放删除节点

2.8 查找链表

如果我们要指定位置插入或者删除，我们就要找到这个位置，我们进行链表的查找

LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

如果存在返回当前节点，不存在返回空。

2.9 在pos位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = LTBuyNode(x);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}

我们要改变新节点，pos节点，pos节点的后继节点的指向。

注意：我们要先把pos的后继节点的前驱节点指向新节点，才能把pos的后继节点指向新节点，不然反过来会找不到pos节点后继节点的位置。

2.10 删除pos位置的数据

//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

我们要改变新节点，pos节点的前驱，pos节点的后继节点的指向。

2.11 销毁链表

因为每个节点都是单独开辟的空间，所以我们要依次销毁。

//方法一
void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

//方法二
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}

与链表的初始化一样，我们有两种方法，但是我们一般选择第二种方法，为了保持接口的一致性，但是第二种方法我们要在函数外面手动给链表置为空。

三、完整代码实现

list.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//尾插 在最后有效节点或者哨兵位前插入都是尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插 在第一个有效节点之前插入
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos后面插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的数据
void LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);

list.c

#include"list.h"//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}//链表初始化
//写法一 传入头节点的地址
//void LTInit(LTNode** pphead) {
//	assert(pphead);
//   哨兵位
//	*pphead = LTBuyNode(-1);
//}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}//打印链表
void LTPrint(LTNode* phead) {assert(phead);//从哨兵位下一个节点开始打印LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾插	
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = LTBuyNode(x);//phead phead->prev newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}//头插	
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}//尾删
void LTPopBack(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = LTBuyNode(x);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁链表
/*void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}*/
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}

listest.c

#include"list.h"void Listest() {//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist=LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//1 2 3 4;LTPrint(plist);//头插/*LTPushFront(plist, 8);LTPushFront(plist, 7);LTPushFront(plist, 6);LTPushFront(plist, 5);LTPrint(plist);*///尾删/*	LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);//删除失败，链表为空//LTPopBack(plist);*///头删/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);//删除错误链表为空//LTPopFront(plist);*///查找LTNode* retFInd = LTFind(plist,1);/*if (retFInd) {printf("找到了\n");}else {printf("没找到\n");}*///在pos后面插入数据/*LTInsert(retFInd, 50);LTPrint(plist);*///删除pos位置上的数据/*LTErase(retFInd);LTPrint(plist);*///销毁链表//LTDesTroy(&plist);//保持接口一致性LTDesTroy(plist);plist = NULL;
}int main() {Listest();return 0;
}

四、顺序表和双向链表的优缺点分析

不同点	顺序表	链表（单链表）
存储空间上	物理上⼀定连续	逻辑上连续，但物理上不⼀定连续
随机访问	⽀持O(1)	不⽀持：O(N)
任意位置插⼊或删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插⼊	动态顺序表，空间不够时需要扩 容	没有容量的概念
应⽤场景	元素⾼效存储+频繁访问	任意位置插⼊和删除频繁

---

总结

上述文章我们讲了链表的双向带头循环链表的实现，希望对你有所帮助