带头双向循环链表
- 下面的是带头双向的循环链表逻辑图
1.不同于单链表的特点
1.双向：双向是指在带头双向循环链表的结构中，存在两个指针来链接链表，其中一个指针是指向前一个结点，另一个指针指向后一个结点。
2.循环：单链表的尾部结点指向的是NULL，而双向循环链表的尾部结点指向头部的结点head，而head中指向前一个结点的指针则指向尾部结点（没理解了结合图看看哦）
3.带头：带头是指在双向循环链表中存在一个哨兵位作为链表的头部（这里别急，先知道有这个东西就行，下面会重点解释的）
2.一个结点中存储的元素
typedef int LTDataType; typedef struct ListNode { LTDataType data;//链表中存的值 struct ListNode* next;//指向下一个结点的指针 struct ListNode* prev;//指向上一个结点的指针 }ListNode;
3.初始化链表的函数 BuyListNode
//初始化双链表,创建节点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//malooc开辟一个结点的空间 if (newnode == NULL)//判断一下是否开辟空间成功 { perror("malloc failed\n"); exit(-1); } //初始化时把两个指针都置空 newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode;//返回创建好的链表节点 }
- 这一步比较简单，看看注释相信代码非常容易理解就不过多解释了。
4.创建链表的头节点 ListCreate
// 创建返回链表的头结点. ListNode* ListCreate() { ListNode* phead = BuyListNode(0);//开辟结点所需动态空间 phead->next = phead; phead->prev = phead; return phead; }
- 我们刚才介绍了链表的头是有一个哨兵位的，这个哨兵位在链表没有节点时，它中的头指针和尾指针都是指向自己的，那么这个哨兵位存在的意义是什么呢？
什么是哨兵位以及哨兵位存在的意义
哨兵位是一种在数据结构中使用的特殊值或节点，它的作用是简化算法的实现并提高效率。在查找操作中，可以将哨兵位预置在适当的位置上，以避免边界越界和找不到的情况。比如在链表中，哨兵位用来定位链表的位置，即使是空链表也会有哨兵位。在插入排序中，哨兵位用于辅助移动数据的循环处理，它可以存储需要移动的数据，并且不会受到后续操作的覆盖。通过使用哨兵位，可以简化算法的实现，减少边界判断的次数，提高程序的执行效率
在我们这个链表中具体来讲有什么意义呢？
在我们使用链表时，如果没有这个哨兵位，为了防止出现越界访问和空链表的情况，我们每一次使用链表时都得进行判空操作，这样会很影响程序运行的效率。而当存在这个哨兵位，当这是个空链表时，此时的phead就是一个指向自己的结点，不会导致出错，而当链表中存在结点时，它就是一个指向头结点的结点，同时也方便了我们的循环，我们直接把尾结点的next指向这个phead就行。
5.打印链表的函数 ListPrint
// 双向链表打印 void ListPrint(ListNode* phead) { assert(phead);//断言，判断是否有结点， printf("Phead");//没有其他结点，打印phead ListNode* cur = phead->next; while (cur!= phead) { printf(" <==> %d", cur->data); cur = cur->next; } printf("\n"); }
与之前单链表的打印基本相同，但是由于我们是循环链表，链表的尾部不再指向NULL，刚才我们说了此时链表的尾部的next指向phead，因此当我们遍历链表时，当链表再次等于phead时说明已经遍历过一次链表了，这就是我们遍历时循环停止的条件
6.销毁链表的函数 ListDestory
// 双向链表销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur!=phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); }
- 我们遍历整个链表，把每个结点都释放掉即可，遍历链表的循环条件与上面打印链表的相同。
- 好了，讲完上面的几个基础的接口，接下来才是重头戏，我们怎样往我们的链表中插入结点呢？
7.链表的头插与头删
- 其实关于插入与删除这一块，如果你能理解之前单链表的插入与删除，这一块的逻辑其实非常好理解。
头插
// 双向链表头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead);//断言， ListNode* frist = BuyListNode(x);//创建节点 ListNode* cur = phead->next; frist->next = cur; frist->prev = phead; cur->prev = frist; phead->next = frist; }
- 我们先通过图来看看这里想要达到的目标
- 首先，我们需要保存一下第一个位置的地址，也就是图中的cur，然后我们让first的next指向此时的cur，first的prev指向头head，这样就建立起了结点间的联系
- 但是由于我们需要链表是一个双头链表，我们此时还需要让head的next指向插入的first，cur的prev也指向first这样才算真正完成我们的头插
头删
// 双向链表头删 void ListPopFront(ListNode* phead) { assert(phead); ListNode* frist = phead->next; phead->next = frist->next; frist->next->prev = phead; free(frist); }
- 让phead的next指向first下一个结点，让first的下一个结点的prev指向phead，释放此时的free，头删完成
- 与头插类似，大家把上面的逻辑图反着看即可，就不再浪费篇幅画图了。
8.链表的尾插和尾删
尾插
// 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); assert(phead->prev); ListNode* newnode = BuyListNode(x); //ListInsert(phead, x); ListNode* tail = phead->prev;//起初的尾 newnode->next = phead;//插入的结点指向头 tail->next = newnode;//之前的尾指向现在的尾 newnode->prev = tail; tail = newnode; }
不同于单链表的是，由于我们的链表是循环链表，其实尾部的结点就保存在phead的prev中，因此不再需要遍历就能轻易的找到我们的尾部
- 此时，就比较简单啦，我们让现在的尾（d3）的next指向插入的newnode，让newnode的prev指向d3，next指向phead，再让phead的prev指向插入的newnode，即可完成尾插
尾删
// 双向链表尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->prev); ListNode* tail = phead->prev; ListNode* tailprev = phead->prev->prev; tailprev->next = phead; tail = tailprev; free(phead->prev); // ListErase(phead->prev); }
- 尾删需要我们找到现在尾的前一个结点，把它变成现在的尾，最后free掉现在的尾即可。
9.查找某个值是否在链表中的函数 ListFind
// 双向链表查找 ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead; while (cur->next != phead) { if (cur->data == x) return cur; else cur = cur->next; } return NULL; }
- 这个也非常简单，我们通过遍历链表的方式，通过比较结点中存储的值于我们需要查找的值来比较，找到了就返回当前结点位置的地址，没找到就返回NULL
10.修改pos前一个位置的值的函数 ListInsert
- 在这里先简单提一嘴修改pos位置的值的函数，非常简单所以就不浪费篇幅了，我们通过上面的ListFind找到后，直接把此位置的data修改成我们需要的x即可
cur->data=x;
- 进入正题
// 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { ListNode* newnode = BuyListNode(x);//创建结点 ListNode* posPrev = pos->prev; newnode->next = posPrev->next; posPrev->next = newnode; pos->prev = newnode; newnode->prev = posPrev; }
- 这里的pos位置是通过我们上面的查找函数找到的。
- 找到后就很简单啦,我们把pos位置之前的结点posprev的next指向newnode，让newnode的prev指向posprev，再让newnode的next指向pos，最后pos的prev指向插入的newnode即可。
11.删除pos位置的结点 ListErase
// 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->prev; ListNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); //pos = NULL; }
这个也是非常容易理解的，我们让pos位置的前一位置的结点posPrev指向pos后一位置的结点posNext即可。
最后一个小小的细节优化，当你在面试或者笔试等限定时间的时候，要求你完成一个带头双向循环链表，对于里面的头插头删，尾插尾删你也可以这样写，只需要引用上面这两个函数即可
//头插与头删 ListInsert(phead->next, x); ListErase(phead->next); //尾插与尾删 ListInsert(phead, x); ListErase(phead->prev);
- 想想看为啥
- 其实我们的头插头删与尾插尾删无非是对特殊pos位置的操作嘛，因此自然可以引用上面的这两个函数啦
总结
- 今天的内容到这里就结束了，带头双向循环链表可能不是那么好理解，如果你真的想要深入看懂的话一定要配合逻辑图自己尝试去敲一敲，光看不练是不可能学好的哦！！
- 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！
