一、链表种类的优劣
链表可分为8种：
单向 双向 单向带头循环 双向带头循环 单向带头不循环 双向带头不循环 单向不带头循环 双向不带头循环 单向不带头不循环 双向不带头不循环
在C语言实现链表那篇博客中https://blog.csdn.net/sjsjnsjnn/article/details/123920224?spm=1001.2014.3001.5501
主要实现的是单向不带头非循环的链表结构；
此结构：
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
-------------------------------------------------------------------------------------------------------------------------
本次主要分析 双向带头循环链表的链表结构；
此结构：
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了；
二、什么是双向循环链表
双向循环链表和单链表都是由结点组成的，单链表包含一个数据域和一个指针域构成，而双向循环链表不同，它是由一个数据域和两个指针域组成，其中指针包含前驱指针（prev）和后继指针（next）；
三，双向循环链表各接口函数实现
1.双链表的初始化
//双向带头循环链表的初始化 LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//创建头结点 phead->next = phead;//后继指针指向头 phead->prev = phead;//前驱指针指向头 return phead; }
2.双链表的打印
//双向带头循环链表的打印 void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d->", cur->Data); cur = cur->next; } printf("\n"); }
3.扩容函数
//增容函数 LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->Data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
4.双链表的尾插
//双向带头循环链表的尾插 void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
5.双链表的尾删
//双向带头循环链表的尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); tailprev->next = phead; phead->prev = tailprev; //ListErase(phead->prev);//尾删就相当于复用Erase这个函数 }
6.双链表的头插
//双向带头循环链表的头插 void ListPushFront(LTNode* phead, LTDataType 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); }
7.双链表的头删
//双向带头循环链表的头删 void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead);//如果哨兵位的后继指针指向的是头，就不能去调用头删 LTNode* next = phead->next;//先找到头结点 LTNode* nextNext = next->next;//再找到头结点的下一个结点 phead->next = next->next; nextNext->prev = phead; }
8.双链表的查找
//双向带头循环链表的查找 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next;//从头结点出发 while (cur != phead) { //找到返回对应的地址 if (cur->Data == x) { return cur; } //找不到继续向后找 cur = cur->next; } //彻底找不到 return NULL; }
9. 双链表在pos位置之前插入结点
//双向带头循环链表pos位置之前插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* posPrev = pos->prev;//先找到pos的前一个结点的位置 LTNode* newnode = BuyListNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
