[数据结构]带头双向循环链表的实现与应用

一、引言

链表作为数据结构中的重要一员，在众多应用场景中发挥着关键作用。本文旨在深入探讨带头双向循环链表的基本概念、实现机制及其优缺点，以便读者能够更全面地理解并有效运用这一数据结构。

---

二、链表的基本概念

1、链表是什么

链表是一种线性数据结构，但与传统的顺序表（例如数组）不同，链表中的元素（节点）在内存中并非连续存储。每个节点包含一个数据域和一个或多个指针域，这些指针域指向链表中的其他节点，从而构成链式结构。

2、链表与顺序表的区别

• 存储方式：顺序表采用连续存储方式，而链表则采用分散存储方式。
• 访问速度：顺序表支持通过索引直接访问元素，因此访问速度较快；而链表则需要从头节点开始顺序遍历，访问速度相对较慢。
• 插入与删除操作：顺序表在插入或删除元素时需要移动大量元素，效率较低；链表则通过修改指针指向即可完成插入和删除操作，效率较高。
• 内存利用率：顺序表在创建时需预先分配连续内存空间，可能导致内存浪费；链表则可根据需求动态分配内存，内存利用率更高。

3、带头双向循环链表

带头双向循环链表是一种特殊的链表结构，具有以下特点：

• 头节点：通常不存储实际数据，仅作为链表的起始点，便于插入和删除操作。
• 双向指针：每个节点包含两个指针，一个指向下一个节点，另一个指向上一个节点，从而支持从任意节点向前或向后遍历链表。
• 循环结构：链表的最后一个节点指向头节点，形成一个环形结构，便于从链表的任意位置开始遍历整个链表。
  这种结构使得带头双向循环链表在插入、删除以及遍历操作上具有更高的灵活性和效率。

---

三、带头双向循环链表的实现

1、结构体定义

在C语言环境中，我们通过定义结构体来构建带头双向循环链表。该结构体融合了数据域与指针域，为链表节点提供了全面的功能支持。以下是一个典型的结构体定义示例：

typedef int DataType;typedef struct ListNode {DataType data;struct ListNode* prev;struct ListNode* next;
}L;

2、初始化

链表初始化是构建带头双向循环链表的首要步骤。此过程涉及头节点的内存分配、指针的初始化设置，以及环形结构的构建。以下是具体的初始化实现代码：

void Init(L** head)
{assert(head != NULL && *head == NULL);L* pos = (L*)malloc(sizeof(L));if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}pos->next = pos;pos->prev = pos;pos->data = 0;*head = pos;
}

3、销毁

链表销毁是释放链表所占内存资源的关键步骤。此过程需遍历链表，逐个释放节点的内存，并将头节点指针置为NULL。以下是具体的销毁实现代码：

void Destroy(L** head)
{if (head == NULL)return;L* h = *head;while (*head != h){L* next = (*head)->next;free(*head);*head = next;}*head = NULL;
}

4、显示

链表显示是验证链表正确性的重要手段。此过程通过遍历链表，并打印每个节点的数据部分来实现。以下是具体的显示实现代码：

void Print(L** head, void (*Prin) (DataType))
{assert(head != NULL && Prin != NULL);printf("head->");for (L* i = (*head)->next; i != *head; i = i->next){Prin(i->data);}printf("\n");
}

5、数据操作

void PushFront(L** head, DataType data)
{assert(head != NULL && *head != NULL);L* pos = (L*)malloc(sizeof(L));if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}pos->next = (*head)->next;pos->prev = *head;pos->next->prev = pos;pos->data = data;(*head)->next = pos;(*head)->data++;
}void PopFront(L** head)
{assert(head != NULL && *head != NULL && (*head)->next != *head);L* next = (*head)->next;(*head)->next = next->next;next->next->prev = *head;free(next);(*head)->data--;
}void PushBack(L** head, DataType data)
{assert(head != NULL && *head != NULL);L* pos = (L*)malloc(sizeof(L));if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}pos->next = *head;pos->prev = (*head)->prev;pos->prev->next = pos;pos->data = data;(*head)->prev = pos;(*head)->data++;
}void PopBack(L** head)
{assert(head != NULL && *head != NULL && (*head)->next != *head);L* prev = (*head)->prev;(*head)->prev = prev->prev;prev->prev->next = *head;free(prev);(*head)->data--;
}L* Find(L** head, DataType data)
{assert(head != NULL && *head != NULL);for (L* i = (*head)->next; i != *head; i = i->next){if (i->data == data)return i;}return NULL;
}void Modify(L** head, L* x, DataType data)
{assert(head != NULL && *head != NULL && x != NULL);for (L* i = (*head)->next; i != *head; i = i->next){if (i == x){i->data = data;return;}}assert(0);
}

---

四、分析带头双向循环链表

1、存储方式

带头双向循环链表是一种特殊的链表结构，它包含一个头节点，并且该头节点与链表的第一个实际数据节点以及最后一个数据节点之间都通过指针相互连接，形成一个环状结构。每个节点除了存储数据外，还包含两个指针，一个指向前一个节点，另一个指向后一个节点。

2、优点

• 插入和删除操作效率高：由于链表通过指针连接各个节点，因此在进行插入和删除操作时，只需修改相关节点的指针指向即可，无需移动大量数据。这使得插入和删除操作的时间复杂度为O(1)，即常数时间。
• 内存利用率高：链表结构允许根据实际需求动态分配内存空间，避免了像数组那样因预先分配过大空间而造成的内存浪费。因此，链表在内存利用方面具有较高的灵活性。

3、缺点

• 访问速度较慢：链表中的数据节点并非连续存储，而是通过指针连接。因此，要访问链表中的某个元素，通常需要从头节点开始遍历链表，直到找到目标节点。这使得访问元素的时间复杂度为O(n)，即线性时间，其中n为链表的长度。
• 存储空间较大：链表中的每个节点除了存储数据外，还需要额外存储两个指针（一个指向前一个节点，另一个指向后一个节点）。这增加了节点的存储空间需求，相对于数组等连续存储结构，链表在存储空间方面可能不够紧凑。

---

五、总结

1、练习题

• 移除链表元素
• 相交链表
• 环形链表 I
• 环形链表 II
• 随机链表的复制

2、源代码

对于带头双向循环链表的源代码我已经开源在Gitee：传送门。

---