要学习带头双向循环链表，需要有普通链表的基础知识-------------------->：
带头双向循环链表的意思是：
1.带头：有一个哨兵位的头节点，这个头节点不存储有效数据，如下图所示：
2.双向：单链表的节点中只有指向下一个节点的next指针，双向链表的节点多了一个指向上一个节点的prev指针，如下图所示：
3.循环：这个链表是循环的，我们可以把它想象成一个圈，如下图所示：
所以带头双向循环链表的逻辑图是这样的：
实际中使用的链表数据结构，都是带头双向循环链表，另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现起来简单。
讯享网
讯享网
初始化和新增节点用的都是同一个函数，除了检查在堆上是否开辟空间外，重点就是将prev和next指针指向自己，这样做方便后续的管理。初始化也是使用这个函数的好处在于不用二级指针，在外界用一级指针来接收就可以了。
带头双向循环链表是循环的，但是它有一个哨兵位头节点，所以遍历从哨兵位头节点的下一个节点开始，当遍历转完一圈后又到了哨兵位头节点时，遍历就完成了。遍历方式和普通链表基本一样，只是判断结束的方式不一样而已。
单链表中尾插需要找尾，带头双向循环链表不需要找尾，head->prev就是尾节点(单链表尾插的时间复杂度是O(n),带头双向循环链表尾插的时间复杂度是O(1))。
下图中如果我们要尾插数据3节点，影响到的有尾节点和头节点
带头双向循环链表逻辑上是很复杂的，尾插的方式有多种，看不懂图的同学可以参考我下面这种尾插的方法：
1.将数据3节点的prev指针指向尾节点：
伪代码：(数据3节点)->prev = head -> prev
2.将哨兵位头节点(head)的prev指向数据3节点：
伪代码：head -> prev = (数据3节点)
3.将数据3节点的next指向哨兵位头节点(head)：
伪代码：(数据3节点)->next = head
4.将数据2节点的next指向数据3节点，尾插完成(此时的数据2节点已经不是尾节点了):
伪代码：(数据3节点)->prev->next = (数据3节点);
讯享网
如果我们删除下图中的数据3尾节点，只需要将head节点的prev指向数据2节点，数据2节点的next指向head节点尾删就完成了。需要创建一个指针变量(del)来保存数据3节点，防止数据3节点丢失。
1.将head节点的prev指向数据2节：
伪代码：head->prev = del->prev
2.数据2节点的next指向head节点：
伪代码：del->prev->next = head
3.释放掉数据3节点，尾插完成：
伪代码：free(del)
尾删需要注意的点：只剩下一个哨兵位头节点(head)时,说明没有节点了，还删什么，建议用assert断言一下直接报错。
下图中如果我们要头插(数据1前面插入)数据3节点，需要改动head节点和数据1节点
1.将数据3节点的prev指向head节点，next指向数据1节点：
伪代码：(数据3节点)->prev = head; (数据3节点)->next = head->next;
2.将head的next指向数据3节点：
伪代码：head->next = (数据3节点)
3.将数据1节点的prev指向数据3节点,头插完成
伪代码：(数据3节点)->next->prev = (数据3节点)
讯享网
下图中，如我们要头删(删除数据1节点),会影响到head节点和数据2节点，我们先用指针变量del保存数据1节点，方便后面的代码编写和释放。
1.将head的next指向数据2节点：
伪代码：head->next = del->next
2.将数据2节点的prev指向head：
伪代码：del->next->prev = head:
3.释放掉数据1，头删除完成。
伪代码：free(del)
1.销毁
带头双向循环链表的销毁非常简单，循环调用头删或尾删，循环结束条件是head->next != head，前面在初始化和新增节点的那个函数里，我们让prev和next指向自己的好处就体现出来了，最后最释放掉哨兵位头节点，带头双向循环链表的销毁就完成了。
讯享网
2.查找
查找和遍历基本一样，找到了返回对应的节点，找不到就返回哨兵位头节点。
假设pos位置是下图中的数据2节点，我们要在数据2的前面插入数据4节点。
1.将数据4节点的next指向数据2节点，prev指向数据1节点：
伪代码：(数据4节点)->next = pos; (数据4节点)->prev = pos->prev;
2.将数据1节点的next指向数据4节点：
伪代码：(数据4节点)->prev->next = (数据4节点)
3.将数据2节点的prev指向数据4节点，插入完成：
伪代码：pos->prev = (数据4节点)
讯享网
假设pos位置是下图中的数据2节点，我们要删除数据2节点。
1.先将数据1节点的next指向数据3节点：
伪代码：pos->prev->next = pos->next;
2.将数据3节点的prev指向数据1节点：
伪代码：pos->next->prev = pos->prev;
3.释放掉数据2节点，删除完成：
伪代码：free(pos)
其实头插和尾插可以复用在pos的前面进行插入(void ListInsert(ListNode* pos, LTDataType x))这个函数，为什么不提前说明和实现的原因是因为我觉得这样做不好，老老实实的画图加上伪代码可以加深大家的印象(虽然不知道有多少人能看)，下面是复用在pos的前面进行插入(void ListInsert(ListNode* pos, LTDataType x))这个函数的头插和尾插：
头插：
讯享网
尾插：
头插尾删复用的代码是删除pos位置的结点(ListErase(ListNode* pos))这个函数
头删：
讯享网
尾删：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/182230.html