💓1.总体布局
1.创建双向链表节点
LTNode* CreateLTNode(LTDataType x)；
2.初始化双向循环链表
LTNode* LTInit();
3.打印双向循环链表
void LTPrint(LTNode* phead);
4.循环双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);
5.双向循环链表中删除尾节点
void LTPopBack(LTNode* phead);
6.双向链表的头插操作
void LTPushFront(LTNode* phead, LTDataType x);
7.双向链表的头部删除操作
void LTPopFront(LTNode* phead);
8.循环链表中查找指定值节点
LTNode* LTFind(LTNode* phead, LTDataType x);
9.该函双向链表中指定节点pos的前面插入一个新的节点
void LTInsert(LTNode* pos, LTDataType x);
10.双向链表中删除某个节
void LTErase(LTNode* pos);
11.销毁一个循环双向链表
void LTDestroy(LTNode * phead);
💓2.详细解读
❣️1.创建双向链表节点
函数输入参数为节点的值x，函数返回一个指向节点的指针。
函数内部实现：
使用malloc函数为新节点分配内存空间，分配的大小为一个LTNode结构体的大小。
判断内存分配是否成功，如果分配失败，则输出错误信息并退出程序。
对新节点进行初始化，将节点的值设置为x，next指针和prev指针设置为NULL。
返回指向新节点的指针。
LTNode* CreateLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
❣️2.初始化双向循环链表
链表中的每个节点都是LTNode类型的结构体，其中包含一个指向前一个节点的指针prev和一个指向后一个节点的指针next。该函数首先创建一个值为-1的头节点，并将头节点的前一个节点和后一个节点都指向头节点本身，以形成一个空的双向循环链表。最后返回头节点的指针。
LTNode* LTInit() { LTNode* phead = CreateLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
❣️3.打印双向循环链表
其参数为双向循环链表的头结点指针，函数内部会从头结点开始遍历链表，并依次打印每个节点的值，直到遍历到头结点为止。最终输出的内容是形如“哨兵位<=>x<=>y<=>z<=>哨兵位”的字符串，其中x、y、z分别表示链表中的元素值。
void LTPrint(LTNode* phead) { assert(phead); printf("哨兵位<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->val); cur = cur->next; } printf("\n"); }
❣️4.循环双向链表尾插
将一个元素x插入到链表的最后一个节点的后面。
函数接收两个参数，一个是指向链表头结点的指针phead，另一个是要插入到链表尾部的元素x。
首先使用assert函数检查参数phead是否为NULL，如果是则直接终止程序。
接着定义两个指针tail和newnode，tail指向链表的最后一个节点，newnode是要插入到链表尾部的新节点。
然后将新节点插入到链表尾部。具体步骤如下：
让tail节点的next指针指向newnode节点，即tail->next = newnode。
让newnode节点的prev指针指向tail节点，即newnode->prev = tail。
让newnode节点的next指针指向链表头节点phead，即newnode->next = phead。
让phead节点的prev指针指向newnode节点，即phead->prev = newnode。
这样就完成了在链表尾部插入新节点的操作。
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = CreateLTNode(x); // phead tail newnode tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
❣️5.双向循环链表中删除尾节点
具体分析如下：
首先使用assert函数来判断phead是否为空，如果为空则程序立即终止。
由于是双向循环链表，在删除尾节点之前需要判断链表中是否存在节点。使用assert函数来判断phead的next指针是否指向phead本身，如果是则链表为空，程序立即终止。
设置指针tail指向链表的尾节点，并使用tailPrev指针来记录尾节点的前一个节点。
释放tail指向的节点，即删除尾节点。
将tailPrev节点的next指针指向phead节点，即将链表尾节点删除后，将尾节点的前一个节点的next指针指向头节点。
将phead节点的prev指针指向tailPrev节点，即将链表尾节点删除后，将头节点的prev指针指向链表的倒数第二个节点，以保证链表仍然是双向循环的。
注意，该函数的前提条件是链表中至少存在一个节点，否则会因为assert函数判断失败而终止程序。在使用该函数时需要注意链表的状态。
void LTPopBack(LTNode* phead) { assert(phead); // 空 assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }
❣️6.双向链表的头插操作
将一个新节点插入到链表的第一个位置。
输入参数：
phead：头结点指针，其中包含链表的头指针和尾指针；
x：要插入的节点的值。
函数流程：
创建新节点，其数据域为x；
获取原链表中第一个节点的指针first；
将新节点插入到头结点之后的位置，使得新节点为原链表的第一个节点，first成为新节点的后继节点；
将原第一个节点的prev指针指向新节点，完成头插操作。
注意事项：
函数中使用了assert宏，用于判断头结点是否存在；
操作需要改变多个节点的指针，需要仔细考虑顺序和细节。
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = CreateLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
❣️7.双向链表的头部删除操作
1. 首先使用assert函数判断传入的链表头结点指针phead是否为空，如果为空则终止程序运行。
2. 再通过assert函数判断链表是否为空，即头结点的下一个结点是否还是头结点自身，如果是则说明链表为空，同样终止程序运行。
3. 取出链表头结点的下一个结点first，以及第二个结点second。
4. 将头结点的下一个结点指向第二个结点，同时将第二个结点的前一个结点指向头结点，完成删除操作。
5. 最后使用free函数释放被删除的结点first的内存空间，并将first指针置为空。
void LTPopFront(LTNode* phead) { assert(phead); // 空 assert(phead->next != phead); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; }
❣️8.循环链表中查找指定值节点
参数说明：
phead：指向循环链表头节点的指针。
x：需要查找的值。
函数实现步骤：
首先，断言链表头节点不为空。
定义一个指针 cur，指向链表的第一个节点。
遍历链表，如果找到了值为 x 的节点，直接返回该节点指针。
如果遍历完整个链表都没有找到值为 x 的节点，就返回 NULL 指针，表示没有找到。
需要注意的是，该函数是针对循环链表的查找实现，因此需要判断 cur 指针是否回到了头节点 phead，如果回到了头节点，则表示遍历完整个链表，需要退出循环。
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; }
❣️9.该函双向链表中指定节点pos的前面插入一个新的节点
节点的值为x。函数实现需要注意以下几点：
首先需要判断pos节点是否存在，若不存在则直接返回。
创建一个新节点newnode，并将其值赋为x。
获取pos节点的前一个节点posPrev，posPrev节点和newnode节点之间需要插入新的节点。
将posPrev节点的next指针指向newnode节点，将newnode节点的prev指针指向posPrev节点，将newnode节点的next指针指向pos节点，将pos节点的prev指针指向newnode节点。
确保插入操作顺利完成后，函数返回。
// 在pos前面的插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = CreateLTNode(x); // posprev newnode pos posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
❣️10.双向链表中删除某个节
输入参数是要删除的节点指针pos。
首先通过断言语句assert(pos)来检查输入参数是否为空。
然后通过pos指针找到它的前驱节点posPrev和后继节点posNext，将它们之间的连接断开，即将posPrev的next指针指向posNext，将posNext的prev指针指向posPrev。
最后通过free函数释放pos指向的内存空间，完成删除操作。
// 删除pos位置 void LTErase(LTNode* pos) { assert(pos); LTNode* posNext = pos->next; LTNode* posPrev = pos->prev; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
❣️11.销毁一个循环双向链表
参数phead是链表的头指针，其指向一个LTNode类型的结构体，该结构体中有两个指针，分别指向链表的头节点和尾节点。
首先，函数中使用了断言assert(phead)，判断参数phead是否为空指针，如果是，程序会终止运行，有助于在调用函数时发现错误。
然后，定义一个指针cur指向链表第一个节点，然后使用while循环遍历除了头节点之外的所有节点，直到遍历完所有节点为止。
在循环中，使用一个指针next指向当前节点的下一个节点，然后释放当前节点的内存空间，最后将cur指向下一个节点。
循环结束后，释放链表头节点的内存空间，销毁整个链表。
void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
💓3.部分代码进阶
❣️1.根据2—9：void LTInsert(LTNode* pos, LTDataType x)
1.循环双向链表尾插操作
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
2. 双向链表的头插操作
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x); }
❣️2.根据2—10void LTErase(LTNode* pos)
1.双向循环链表中删除尾节点
void LTPopBack(LTNode* phead) { assert(phead); LTErase(phead->prev); }
2. 双向链表的头部删除操作
void LTPopFront(LTNode* phead) { assert(phead); // 空 assert(phead->next != phead); LTErase(phead->next); }
💓4.整体代码
❣️1.List.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType val; }LTNode; LTNode* CreateLTNode(LTDataType x); LTNode* LTInit(); void LTPrint(LTNode* phead); void LTPushBack(LTNode* phead, LTDataType x); void LTPopBack(LTNode* phead); void LTPushFront(LTNode* phead, LTDataType x); 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.List.c
#include"List.h" LTNode* CreateLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } LTNode* LTInit() { LTNode* phead = CreateLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTPrint(LTNode* phead) { assert(phead); printf("哨兵位<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->val); cur = cur->next; } printf("\n"); } void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); //LTNode* tail = phead->prev; //LTNode* newnode = CreateLTNode(x); phead tail newnode //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; LTInsert(phead, x); } void LTPopBack(LTNode* phead) { assert(phead); // 空 assert(phead->next != phead); /*LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev;*/ LTErase(phead->prev); } //void LTPushFront(LTNode* phead, LTDataType x) //{ // assert(phead); // LTNode* newnode = CreateLTNode(x); // // newnode->next = phead->next; // phead->next->prev = newnode; // // phead->next = newnode; // newnode->prev = phead; // //} void LTPushFront(LTNode* phead, LTDataType x) { /*assert(phead); LTNode* newnode = CreateLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode;*/ LTInsert(phead->next, x); } void LTPopFront(LTNode* phead) { assert(phead); // 空 assert(phead->next != phead); /*LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL;*/ LTErase(phead->next); } LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; } // 在pos前面的插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = CreateLTNode(x); // posprev newnode pos posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; } // 删除pos位置 void LTErase(LTNode* pos) { assert(pos); LTNode* posNext = pos->next; LTNode* posPrev = pos->prev; posPrev->next = posNext; posNext->prev = posPrev; free(pos); //pos = NULL; } void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); //phead = NULL; }
❣️3.Test.c
#include "List.h" void TestList1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 5); LTPushBack(plist, 4); LTPrint(plist); LTPushFront(plist, 10); LTPrint(plist); } void TestList2() { LTNode* plist = LTInit(); LTPushFront(plist, 10); LTPushFront(plist, 20); LTPushFront(plist, 30); LTPushFront(plist, 40); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); //LTPopFront(plist); //LTPrint(plist); } void TestList3() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 5); LTPushBack(plist, 4); LTPrint(plist); LTNode* pos = LTFind(plist, 3); if (pos) { pos->val *= 10; } LTPrint(plist); LTInsert(pos, 30000); LTPrint(plist); LTInsert(plist, -1); LTPrint(plist); LTInsert(plist, -2); LTPrint(plist); } void TestList4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 5); LTPushBack(plist, 4); LTPrint(plist); LTNode* pos = LTFind(plist, 3); if (pos) { LTErase(pos); pos = NULL; } LTPrint(plist); LTDestroy(plist); plist = NULL; } int main() { TestList4(); return 0; }
💓5.优缺点
带头双向循环链表的优点：
相对于单向链表，双向链表可以在遍历列表时可以很方便地获取前驱节点，这是非常有用的。因此，双向链表的操作速度要快于单向链表，尤其是在需要频繁地对链表进行插入和删除操作时。
循环链表能够有效地利用链表结构，实现了一种无限循环的数据结构，可以在遍历列表时可以非常方便地实现循环。
带头结点的链表可以避免一些特殊情况，例如对于空链表的插入和删除操作，带头节点的链表不需要特殊处理。
带头双向循环链表的缺点：
相对于单向链表，双向链表需要多维护一个指向前驱节点的指针，这会增加空间复杂度。
双向链表的实现相对单向链表来说较为复杂，需要处理的指针较多，同时也需要对链表的多个指针进行操作，这在一些情况下导致代码会比单向链表的代码更为复杂。
总的来说，带头双向循环链表在需要频繁对链表进行插入和删除操作时，以及需要实现无限循环链表时非常有用。但是相比于单向链表，需要额外维护一个指向前驱节点的指针，同时实现也较为复杂。
