数据结构（4）——带哨兵位循环双向链表

目录

前言

一、带哨兵的循环双向链表是什么

二、链表的实现

2.1规定结构体

2.2创建节点

2.3初始化

2.4打印

2.5检验是否为空

2.6销毁链表

2.7尾插

2.8尾删

2.9头插

2.10头删

2.11寻找特定节点

2.12任意位置插入（pos前）

2.13删除任意节点

总结

---

前言

前面我们学习了单链表的一些知识，由单链表引申出双向链表，同时带哨兵位或者不带哨兵位是两种，但大差不差，这里学习一下带哨兵位的循环双向链表。

其实有很多链表的结构，组成它们的也就是循环非循环，带哨兵位不带哨兵位，双向还是单向。

---

一、带哨兵的循环双向链表是什么

无哨兵单向非循环链表：结构简单，也就是我们常说的单链表，一般不会用来单独存数据，实际中更多是作为其它数据的子结构，如哈希桶，图的邻接表等等。

而带哨兵双向循环链表：结构最复杂，一般用来单独存储数据，实际中使用的链表数据结构，都是带哨兵（头）双向链表，另外这个结构虽然复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。

二、链表的实现

这里我们要实现的有

//创建节点
LTNode* BuyListNode(LTDataType x)
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//销毁链表
void LTDestory(LTNode* phead);
//检验是否为空
bool LTEmpty(LTNode* phead)
//尾插尾删
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
//检验链表是否为空
bool LTEmpty(LTNode* phead);
//头插头删
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos之前加入一个值
void LTInsert(LTNode* pos, LTDataType x);
//删除节点
void LTErase(LTNode* pos);
//寻找特定节点
LTNode* LTFind(LTNode* phead, LTDataType x);

2.1规定结构体

要想实现一个链表，就要首先规定一下每一个节点的结构体组成部分，这里我们先使用结构体来定义一下。

每一个节点内包括数据域，头指针和尾指针。

typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//头指针struct ListNode* prev;//尾指针LTDataType data;//数据
}LTNode;

基于这个结构，我们就可以实现后期的一系列操作内容，包括哨兵位的创建。

2.2创建节点

这里我们命名为BuyListNode，返回类型为结构体也就是LTNode*，通过传入一个数据LTDataType x，从而实现对节点的创建。

LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;}node->next = NULL;node->prev = NULL;node->data = x;return node;
}

通过malloc分配一个节点的内存，然后把头指针尾指针都赋为空，因为这里不知道头尾指针指向谁，把传入数据，最后返回节点。

2.3初始化

初始化就是初始化一个哨兵位节点，也就是一个头，这里把哨兵位数据定义为-1，头尾指针指向自己，因为这里是双向循环链表，返回此节点。

//初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

2.4打印

打印这里就是不断访问当前节点的下一个节点，之后打印此节点的数据。

//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("head<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}
}

这里为了形象，打印出来的后面会接上一个<<=>>，来代表双向循环链表。

2.5检验是否为空

 通过一个布尔值来检验是否为空，主要就是检查哨兵位有没有。

//检验是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.6销毁链表

我们用 LTDestory来作为销毁链表的函数名字。实际上销毁链表就是先把除了哨兵位（头节点）以外的所有节点删除释放，最后再释放哨兵位，实现是这么实现的：

//销毁释放
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

先检查是否有节点，然后把当前cur节点定义为哨兵位的下一个节点，如果cur不为哨兵位（因为是循环链表，所以最后肯定有一个时间，它的尾节点一定指向自己），在循环里面，先用next节点记住cur当前节点的下一个节点，然后释放掉当前节点，再把之前定义的next赋给当前节点，就相当于cur不断再往后走，不断再释放，最后到了循环结束的条件后，释放一下哨兵位就可以实现全部释放。

2.7尾插

这个尾插实现就基于之前创建节点的函数BuyListNode，先创建节点，找到尾节点后，再进行修改。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;//找尾节点tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

用newnode来代表要插入的新节点，找到尾节点，因为哨兵位的头指针指向最后一个节点，这时候把新的newnode插入到尾节点后面就可以，注意此时新的节点成为了尾节点，所以要更新一下头尾指针的指向关系。

2.8尾删

尾删就是找到当前尾节点，然后把尾节点的上一个节点作为最后一个节点，更新当前节点的头尾指针，删除当前尾节点。

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;}

当然这里也要断言一下，看看是否为空，为空就不需要删除。

2.9头插

头插实际上就是在哨兵位的下一个节点插入，实现过程就是类似链表的插入一样。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);phead->next->prev = newnode;newnode->next = phead->next;phead->next = newnode;newnode->prev = phead;}

插入进去后更新前后指针的指向就可以。

2.10头删

头删就是指定哨兵位的下一个节点，然后这个节点的下一个节点的头指针更新指向哨兵位，哨兵位的下一节点指向它，就然后释放掉刚才的头节点可以。

//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* destorynode = phead->next;phead->next->next->prev = phead;phead->next = phead->next->next;free(destorynode);destorynode = NULL;
}

上面给出了头删的代码。

2.11寻找特定节点

寻找特定节点，就是通过数据x寻找，之后返回一个节点的地址，这里就是通过一个循环寻找的特定节点，然后返回。

//寻找特定节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);//带头双向循环是定不为空的LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.12任意位置插入（pos前）

基于之前的寻找特定的节点，以及新节点的创建，在这里对新节点进行插入，插入到pos的下一个节点，并且更新指针。

//任意位置插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

2.13删除任意节点

通过传入一个pos节点，进行删除，逻辑和前面的删除差不多。

//删除节点
void LTErase(LTNode* pos)
{assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;
}

---

总结

这里对循环有哨兵位双链表进行基本功能的编写和学习。