作者：旧梦拾遗186

专栏：数据结构成长日记

前言：

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
现在我们来通过代码实现带头双向循环链表，结构上虽然是链表最复杂的，但是并没有我们想象的那么困难，恰恰相反，其代码实现比较简单

带头双向链表样例：

代码实现

List.h

#pragma once#include #include #include #include typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* ListInit();void ListPrint(LTNode* phead);void ListPushBack(LTNode* phead, LTDataType x);void ListPushFront(LTNode* phead, LTDataType x);void ListPopBack(LTNode* phead);void ListPopFront(LTNode* phead);bool ListEmpty(LTNode*phead);size_t ListSize(LTNode*phead);LTNode* ListFind(LTNode* phead,LTDataType x);//在pos之前插入void ListInsert(LTNode* pos, LTDataType x);//删除pos位置void ListErase(LTNode* pos);void ListDestory(LTNode* phead);

List.c

#include "List.h"LTNode* ListInit(){LTNode* guard = (LTNode*)malloc(sizeof(LTNode));if (guard == NULL){perror("malloc fail");exit(-1);}guard->next = guard;guard->prev = guard;return guard;}LTNode* BuyListNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;}void ListPrint(LTNode* phead){assert(phead);printf("phead");LTNode* cur = phead->next;while (cur != phead){printf("%d", cur->data);cur = cur->next;}printf("\n");}void ListPushBack(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;}void ListPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = BuyListNode(x);//考虑先后顺序/*newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*///记录下一位，就不用考虑顺序LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}void ListPopBack(LTNode* phead){assert(phead);assert(!ListEmpty(phead));LTNode* tail = phead->prev;LTNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;}void ListPopFront(LTNode* phead){assert(phead);assert(!ListEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}bool ListEmpty(LTNode* phead){assert(phead);return phead->next == phead;}size_t ListSize(LTNode*phead){assert(phead);size_t n = 0;LTNode* cur = phead->next;while (cur != phead){++n;cur = cur->next;}return n;}LTNode* ListFind(LTNode* phead, int x){assert(phead);size_t n = 0;LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}}return NULL;}//在pos之前插入void ListInsert(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;}//删除pos位置void ListErase(LTNode* pos){assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}//可以传二级，内部置空//一级指针外部置空void ListDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

test.c

#include "List.h"//测试尾插、头插、尾删、打印void TestList1(){LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPushFront(plist, 10);ListPushFront(plist, 20);ListPushFront(plist, 30);ListPushFront(plist, 40);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);}//测试头删、销毁void TestList2(){LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);ListDestory(plist);plist = NULL;}int main(){//TestList1();TestList2();return 0;}

总结：

结语：

链表的学习结束啦！！！同学们要时常复习和刷题啊，我也写了好多链表的习题博客，同学们可以来访问啦。