双向带头循环链表
一、概念
何为双向：此链表每一个节点的指针域由两部分组成，一个指针指向下一个节点，另一个指针指向上一个节点，并且两头的节点也是如此，头节点的下一个节点是尾节点，尾节点的上一个节点是头节点；
何为带头：此处的头节点是一个 哨兵位，在链表定义时就要手动设置，此节点只是起到头的作用，并不是真正的节点；在双向带头循环链表为空时，链表中只有一个头节点，当链表中连头节点都不存在时，此链表不能被称作一个有效链表；
何为循环：头节点的指针域中能指向前一个节点的指针指向尾节点，尾节点中能指向下一个节点的指针指向头节点，使得这个链表循环；
二、节点结构
struct ListNode
{
ListDatatype data;
struct ListNode* next;
struct ListNode* prev;
}；data存储节点的胡数据，next作用是指向下一个节点，prev的作用是指向前一个节点；
三、基本功能实现
1、头文件
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<assert.h>
typedef int ListDatatype;
typedef struct ListNode
{
ListDatatype data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//初始化链表
void LTInit(ListNode** pphead);
//尾插
void LTPushBack(ListNode* phead, ListDatatype x);
//头插
void LTPushFront(ListNode* phead, ListDatatype x);
//头删
void LTPopFront(ListNode* phead);
//尾删
void LTPopBack(ListNode* phead);
//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x);
//删除指定位置的节点
void LTErase(ListNode* phead,ListNode* pos);
//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x);
//销毁双向带头循环链表
void LTDestroy(ListNode** phead);2、函数的实现
初始化
//初始化
void LTInit(ListNode** pphead)
{
assert(pphead);
*pphead = (ListNode*)malloc(sizeof(ListNode));
if (*pphead == NULL)
{
perror("malloc failed");
exit(1);
}
(*pphead)->data = -1;
(*pphead)->next = (*pphead)->prev = *pphead;
}初始化传二级指针，涉及到头节点的修改，默认-1为无效值，给定头节点的数据域是-1；让头节点的next和prev指针都指向自己，实现循环。
申请节点
//申请节点
ListNode* BuyNode(ListDatatype x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(1);
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
}申请的节点数据域为你传进的值；同样地，新节点地next和prev指针都指向自己；
尾插
//尾插
void LTPushBack(ListNode* phead, ListDatatype x)
{
assert(phead);
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}尾插不涉及到头节点地改变，所以只需要传入一级指针；尾插进入一个数据，涉及到头节点的prev指针指向发生变化，和原连边尾节点的next指针指向发生变化，为了不造成节点找不到的情况，先修改newnode的指针指向，让newnode的next指向phead，prev指向原链表的尾节点，也就是phead->prev；此操作完成后，先让原链表的尾节点（phead->prev）的next指向newnode，使得newnode成为新的尾节点，再让头节点phead的prev指向作为新的尾节点的newnode，完成循环；
头插
//头插
void LTPushFront(ListNode* phead, ListDatatype x)
{
assert(phead);
ListNode* newnode = BuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}头插是往头节点（哨兵位）的下一个指针插入节点，因为头节点不存放有效数据，在链表中的的作用只是当做一个桩子；所以先让newnode的next指针指向原链表头指针的下一个节点，也就是phead->next，再让newnode的prev指针指向phead； 再让原链表头节点之后的那个节点（phead->next）的prev指向newnode，最后再让头节点的next指针指向newnode
注意：最后两行代码不能颠倒顺序，若是颠倒，那么phead的next指针就先指向newnode，再进行（ phead->next->prev = newnode;）操作时相当于newnode->prev=newnode，这样无法实现双向（尾插同样如此）
尾删
//尾删
void LTPopBack(ListNode* phead)
{
assert(phead && phead->next!=phead);
ListNode* del = phead->prev;
phead->prev = del->prev;
del->prev->next = phead;
free(del);
del = NULL;
}尾删首先要保证链表中含有可以删除的有效节点，所以assert断言中（phead->next!=phead）操作必不可少，若是只含有头节点，那么相当于phead->next=phead这行代码，那么断言错误；当然头节点是必须存在的；
先把要删除的尾节点存在del中，先不删除del，先把要修改的指针指向修改好之后再删除要删除的尾节点，这样是为了避免找不到尾节点的前后节点；pehad->prev就是尾节点，把头节点的prev指针指向倒数第二个节点也就是（del->prev），再让倒数第二个节点的next指针指向头节点；最后释放尾节点del；
头删
//头删
void LTPopFront(ListNode* phead)
{
assert(phead && phead->next!=phead);//头删时要存在有效节点
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}头删删除的是头节点后面的那个指针，和尾删断言一样，链表中要存在有效节点，否则断言报错；先把要删除的节点存放起来，再先修改指针的指向，最后删除del；
查找结点
//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}查找节点的方法是把链表遍历一遍，看有没有数据域等于要查找的节点的数据域，若是有则返回这个节点，反之返回NULL；
在指定位置之后插入节点
//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x)
{
assert(phead && pos);
ListNode* newnode = BuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}需要配合查找节点一起使用，将查找到的节点作为pos，在此后插入节点，同样地先改变newnode的先后指针指向，再去修改pos以及pos后一个几点的指针指向；
删除指定位置的节点
//删除指定位置的节点
void LTErase(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}pos必须存在，删除先改变删除的节点的前后节的指针的指向，再删除pos；
销毁链表
//销毁双向带头循环链表
void LTDestroy(ListNode** pphead)
{
assert(pphead && *pphead);
ListNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}销毁链表涉及到头节点的改变。要传入二级指针；并且要销毁链表中每一个节点，遍历删除，最后free掉头节点并置为空。
原文地址：https://blog.csdn.net/zc331/article/details/140351826
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！