双向带头循环链表

一、概念

何为双向：此链表每一个节点的指针域由两部分组成，一个指针指向下一个节点，另一个指针指向上一个节点，并且两头的节点也是如此，头节点的下一个节点是尾节点，尾节点的上一个节点是头节点；

何为带头：此处的头节点是一个 哨兵位，在链表定义时就要手动设置，此节点只是起到头的作用，并不是真正的节点；在双向带头循环链表为空时，链表中只有一个头节点，当链表中连头节点都不存在时，此链表不能被称作一个有效链表；

何为循环：头节点的指针域中能指向前一个节点的指针指向尾节点，尾节点中能指向下一个节点的指针指向头节点，使得这个链表循环；

---

二、节点结构

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掉头节点并置为空。