到目前为止，我们对顺序表，链表都进行了初步是实现，其中仅完成了单链表。要知道，链表可不仅仅用是否有头结点来区分,另外还有单向、双向，循环和非循环。将这些情况组合起来可以组成 8 种不同的链表，由于带头双向循环链表的使用情况较多，本章就对带头双向循环链表进行实现。

1. 双向链表的实现

1.1 简单图例

1.2 结点的定义

typedef int LTDataType;
typedef struct ListNode
{LTDataType val;			//数据域struct ListNode* prev;	//指针域（存放前驱结点的地址）struct ListNode* next;	//指针域（存放后继结点的地址）
}ListNode;

注意：双向链表有 两个 指针域，一个指向前驱 结点，一个指向后继 结点。

1.3 新结点的创建

ListNode* CreateListNode(LTDataType x) {						//x为新结点的val部分（数据域）ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//为新结点开辟新空间if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;				//返回新结点的地址
}

1.4 链表的初始化

  这里链表的初始化只是针对于头结点，相当于给头结点一个初始的值。

ListNode* DListInit() {ListNode* phead = CreateListNode(-1);	//给头结点的值赋为 -1phead->next = phead;phead->prev = phead;	//指针域全部指向本身（初始化）return phead;
}

测试时即可使用：

ListNode* Dlist=DListInit();

1.5 结点的插入

1.5.1 头部插入（头插）

注意：头部插入不是在头结点之前插入，而是在 头结点后面第一个结点之前插入。

void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}

图解：

1.5.2 尾部插入（尾插）

void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

图解：

1.5.3 任意位置（前）插入

  在这部分功能上双向链表就比单链表好实现得多，双向链表自带一个前驱结点的地址，不需要像单链表一样从头开始遍历。

void DListInsert(ListNode* pos, LTDataType x) {assert(pos);	//判断pos不为空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}

此部分图例可参考头插（同原理）

1.6 结点的删除

1.6.1 头部删除（头删）

void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}

图解：

1.6.2 尾部删除（尾删）

  删除尾部结点只需要将倒数第二个的结点的位置找到，尾部结点的空间就可以直接释放了，接下来就直接链接头结点。

void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}

图解：

1.6.3 任意位置删除

void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}

此处图例可参考头删 尾删（同原理）

1.7 查找结点

  在顺序表中，当结点的位置被找到时，函数会返回顺序表的下标。在链表中，返回的就是结点的地址。

ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;	//找不到对应的结点返回NULL
}

1.8 链表的打印

void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(头结点)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(头结点)\n");
}

打印部分可自行美化

1.9 链表的销毁

void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next;		//先存储下一个结点的地址free(cur);						//再释放当前结点cur = Next;						//然后把Next给cur}free(phead);phead = NULL;
}

2. 功能综合

  功能整合起来代码较长，另外也可以通过接口的方式实现（层次分明），有不懂的可参考上文图解自行消化，main部分可以自行调用函数进行测试。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//创建新结点
ListNode* CreateListNode(LTDataType x) {						//x为新结点的val部分（数据域）ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//为新结点开辟新空间if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;				//返回新结点的地址
}//初始化头结点
ListNode* DListInit() {ListNode* phead = CreateListNode(-1);	//给头结点的值赋为 -1phead->next = phead;phead->prev = phead;	//指针域全部指向本身（初始化）return phead;
}//头插
void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}//尾插
void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//任意位置（前）插入
void DListInsert(ListNode* pos, LTDataType x) {assert(pos);	//判断pos不为空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}//头删
void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}//尾删
void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}//任意位置删除
void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}//查找结点
ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;	//找不到对应的结点返回NULL
}//打印链表
void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(头结点)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(头结点)\n");
}//销毁链表
void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next;		//先存储下一个结点的地址free(cur);						//再释放当前结点cur = Next;						//然后把Next给cur}free(phead);phead = NULL;
}int main() {ListNode* Dlist = DListInit();  //初始化DListPushBack(Dlist, 1);DListPushBack(Dlist, 2);DListPushBack(Dlist, 3);DListPushBack(Dlist, 5);DListPushBack(Dlist, 4);		//尾插DListPrint(Dlist);				//打印DListPopBack(Dlist);			//尾删DListPrint(Dlist);				//打印DListPushFront(Dlist, 99);DListPushFront(Dlist, 78);DListPushFront(Dlist, 666);		//头插DListPrint(Dlist);				//打印DListPopFront(Dlist);			//头删DListPrint(Dlist);				//打印return 0;
}

运行结果：

3. 误区纠正

1. 增删查改的操作对象的主体不是头结点，头的增删动的是 head->next。
2. 头结点只是起辅助作用，判断带头链表是否为空，要从头结点->next开始判断。
3. 双向链表不能完全替代单链表，单链表相对于双向链表来说 内存使用少 ，比双向链表少一个指针。

4. 正确使用链表

• 理解 prev 和 next 的指向关系。
• 根据实际情况判断链表是否需要 头结点、循环、双向 。