文章目录
写在前面
上面文章用C语言实现了单链表的增删查改，我们知道，单链表只能从头结点开始正向遍历，而在单链表中插入或删除节点时，需要修改前一个节点的指针，因此在单链表中插入或删除节点时需要遍历链表找到前一个节点，导致插入和删除操作的效率较低。为了能够高效率解决类似的问题，本片文章继续用C语言来实现另一种线性存储结构——带头双向循环链表。
我们从它的逻辑结构来更深层次的理解一下带头双向循环链表：
1. 链表节点的定义
链表的结点分为三部分：指针域、数据域、指针域。
指针域：用于指向当前节点的直接前驱节点
数据域：链表要存储的数据所在的区域。
指针域：用于指向当前节点的直接后继节点。
typedef int STDataType;
typedef struct ListNode
{
struct ListNode* prev;//指针域， 指向上一个节点
struct ListNode* next;//指针域， 指向下一个节点
STDataType val;//数据域
}LTNode;
2. 链表的初始化
该链表在初始化的时候，只需要创建哨兵位的头节点即可，并将该节点的地址返回。该节点不存储有效数据，其prev 和 next指针指向自己。
由于后面的插入都需要创建新的节点，因此这里把创建节点封装成一个函数。
LTNode* BuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror(" BuyNode()");
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
链表的初始化代码如下：
LTNode* LTInit()
{
//创建哨兵位的头节点
LTNode* newnode = BuyNode(-1);
//prev 和 next指针指向自己
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}
3. 插入数据
向链表插入数据时，根据插入位置的不同可以分为以下三种情况：
- 在头节点前插入一个元素，即头插。
- 在链表中间位置插入元素。
- 在最后一个节点后面插入一个元素，即尾插。
3.1 头插
头插数据步骤：
- 首先，创建一个新的节点，并用 val 初始化其数据域。
- 将新节点插入到链表的头部，更新指针。
代码如下：
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//检查参数有效性
LTNode* newnode = BuyNode(x);//创建新节点
LTNode* next = phead->next;
//修改指针链接关系
newnode->next = next;
next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}
3.2 尾插
尾插数据步骤：
- 首先，创建一个新的节点，并用 val 初始化其数据域。
- 将新节点插入到链表的尾部，更新指针。
代码如下：
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//检查参数有效性
LTNode* newnode = BuyNode(x);//创建新节点
LTNode* tail = phead->prev;
//修改指针链接关系
newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
//LTInsert(phead, x);
}
3.3 在指定位置的前面插入数据
- 首先，创建一个新的节点，并用 val 初始化其数据域。
- 将新节点插入到链表的 pos 位置之前，更新指针。
代码如下：
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//检查位置有效性
LTNode* newnode = BuyNode(x);//创建新节点
LTNode* posPrev = pos->prev;
//修改指针链接关系
pos->prev = newnode;
newnode->next = pos;
posPrev->next = newnode;
newnode->prev = posPrev;
}
4 删除数据
4.1 头删
头删的步骤如下：
bool LTEmpty(LTNode* phead)
{
return phead->next == phead;
}
- 删除第一个节点，并更新指针。
代码如下：
void LTPopFront(LTNode* phead)
{
assert(phead);//检查参数有效性
assert(!LTEmpty(phead));//判断链表是否为空
LTNode* pos = phead->next;
LTNode* posNext = pos->next;
free(pos);//删除第一个节点
修改指针链接关系
phead->next = posNext;
posNext->prev = phead;
}
4.2 尾删
头删的步骤如下：
- 判断链表是否为空，不为空在进行删除。
- 删除最后一个节点，并更新指针。
代码如下：
void LTPopBack(LTNode* phead)
{
assert(phead);//检查参数有效性
assert(!LTEmpty(phead));//判断链表是否为空
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);//删除最后一个节点
修改指针链接关系
phead->prev = tailPrev;
tailPrev->next = phead;
}
4.3 删除指定位置的数据
注意：删除指定位置的数据，需要传递正确的节点的地址，否则删除的结果是不确定的。
代码如下：
void LTErase(LTNode* pos)
{
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);//删除指定位置的节点
//修改指针链接关系
posPrev->next = posNext;
posNext->prev = posPrev;
}
5 查找并修改数据
遍历链表若找到目标节点，就返回目标节点的地址，否则返回空指针(NULL)。
该函数兼并修改的功能，因为该函数返回的是目标节点的地址。
代码如下：
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//检查参数有效性
LTNode* cur = phead->next;
//遍历链表
while (cur != phead)
{
//找到返回，目标节点地址
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
//未找到，返回NLL
return NULL;
}
5. 链表的销毁
- 依次释放链表的每个节点。
- 释放哨兵位的头节点。
注意：链表销毁以后，要在函数外面将头指针置空(NULL),以免造成野指针的问题。
代码如下：
void LTDestroy(LTNode* phead)
{
assert(phead);//检查参数有效性
LTNode* cur = phead->next;
//依次释放链表的每个节点
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);//释放哨兵位的头节点
}
至此，本片文章就结束了，若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。
创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
如果本篇博客有任何错误，请批评指教，不胜感激 ！！！
