【数据结构】带头+双向+循环链表（DList）（增、删、查、改）详解

一、带头双向循环链表的定义和结构

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;
}