目录
前言
在前几章实现了用C语言实现无哨兵位单向不循环链表，以及一些单链表的oj题
数据结构 ——— C语言实现无哨兵位单向不循环链表-CSDN博客
数据结构 ——— 单链表oj题：相交链表（链表的共节点）-CSDN博客
数据结构 ——— 单链表oj题：环状链表（判断链表是否带环）-CSDN博客
接下来要学习的是带哨兵位双向循环链表的概念及其实现
无哨兵位单向不循环链表的缺陷
- 在实现 无哨兵位单向不循环链表 时，可以发现对其尾插节点的时间复杂度为：O(N) ；因为要从头节点遍历，找到原尾节点，才能进行插入节点
- 在查找当前节点的前一个节点时，也需要从头节点开始遍历才能查找到
- 且在没有哨兵位的情况下，在进行插入时，都需要判断链表的头节点是否为 NULL
所以给出了 带哨兵位双向循环链表，可以有效的解决以上问题
带哨兵位双向循环链表的概念
- 带哨兵位可以有效的避免对头节点为 NULL 时的判断，可以直接插入或者删除
- 双向的好处在于对当前节点的前一个节点或者后一个节点的查找时间复杂度为：O(1)
- 链表循环的好处在于对于尾插的时间复杂度为：O(1)
带哨兵位双向循环链表的结构
// 节点数据的类型
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev; //指向前一个节点的指针
LTDataType data; //节点的数据
struct ListNode* next; //指向后一个节点的指针
}LNode;以上的结构就是 带哨兵位双向循环链表 中每一个节点的结构
prev 指针指向前一个节点，next 指针指向后一个节点，这样就实现了双向的结构
带哨兵位双向循环链表逻辑结构示意图
哨兵位 head 节点的 prev 指向最后一个节点，next 指向第一个节点
这样就实现了带哨兵位循环的结构
实现带哨兵位双向循环链表的准备工作
和实现 无哨兵位单向不循环链表 一样，需要准备3个文件
test.c 文件：用来测试代码功能的完善性
List.h 文件：用来声明头文件和定义单链表的结构以及函数的声明
List.c 文件：用来实现单链表的功能函数
实现带哨兵位双向循环链表
1. 创建新节点
static LNode* BuyLTNode(LTDataType x)
{
LNode* newnode = (LNode*)malloc(sizeof(LNode));
// 判断是否开辟成功
if (newnode == NULL)
{
perror("BuyLTNode fail");
return NULL;
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
} 使用 malloc 函数动态开辟一个 newnode 节点，并判断是否开辟成功
将数据 x 存储到 newnode 的 data 中，最后返回 newnode 节点指针
2. 初始化哨兵位
LNode* LTInit()
{
LNode* phead = BuyLTNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}在函数内部创建哨兵位，最后再返回哨兵位的指针，这样做的好处是避免使用二级指针
为什么要将哨兵位的 prev 和 next 都指向自己呢？这个留作悬念，在尾插时会讲解到
3. 定义哨兵位指针
LNode* plist = LTInit();
直接利用初始化哨兵位的函数定义链表，这样就避免了使用二级指针
因为如果使用传址初始化哨兵位的话，就需要传递二级指针才能改变指针的指向
没有这样做是因为稳定函数的统一性，使函数都使用一级指针进行增删查改
4. 打印链表所有节点的数据
void LTPrint(LNode* phead)
{
LNode* cur = phead->next;
printf("head<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("head\n");
}phead 的 next 也就是链表的第一个节点 cur
因为链表是循环链表，那么尾节点的 next 就是哨兵位
所以 while 循环的判断条件是头节点 cur 不等于 哨兵位 phead
这样就实现了打印链表所有节点的数据
5. 在链表尾部插入节点
void LTPushBack(LNode* phead, LTDataType x)
{
// 判断哨兵位的有效性
assert(phead);
LNode* newnode = BuyLTNode(x); //申请新节点
LNode* tail = phead->prev; //找原尾节点
// 原尾节点链接新尾节点
tail->next = newnode;
newnode->prev = tail;
// 哨兵位链接新尾节点
phead->prev = newnode;
newnode->next = phead;
}在链表尾部插入数据，那么就要先找到链表中原来的尾节点
且原来的尾节点 tail 就是哨兵位 phead 节点的 prev
先把原尾节点 tail 的 next 指向 新节点 newnode ，新节点 newnode 的 prev 指向原尾节点 tail ，这样 newnode 就成功链接成新的尾节点
最后再把哨兵位 phead 的 prev 指向新的尾节点 newnode ，新尾节点 newnode 的 next 指向 phead ，这样哨兵位就成功链接了新的尾节点
且当链表为空时，以上的代码逻辑同样适用，这就是为什么在初始化哨兵位时要将哨兵位的 prev 和 next 都指向自己的原因
测试代码：
6. 在链表头部插入节点
void LTPushFront(LNode* phead, LTDataType x)
{
assert(phead);
LNode* newnode = BuyLTNode(x); //申请新节点
LNode* first = phead->next; //找原头节点
// 原头节点链接新头节点
newnode->next = first;
first->prev = newnode;
// 哨兵位链接新头节点
phead->next = newnode;
newnode->prev = phead;
}先找到原来的头节点 first ，原来的头节点也就是 phead 的 next
再把原头节点和新头节点链接、哨兵位和新头节点链接，无论先后顺序都可以
这样就实现了在链表头部插入数据
以上的代码逻辑同样适用于当链表为空的情况
测试代码：
7. 在链表尾部删除节点
void LTPopBack(LNode* phead)
{
assert(phead);
// 当链表为空时
if (phead->prev == phead)
{
printf("链表无节点可删除\n");
return;
}
// 找到尾节点的前一个节点
LNode* tailPrev = phead->prev->prev;
// 删除（释放）尾节点
free(phead->prev);
// 哨兵位链接新尾节点
tailPrev->next = phead;
phead->prev = tailPrev;
}先找到尾节点的前一个节点，phead 的 prev 是尾节点，那么 phead 的 prev 的 prev 就是尾节点的前一个节点
再释放尾节点，最后再链接哨兵位和新的尾节点 tailPrev
这样就实现了在链表尾部删除节点
以上的代码逻辑在 链表只有一个节点 或者 链表为空 的时候同样适用
测试代码：
8. 在链表头部删除节点
void LTPopFront(LNode* phead)
{
assert(phead);
// 当链表为空时
if (phead->next == phead)
{
printf("链表无节点可删除\n");
return;
}
// 找到头节点的下一个节点
LNode* firstNext = phead->next->next;
// 释放头节点
free(phead->next);
// 哨兵位链接新的头节点
phead->next = firstNext;
firstNext->prev = phead;
}先找到头节点的下一个节点，phead 的 next 就是头节点，那么 phead 的 next 的 next 就是头节点的下一个节点
再释放头节点，最后在把哨兵位和新的头节点链接
这样就实现了在链表头部删除节点
以上的代码逻辑在 链表只有一个节点 或者 链表为空 的时候同样适用
测试代码：
9. 查找链表中的指定节点
LNode* LTFind(LNode* phead, LTDataType x)
{
assert(phead);
LNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}和 打印链表所有节点的数据 的逻辑差不多，也是需要遍历链表
当 cur 的 data 等于 x 时，cur 就是要查找的节点，返回 cur
当链表遍历完一遍还没有找到指定节点时，说明没有此节点，返回NULL即可
以上的逻辑既有读也有写的功能，因为返回值是指定节点的指针，那么就可以进行修改
且在实现中间插入删除节点时，都要利用 LTFind 函数配合使用
10. 在pos节点之前插入节点
void LTInsert(LNode* pos, LTDataType x)
{
assert(pos);
LNode* newnode = BuyLTNode(x);
LNode* posPrev = pos->prev; //找到 pos 节点的前一个节点
// posPrev 节点链接新节点
posPrev->next = newnode;
newnode->prev = posPrev;
// 新节点链接 pos 节点
newnode->next = pos;
pos->prev = newnode;
}优先判断 pos 指针的有效性，因为当 LTFind 函数没有查找到指定节点时，会返回 NULL
找到 pos 节点的前一个节点 posPrev
再将 posPrev 和 newnode 和 pos 节点各自链接，无论先后顺序都可以
这样就实现了在链表 pos 节点之前插入节点
以上代码逻辑同样适用于当链表只有一个节点的情况
测试代码：
11. 删除pos节点
void LTErase(LNode* pos)
{
assert(pos);
// 找到 pos 节点的前一个节点
LNode* posPrev = pos->prev;
// 找到 pos 节点的后一个节点
LNode* posNext = pos->next;
// 释放 pos 节点
free(pos);
// 链接 posPrev 和 posNext 节点
posPrev->next = posNext;
posNext->prev = posPrev;
}同样优先判断 pos 节点的有效性
再找到 pos 节点的前一个节点 posPrev 和 pos 的后一个节点 posNext
最后释放 pos 节点，再链接 posPrev 和 posNext 节点即可
这样就实现了删除 pos 节点
以上代码逻辑同样适用于当链表只有一个节点的情况
测试代码：
小结
只要有了 LTFind 和 LTInsert 和 LTErase 这三个函数，以上的头插、尾插、头删、尾删这些函数都可以复用这三个函数，具体怎么复用我就不写了，望大家自己实现
12. 释放链表
void LTDestroy(LNode* phead)
{
assert(phead);
LNode* cur = phead->next;
LNode* next = NULL;
while (cur != phead)
{
next = cur->next;
free(cur);
cur = next;
}
free(phead);
}从第一个节点开始释放，释放前要先存储下一个节点
最后再释放哨兵位 phead
自此，带哨兵位双向循环链表的基本函数都以实现，接下来就是做一些有关链表的oj题
感谢大家阅读，最后我会把定义和实现的所有代码文件展示在下面
List.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 节点数据的类型
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev; //指向前一个节点的指针
LTDataType data; //节点的数据
struct ListNode* next; //指向后一个节点的指针
}LNode;
// 初始化哨兵位
LNode* LTInit();
// 打印
void LTPrint(LNode* phead);
// 尾插
void LTPushBack(LNode* phead, LTDataType x);
// 头插
void LTPushFront(LNode* phead, LTDataType x);
// 尾删
void LTPopBack(LNode* phead);
// 头删
void LTPopFront(LNode* phead);
// 查找
LNode* LTFind(LNode* phead, LTDataType x);
// pos节点之前插入
void LTInsert(LNode* pos, LTDataType x);
// 删除pos节点
void LTErase(LNode* pos);
// 释放链表
void LTDestroy(LNode* phead);List.c
#include"List.h"
// 创建新节点
static LNode* BuyLTNode(LTDataType x)
{
LNode* newnode = (LNode*)malloc(sizeof(LNode));
// 判断是否开辟成功
if (newnode == NULL)
{
perror("BuyLTNode fail");
return NULL;
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
// 初始化哨兵位
LNode* LTInit()
{
LNode* phead = BuyLTNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}
// 打印
void LTPrint(LNode* phead)
{
assert(phead);
LNode* cur = phead->next;
printf("head<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("head\n\n");
}
// 尾插
void LTPushBack(LNode* phead, LTDataType x)
{
// 判断哨兵位的有效性
assert(phead);
LNode* newnode = BuyLTNode(x); //申请新节点
LNode* tail = phead->prev; //找尾节点
// 原尾节点链接新尾节点
tail->next = newnode;
newnode->prev = tail;
// 哨兵位链接新尾节点
phead->prev = newnode;
newnode->next = phead;
}
// 头插
void LTPushFront(LNode* phead, LTDataType x)
{
assert(phead);
LNode* newnode = BuyLTNode(x); //申请新节点
LNode* first = phead->next; //找原头节点
// 原头节点链接新头节点
newnode->next = first;
first->prev = newnode;
// 哨兵位链接新头节点
phead->next = newnode;
newnode->prev = phead;
}
// 尾删
void LTPopBack(LNode* phead)
{
assert(phead);
// 当链表为空时
if (phead->prev == phead)
{
printf("链表无节点可删除\n");
return;
}
// 找到尾节点的前一个节点
LNode* tailPrev = phead->prev->prev;
// 删除（释放）尾节点
free(phead->prev);
// 哨兵位链接新尾节点
tailPrev->next = phead;
phead->prev = tailPrev;
}
// 头删
void LTPopFront(LNode* phead)
{
assert(phead);
// 当链表为空时
if (phead->next == phead)
{
printf("链表无节点可删除\n");
return;
}
// 找到头节点的下一个节点
LNode* firstNext = phead->next->next;
// 释放头节点
free(phead->next);
// 哨兵位链接新的头节点
phead->next = firstNext;
firstNext->prev = phead;
}
// 查找
LNode* LTFind(LNode* phead, LTDataType x)
{
assert(phead);
LNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
// pos节点之前插入
void LTInsert(LNode* pos, LTDataType x)
{
assert(pos);
LNode* newnode = BuyLTNode(x);
LNode* posPrev = pos->prev; //找到 pos 节点的前一个节点
// posPrev 节点链接新节点
posPrev->next = newnode;
newnode->prev = posPrev;
// 新节点链接 pos 节点
newnode->next = pos;
pos->prev = newnode;
}
// 删除 pos 节点
void LTErase(LNode* pos)
{
assert(pos);
// 找到 pos 节点的前一个节点
LNode* posPrev = pos->prev;
// 找到 pos 节点的后一个节点
LNode* posNext = pos->next;
// 释放 pos 节点
free(pos);
// 链接 posPrev 和 posNext 节点
posPrev->next = posNext;
posNext->prev = posPrev;
}
// 释放链表
void LTDestroy(LNode* phead)
{
assert(phead);
LNode* cur = phead->next;
LNode* next = NULL;
while (cur != phead)
{
next = cur->next;
free(cur);
cur = next;
}
free(phead);
}