【数据结构之带头双向循环链表的实现】

1.链表的分类

链表的结构有多种多样，以下情况组合起来就有8种（2x2x2）链表结构：

虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：单链表和双向带头循环链表。

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶.图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最为复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现就知道了。

2.带头双向循环链表的实现

和前面的数据结构的实现一样我们需要用三个文件，List.h（链表结构的声明以及链表的函数的声明），List.c（函数功能的实现），test.c（函数功能的测试文件）。

2.1 List.h（链表结构的定义以及链表的函数的声明）

在这里我们需要理解双向是啥意思，双向在结构中体现不仅有指向前一个节点的指针，而且有指向下一个节点的指针。初次之外通过这两个指针让链表也构成了循环。示意图如下：

故而带头双向链表在定义的时候需要用一个包含三个变量的结构变量，具体定义如下：

注：和前面一样在这里我们操作的数据类型可变，所以对类型重命名的方法。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//带头双向链表的结构的定义 以及所要实现的函数的声明
typedef int LTDatatype;
typedef struct ListNode
{LTDatatype data;struct ListNode* prev;struct ListNode* next;
}LTNode;//打印链表
void LTPrint(LTNode* phead);//初始化  需要创建哨兵位 这样插入和删除的时候就不要考虑链表为空了
void LTInit(LTNode** pphead);
//因此双向链表为空的情况就是链表中只有一个哨兵位//插入
//头插   因为有了哨兵位就并不会影响头结点，故传一级指针即可
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);//对链表进行判空
bool* LTEmpty(LTNode* phead);//删除
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//数据的查找
LTNode* LTFind(LTNode* phead, LTDatatype x);//指定位置的操作
//指定位置之后数据的插入
void* LTInsert( LTNode* pos, LTDatatype x);//指定位置的数据的删除
void LTErase( LTNode* pos);//链表的销毁
void LTDestroy(LTNode* phead);

2.2 List.c（函数功能的实现）需要包含头文件#include "List.h"

2.2.1 链表的初始化
LTNode* LTBuyNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->prev = newnode;newnode->next = newnode;return newnode;
}
void LTInit(LTNode** pphead)  //需要改变头结点（影响头结点）所以传二级指针
{*pphead=LTBuyNode(-1);
}
实现思路：

在初始化之前我们得先实现一个申请新节点的函数。实现该函数需要用到malloc函数申请一个节点的空间，再进行判断看是否申请成功。如果申请成功就将数据保存在newnode->data中，并且将两个指针变量newnode->pre和newnode->next都指向新节点。最后返回新节点的地址。
因为我们实现的是带头的链表，这个头是方便插入和删除（就相当于哨兵位），所以在初始化时只需要创建一个携带无效数据的节点即可。

2.2.2 链表的打印
//链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;if(pcur->next!=phead)printf("plist->");while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("plist\n");
}
实现思路：

我们需要遍历链表，对链表中的数据进行打印即可。但是需要注意的是，遍历链表的时候需要从头结点的下一个节点开始遍历，遍历结束条件是当前节点所指向的下一个节点不能是头结点（哨兵位）。

2.2.3 链表的数据的插入
//插入
//尾插   因为有了哨兵位就并不会影响头结点，故传一级指针即可
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//改变 phead->prev phead->prev->next newnode->prev newnode->nextnewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//改变 phead phead->prev  phead->next  phead->next->prev的指向关系newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
实现思路：

在实现头插和尾插时都需要先判断所传值的有效性，以及先申请到一个新节点。

尾插： 先将新节点的prev指向目前链表的尾节点，再将新节点的next指向头结点。除此之外，我们还需要将链表的尾节点的next指向新节点，将头结点的prev指向新节点。
头插： 先将新节点的next指向头结点的下一个节点，再将新节点的prev指向头结点。除此之外我们还需要将头节点的下一个节点的prev指向新节点，再将头结点的next指向新节点。

2.2.4 链表的判空
//对链表进行判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
实现思路：

返回值为bool类型，先判断值的有效性。然后将判断头结点的下一个指针是否为它本身返回即可。

2.2.5 链表的数据的删除
//删除
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//改变phead-prev->prev的next   phead->prev的指向LTNode* del = phead->prev;LTNode* delprev = del->prev;phead->prev = delprev;delprev->next = phead;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//改变phead->next->next的prev  phead的nextLTNode* del = phead->next;LTNode* delnext = del->next;phead->next = delnext;delnext->prev = phead;free(del);del = NULL;
}
实现思路：

在实现尾删和头删时都需要先进行对所传值的有效性进行判断，再进行判断链表是否为空（除头结点外是否还有其他的有效节点）。

尾删： 先将要删除的节点，即尾节点先保存下来；同时将尾节点的前一个节点保存下来delprev。（要不然直接释放掉就找不到了）然后将头结点的prev指向delprev尾节点的前一个节点，将delprev的next指向头节点。最后释放掉del,并将del置为空。
头删： 先将要删除的节点，即头节点先保存下来；同时将尾节点的下一个节点保存下来delnext。（要不然直接释放掉就找不到了）然后将头节点的nedxt指向delnext，再将delnext的prev指向头结点。最后释放掉要删除的节点，并将其置为空。

注：因为每个节点都是通过动态内存申请的空间，所以在删除节点的时候是通过free，切记释放完需置为空，避免对野指针的使用。

2.2.6 链表中数据的查找
//数据的查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);assert(!LTEmpty(phead));LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}
实现思路：

先判断所传phead 的有效性，再进行判空。然后再进行链表的遍历，如果当前节点的数据刚好为所要查找的数据，则就返回当前节点的位置，否则就返回空指针。

2.2.7 链表中指定位置的操作
// 指定位置的操作
//指定位置之后数据的插入
void* LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//指定位置的数据的删除
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next= pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
实现思路：

指定位置之后的插入和指定位置的删除都需要先对所要操作的位置的有效性进行判断。

指定位置之后的插入： 申请一个新节点，将新节点的next指向pos的下一个节点，将新节点的prev指向pos。将pos 的下一个节点的prev指向新节点，将pos的next指向新节点。
指定位置的删除： 先将pos之前的节点的next指向pos的下一个节点，再将pos的下一个节点的prev指向pos的前一个节点。

2.2.8 链表的销毁
//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = pcur = NULL;
}
实现思路：

先判断所传值的有效性，因为每个节点都是通过动态内存申请的空间，所以链表的销毁需要通过free函数，通过遍历逐一释放节点， 释放完需要将当前节点和头结点置为空。

但是值得注意的是：

在释放当前节点时，得先将当前节点的下一个节点保存下来。
释放加点时，应该从头结点的下一个节点开始销毁（即从有效节点开始释放）。

2.3 test.c（函数功能的测试文件）

#include "List.h"
void test()
{LTNode* lt = NULL;LTInit(&lt);//LTPrint(lt);LTPushBack(lt, 1);LTPushFront(lt, 29);LTPushFront(lt, 25);LTPushFront(lt, 2);LTPushFront(lt, 33);LTPrint(lt);LTPopBack(lt);//LTPushBack(lt, 1);//LTPopBack(lt);LTPrint(lt);/*LTPopFront(lt);LTPopFront(lt);LTPopFront(lt);LTPopFront(lt);LTPrint(lt);*/LTNode*ret=LTFind(lt, 25);if (ret)printf("ҵ%d\n",ret->data);elseprintf("δҵ\n");LTInsert(ret, 56);LTErase(ret);LTPrint(lt);LTDestroy(lt);LTPrint(lt);
}
int main()
{test();return 0;
}