一、带头双向循环链表的定义和结构
1、定义
带头双向循环链表，有一个数据域和两个指针域。一个是前驱指针，指向其前一个节点；一个是后继指针，指向其后一个节点。
// 定义双向链表的节点 typedef struct ListNode { LTDataType data; // 数据域 struct ListNode* prev; // 前驱指针 struct ListNode* next; // 后继指针 }ListNode;
2、结构
带头双向循环链表：在所有的链表当中 结构最复杂，一般用在 单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多 优势，实现反而简单了。
二、带头双向循环链表接口的实现
1、创建文件
- test.c（主函数、测试顺序表各个接口功能）
- List.c（带头双向循环链表接口函数的实现）
- List.h（带头双向循环链表的类型定义、接口函数声明、引用的头文件）
2、List.h 头文件代码
// List.h // 带头+双向+循环链表增删查改实现 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDataType; // 定义双向链表的节点 typedef struct ListNode { LTDataType data; // 数据域 struct ListNode* prev; // 前驱指针 struct ListNode* next; // 后继指针 }ListNode; // 动态申请一个新节点 ListNode* BuyListNode(LTDataType x); // 创建返回链表的头结点 ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* plist); // 双向链表打印 void ListPrint(ListNode* plist); // 双向链表尾插 void ListPushBack(ListNode* plist, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* plist); // 双向链表头插 void ListPushFront(ListNode* plist, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* plist); // 双向链表查找 ListNode* ListFind(ListNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos); // 双向链表的判空 bool ListEmpty(ListNode* phead); // 获取双向链表的元素个数 size_t ListSize(ListNode* phead);
三、在 List.c 上是实现各个接口函数
1、动态申请一个新结点
// 动态申请一个新节点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }
2、创建返回链表的头结点（初始化头结点）
// 创建返回链表的头结点 ListNode* ListCreate() { ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点 phead->next = phead; phead->prev = phead; return phead; }
也可以用下面这个函数（道理一样）：
// 初始化链表 void ListInit(ListNode** pphead) { *pphead = BuyListNode(-1); // 动态申请一个头节点 (*pphead)->prev = *pphead; // 前驱指针指向自己 (*pphead)->next = *pphead; // 后继指针指向自己 }
头指针初始指向 NULL，初始化链表时，需要改变头指针的指向，使其指向头节点，所以这里需要传二级指针。
初始化带头双向循环链表，首先动态申请一个头结点，头结点的前驱和后继指针都指向自己，形成一个循环。
3、双向链表的销毁
// 双向链表的销毁 void ListDestroy(ListNode** pphead) { assert(pphead); assert(*pphead); ListNode* cur = (*pphead)->next; while (cur != *pphead) { ListNode* next = cur->next; // 记录cur的直接后继节点 free(cur); cur = next; } free(*pphead); // 释放头节点 *pphead = NULL; // 置空头指针 }
销毁链表，最后要将头指针 plist 置空，所以用了二级指针来接收。这里也可以用一级指针，但要在函数外面置空 plist 。
一级指针写法：
void ListDestroy(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
4、双向链表的打印
// 打印双向链表 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; // 记录第一个节点 printf("head <-> "); while (cur != phead) { printf("%d <-> ", cur->data); cur = cur->next; } printf("head\n"); }
5、双向链表的尾插
// 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); // 头指针不能为空 /* ListNode* newnode = BuyListNode(x); // 动态申请一个节点 ListNode* tail = phead->prev; // 记录尾节点 tail->next = newnode; // 尾节点的后继指针指向新节点 newnode->prev = tail; //2、新节点的前驱指针指向尾节点 newnode->next = phead; // 新节点的后继指针指向头节点 phead->prev = newnode; // 头节点的前驱指针指向新节点 */ ListInsert(phead, x); }
6、双向链表的尾删
// 双向链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除 /* ListNode* tail = phead->prev; // 记录尾节点 ListNode* tailPrev = tail->prev; // 记录尾节点的直接前驱 tailPrev->next = phead; // 尾节点的前驱节点的next指针指向头节点 phead->prev = tailPrev; // 头节点的prev指针指向尾节点的前驱节点 free(tail); // 释放尾节点 */ ListErase(pHead->prev); }
7、双向链表的头插
// 双向链表的头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); /* ListNode* newnode = BuyListNode(x); // 申请新节点 ListNode* pheadNext = phead->next; // 记录第一个节点 // 头节点和新节点建立链接 phead->next = newnode; newnode->prev = phead; // 新节点和第一个节点建立链接 newnode->next = pheadNext; pheadNext->prev = newnode; */ ListInsert(phead->next, x); }
8、双向链表的头删
// 双向链表的头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除 /* ListNode* pheadNext = phead->next; // 记录第一个节点 // 头节点和第一个节点的后继节点建立链接 phead->next = pheadNext->next; pheadNext->next->prev = phead; free(pheadNext); // 头删 */ ListErase(phead->next); }
9、查找双向链表中的元素
// 在双向链表中查找元素，并返回该元素的地址 ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; //找到了 返回该元素的地址 } cur = cur->next; } return NULL; //没找到 返回NULL }
10、在指定pos位置之前插入元素
// 在指定pos位置之前插入元素 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyListNode(x); // 申请一个节点 ListNode* posPrev = pos->prev; // 记录pos的直接前驱 // pos的直接前驱和新节点建立链接 posPrev->next = newnode; newnode->prev = posPrev; // 新节点和pos建立链接 newnode->next = pos; pos->prev = newnode; }
实现了该函数后，可以尝试改进头插函数（pos相当于链表的第一个节点）和尾插函数（pos相当于链表的头节点），这样写起来更简便。
11、删除指定pos位置的元素
// 删除指定pos位置的元素 void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->prev; // 记录pos的直接前驱 ListNode* posNext = pos->next; // 记录pos的直接后继 // pos的直接前驱和直接后继建立链接 posPrev->next = posNext; posNext->prev = posPrev; free(pos); // 释放pos位置的元素 //pos = NULL; }
实现了该函数后，可以尝试改进头删函数（pos相当于链表的第一个节点）和尾删函数（pos相当于链表的最后一个节点），这样写起来更简便。
12、双向链表的判空
// 双向链表的判空 bool ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; //为空 返回ture 否则返回false }
13、获取双向链表的元素个数
// 获取双向链表的元素个数 size_t ListSize(ListNode* phead) { assert(phead); size_t size = 0; ListNode* cur = phead->next; // 记录第一个节点 while (cur != phead) { size++; cur = cur->next; } return size; }
四、代码整合
// List.c #include "List.h" // 动态申请一个新节点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; } // 创建返回链表的头结点 ListNode* ListCreate() { ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); // 哨兵位头结点 phead->next = phead; phead->prev = phead; return phead; } // 双向链表的销毁 void ListDestroy(ListNode** pphead) { assert(pphead); assert(*pphead); ListNode* cur = (*pphead)->next; while (cur != *pphead) { ListNode* next = cur->next; // 记录cur的直接后继节点 free(cur); cur = next; } free(*pphead); // 释放头节点 *pphead = NULL; // 置空头指针 } // 打印双向链表 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; // 记录第一个节点 printf("head <-> "); while (cur != phead) { printf("%d <-> ", cur->data); cur = cur->next; } printf("head\n"); } // 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); // 头指针不能为空 ListInsert(phead, x); } // 双向链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除 ListErase(pHead->prev); } // 双向链表的头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); } // 双向链表的头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); // 只剩头节点时 链表为空 不能再继续删除 ListErase(phead->next); } // 在双向链表中查找元素，并返回该元素的地址 ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; //找到了 返回该元素的地址 } cur = cur->next; } return NULL; //没找到 返回NULL } // 在指定pos位置之前插入元素 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyListNode(x); // 申请一个节点 ListNode* posPrev = pos->prev; // 记录pos的直接前驱 // pos的直接前驱和新节点建立链接 posPrev->next = newnode; newnode->prev = posPrev; // 新节点和pos建立链接 newnode->next = pos; pos->prev = newnode; } // 删除指定pos位置的元素 void ListErase(ListNode* pos) { assert(pos); ListNode* posPrev = pos->prev; // 记录pos的直接前驱 ListNode* posNext = pos->next; // 记录pos的直接后继 // pos的直接前驱和直接后继建立链接 posPrev->next = posNext; posNext->prev = posPrev; free(pos); // 释放pos位置的元素 //pos = NULL; } // 双向链表的判空 bool ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; //为空 返回ture 否则返回false } // 获取双向链表的元素个数 size_t ListSize(ListNode* phead) { assert(phead); size_t size = 0; ListNode* cur = phead->next; // 记录第一个节点 while (cur != phead) { size++; cur = cur->next; } return size; }
