前言
在上一期中我们介绍了单链表，也做了一些练习题，在一些题中使用单链表会十分繁琐。因为单链表只能正着走，不能倒着走，例如：回文、逆置。本期我们将学习带头双向循环链表。
1. 双向链表
带头双向循环链表的结构
特点：带头双向循环链表结构最复杂，一般用在单独存储数据。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来多优势，实现反而简单了。
2. 链表的实现
2.1 初始化
LTNode* LTInit() { LTNode* phead = CreateLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
2.2 尾插
带哨兵位的链表尾插时不用判断是否有节点，两种情况的插入相同，而且还不用传递二级指针。
void LTPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = CreateLTNode(x); phead->prev->next = newnode; newnode->prev = phead->prev; newnode->next = phead; phead->prev = newnode; }
2.3 尾删
在尾删时我们通过 assert(phead->next != phead); 判断链表是否有节点。同时这个代码就有普遍性，不用单独考虑剩一个节点的情况。
void LTPopBack(LTNode* phead) { assert(phead); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead; }
2.4 头插
头删重要的是赋值的顺序，顺序错误会找不到后面的节点，导致内存泄漏。带哨兵位的链表不需要传递二级指针，因为改变的是结构体的变量。
void LTPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = CreateLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
2.5 头删
我们可以多定义几个指针来保存后面节点的地址，这样就不会造成节点的丢失，不用考虑赋值的顺序，会更加方便。
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; LTNode* next = tail->next; phead->next = next; next->prev = phead; free(tail); tail = NULL; }
2.6 在pos位置之前插入
void LTInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* posprev = pos->prev; LTNode* newnode = CreateLTNode(x); posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; }
2.7 删除pos位置
void LTErase(LTNode* pos) { assert(pos); LTNode* posprev = pos->prev; LTNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; }
3.双向链表完整源码
List.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDateType; typedef struct ListNode { LTDateType val; struct ListNode* next; struct ListNode* prev; }LTNode; LTNode* LTInit(); void LTPrint(LTNode* phead); void LTPushBack(LTNode* phead, LTDateType x); void LTPushFront(LTNode* phead, LTDateType x); void LTPopBack(LTNode* phead); void LTPopFront(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDateType x); void LTInsert(LTNode* pos, LTDateType x); void LTErase(LTNode* pos); void LTDestroy(LTNode* phead);
List.c
#include"List.h" LTNode* CreateLTNode(LTDateType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; } LTNode* LTInit() { LTNode* phead = CreateLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("<=>哨兵位<=>"); while (cur != phead) { printf("%d<=>", cur->val); cur = cur->next; } printf("\n"); } void LTPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = CreateLTNode(x); phead->prev->next = newnode; newnode->prev = phead->prev; newnode->next = phead; phead->prev = newnode; } void LTPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = CreateLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; } void LTPopBack(LTNode* phead) { assert(phead); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead; } void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; LTNode* next = tail->next; phead->next = next; next->prev = phead; free(tail); tail = NULL; } LTNode* LTFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; } void LTInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* posprev = pos->prev; LTNode* newnode = CreateLTNode(x); posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; } void LTErase(LTNode* pos) { assert(pos); LTNode* posprev = pos->prev; LTNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; } 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; }
通过上面链表的实现，我们已经感受到了带头双向循环链表的方便和简单，它不需要去考虑链表是否有元素，还可以找到前一个元素，在我们使用中提供很大的便利。
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。
