链表初始化
LTNode* ListInit(LTNode* phead) { //哨兵位头节点 phead = (LTNode*)malloc(sizeof(LTNode)); phead->next = phead; phead->prev = phead; return phead; //利用返回值的方式 }
首先，我们需要一个哨兵头节点，该头节点的next和prev均指向该头节点本身，最后，返回这个头节点的地址。
打印链表
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next;//从phead->开始遍历链表 while (cur != phead)//为了防止死循环，所以终止条件为cur=phead { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
由于链表是双向循环链表，双向循环链表自身的结构很容易在打印时造成死循环，所以我们在打印链表时需要注意循环终止的条件，否则，程序就会陷入死循环。再次提醒，这是一个双向循环链表。当我们循环打印完链表的最后一个数据的时候，此时cur就是指向链表中最后一个节点的，而cur->next是指向链表的哨兵头节点的，所以，循环终止条件就是cur=phead。
尾插
void ListPushBack(LTNode* phead, LTDateType x) { //链表为空时，依然可以处理 assert(phead); LTNode* tail = phead->prev;//找到尾节点 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; //phead tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
尾删
//尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//当链表为空时，就表示不能再删除了 //找到尾 LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; //最后释放空间 free(tail); }
既然是尾删，我们首先要先找到尾，即LTNode* tail = phead->prev;这样会方便很多，同时尾删的时候一定要注意**free（）**的释放时机。
注意一种特殊情况：当phead->next==phead的时候，此时链表为空，就不能继续删除了。所以需要加上 assert(phead->next != phead);。
新建一个节点
LTNode* BuyListNode(LTDateType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
该函数功能就是新建一个节点，把该节点的数据进行赋值（即newnode->data = x;），并把指针均变成空指针（newnode->prev = NULL; newnode->next = NULL;）。最后返回这个新节点的地址即可。
头插
void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
还是看一下特殊情况，即如果链表是一个空链表，我们来简单分析一下：链表为空时phead->next就是phead本身。
我们只需要处理phead、next、newnode三者之间的链接关系即可。最后发现，链表为空时依然可以进行处理。
头删
void ListPopFront(LTNode* phead) { assert(phead); //链表为空就不需要头删了 LTNode* next = phead->next; LTNode* nextNext = next->next; phead->next = nextNext; nextNext->prev = phead; free(next); }
链表为空时就不要进行头删操作了，故加上assert(phead);我们最好还是提前定义好next和nextNext即LTNode* next = phead->next;
LTNode* nextNext = next->next;
这样后面会很方便，可以减少不必要的麻烦，接下来处理phead、next、nextNext三者之间的链接关系就好了。
查找
查找的实现与打印的实现差不太多，提前定义一个cur指向phead的next，即LTNode* next = phead->next;循环终止条件依然是cur = phead，其它按部就班即可。
LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } //没找到就返回NULL return NULL; }
在pos之前插入*
void ListInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = BuyListNode(x); //处理posPrev newnode pos三者之间的链接关系 posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
一定要提前定义一个posPrev即LTNode* posPrev = pos->prev;，然后进行newnode、pos、posPrev之间的链接就好。
在这里，我们还可以利用ListInsert这个函数来完成头插尾插的操作。
首先，我们先利用ListInsert来完成尾插的操作。
当pos是我们的哨兵位节点phead的时候，由于这个函数是在pos之前插入，所以此时就相当于尾插了（因为phead->prev就是尾）。
void ListPushBack(LTNode* phead, LTDateType x) { //链表为空时，依然可以处理 assert(phead); //LTNode* tail = phead->prev;//找到尾节点 //LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //newnode->data = x; phead //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); }
现在再来看头插：
当phead->next和pos相等时，此时就相当于头插。
void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); //LTNode* newnode = BuyListNode(x); //LTNode* next = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = next; //next->prev = newnode; ListInsert(phead->next, x); }
所以我们以后想要快速的写双向循环链表的时候，头插、尾插、或者任意位置的插入都可以利用ListInsert这个函数来快速的实现双向循环链表。把phead->prev传给pos就是尾插，把phead->next传给pos就变成了头删。所以双向链表只需要实现两个函数（ListInsert和ListErase）就都搞定了，这也是双向链表结构的一个优势。
删除pos位置
void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
一般来说，我们想要删除某个数据先是调用ListFind来返回一个地址，然后才调用ListErase继而把该数据删除，请看：
void TestList2() { LTNode* plist = NULL; plist = ListInit(plist); ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPrint(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); LTNode* pos = ListFind(plist, 2); if (pos != NULL) { ListErase(pos); } ListPrint(plist); }
我们可以看到运行结果成功把第一个2删除了。
然而ListErase的功能不仅仅只有这些，我们还可以利用ListErase来完成头删尾删的操作。
请看：
//尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//当链表为空时，就表示不能再删除了 找到尾 //LTNode* tail = phead->prev; //phead->prev = tail->prev; //tail->prev->next = phead; 最后释放空间 //free(tail); ListErase(phead->prev); }
//头删 void ListPopFront(LTNode* phead) { assert(phead); 链表为空就不需要头删了 //LTNode* next = phead->next; //LTNode* nextNext = next->next; //phead->next = nextNext; //nextNext->prev = phead; //free(next); ListErase(phead->next); }
现在我们来测试一下：
void TestList2() { LTNode* plist = NULL; plist = ListInit(plist); ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPrint(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); LTNode* pos = ListFind(plist, 2); if (pos != NULL) { ListErase(pos); } ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); }
销毁链表
最后，我们再来实现一下销毁链表。
//销毁链表 void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); //想要把phead置为空，需要再函数外部进行置空，当然如果传二级指针也可以在函数内部把 //phead置为空，不过因为我们这个双向链表都是传的一级指针，所以为了保持接口一致性， //我们在函数外部把phead置为空即可 }
以上就是双向循环链表所以接口函数的实现。
总代码
test.c
#include"List.h" void TestList1() { LTNode* plist = NULL;//初始化 plist = ListInit(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPrint(plist); } void TestList2() { LTNode* plist = NULL; plist = ListInit(plist); ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPushFront(plist, 4); ListPrint(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); LTNode* pos = ListFind(plist, 2); if (pos != NULL) { ListErase(pos); } ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListDestroy(plist); plist = NULL; } int main() { //TestList1(); TestList2(); return 0; }
list.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDateType; typedef struct ListNode { LTDateType data; struct ListNode* next; struct ListNode* prev; }LTNode; LTNode* ListInit(LTNode* phead);//初始化 void ListPrint(LTNode* phead); //打印链表 //尾插 void ListPushBack(LTNode* phead, LTDateType x); //尾删 void ListPopBack(LTNode* phead); //头插 void ListPushFront(LTNode* phead, LTDateType x); //头删 void ListPopFront(LTNode* phead); //创建新节点 LTNode* BuyListNode(LTDateType x); //查找 LTNode* ListFind(LTNode* phead, LTDateType x); //pos位置之前插入 void ListInsert(LTNode* pos, LTDateType x); //删除pos位置 void ListErase(LTNode* pos); //销毁聊表 void ListDestroy(LTNode* phead);
list.c
#include"List.h" //初始化 LTNode* ListInit(LTNode* phead) { //哨兵位头节点 phead = (LTNode*)malloc(sizeof(LTNode)); phead->next = phead; phead->prev = phead; return phead; //利用返回值的方式 } void ListPushBack(LTNode* phead, LTDateType x) { //链表为空时，依然可以处理 assert(phead); //LTNode* tail = phead->prev;//找到尾节点 //LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //newnode->data = x; phead //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); } void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next;//从phead->开始遍历链表 while (cur != phead)//为了防止死循环，所以终止条件为cur=phead { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//当链表为空时，就表示不能再删除了 找到尾 //LTNode* tail = phead->prev; //phead->prev = tail->prev; //tail->prev->next = phead; 最后释放空间 //free(tail); ListErase(phead->prev); } LTNode* BuyListNode(LTDateType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; } void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); //LTNode* newnode = BuyListNode(x); //LTNode* next = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = next; //next->prev = newnode; ListInsert(phead->next, x); } //头删 void ListPopFront(LTNode* phead) { assert(phead); 链表为空就不需要头删了 //LTNode* next = phead->next; //LTNode* nextNext = next->next; //phead->next = nextNext; //nextNext->prev = phead; //free(next); ListErase(phead->next); } //查找 LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } //没找到就返回NULL return NULL; } //pos位置之前插入 void ListInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = BuyListNode(x); //处理posPrev newnode pos三者之间的链接关系 posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; } //删除pos位置 void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); } //销毁链表 void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); //想要把phead置为空，需要再函数外部进行置空，当然如果传二级指针也可以在函数内部把 //phead置为空，不过因为我们这个双向链表都是传的一级指针，所以为了保持接口一致性， //我们在函数外部把phead置为空即可 }
好了，双向循环链表的实现就到这里了，其实在这里面最重要的两个接口函数就是ListErase和ListInser，这两个函数可以帮助我们快速的实现这个链表，剩余的就是一些边边角角的问题了。
这块的内容还是要多画图，来帮助我们更好的理解。
