循环双向链表
循环双向链表是循环链表和双向链表的组合。它的两个节点由上一个和下一个指针连接。最后一个节点的下一个指针指向第一个节点，第一个节点的上一个指针指向最后一个节点。它可以从两个方向遍历，也可以从尾巴到头部或从头到尾跳跃。它还用于实现高级数据结构，如斐波那契堆。
循环双向链表遍历
我们只需检查迭代中的下一个节点不是 head 的条件，然后遍历循环双向链表，然后根据向前/向后将 temp 从 temp->next 或 temp->prev 中移出迭代。
正向
令 head 成为链接列表的第一个节点。
-
初始化指向链接列表的
head节点的curr。 -
尽管
curr尚未到达列表的末尾，即curr->next！=head，请执行以下操作：- 打印存储在当前节点内的数据。
curr=curr->next;
同样，我们可以通过从 tail 开始并将 curr 更改为 curr->prev 来进行向后遍历。
反向
令 tail（即 head->prev）成为链接列表的最后一个节点。
-
初始化
curr，指向链接列表的tail节点。 -
尽管
curr尚未到达列表的开头，即curr->prev!=tail，请执行以下操作：- 打印存储在当前节点内的数据。
curr = curr->上一个
循环双向链表插入
有 3 种不同的插入情况。
在循环双向链表的开头插入元素
-
用给定的数据创建一个节点
temp。 -
将
temp->next设置为head，将temp->prev设置为tail，以便在head和tail之间插入temp。 -
将
tail->next和head->prev设置为temp以完成插入。 -
将
head设置为temp，以将 head 移至新插入的元素。
在循环双向链表的末尾插入一个元素
-
用给定的数据创建一个节点
temp。 -
如果列表为空，则使用给定数据创建节点
temp，并将temp->prev和temp->next指向其自身，并将其设置为head并返回。 -
执行开始时要插入的步骤，最后一步除外。
在循环双向链表的中间插入元素
令 X 为要在其后插入元素的节点的值。
-
用给定的数据创建一个节点
temp。 -
初始化指向
head的指针curr。 -
迭代直到找到带有
数据=X的节点。将其下一个节点存储为下一个。 -
将
curr->next设置为temp。 -
将
temp->prev设置为curr，将temp->next设置为next。 -
最后，将
下一个->上一个设置为温度。
循环双向链表插入插图
在循环双向链表的开头插入元素
在循环双向链表的末尾插入一个元素
在循环双向链表的中间插入元素
循环双向链表遍历和插入实现
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node* prev; }; void insertEnd(Node** head, int value) { if (*head == NULL) { Node* temp = new Node; temp->data = value; temp->next = temp->prev = temp; *head = temp; return; } Node* tail = (*head)->prev; Node* temp = new Node; temp->data = value; temp->next = *head; (*head)->prev = temp; temp->prev = tail; tail->next = temp; } void insertBegin(Node** head, int value) { Node* tail = (*head)->prev; Node* temp = new Node; temp->data = value; temp->next = *head; temp->prev = tail; tail->next = (*head)->prev = temp; *head = temp; } void insertAfter(Node** head, int value1, int value2) { Node* temp = new Node; temp->data = value1; Node* curr = *head; while (curr->data != value2) curr = curr->next; Node* next = curr->next; curr->next = temp; temp->prev = curr; temp->next = next; next->prev = temp; } void printList(Node* head) { Node* curr = head; printf("Forward Traversal:"); while (curr->next != head) { printf("%d ", curr->data); curr = curr->next; } printf("%d ", curr->data); printf("\nBackward Traversal:"); Node* tail = head->prev; curr = tail; while (curr->prev != tail) { printf("%d ", curr->data); curr = curr->prev; } printf("%d ", curr->data); cout << "\n"; } int main() { Node* head = NULL; insertEnd(&head, 2); insertBegin(&head, 1); insertEnd(&head, 4); printList(head); insertEnd(&head, 5); insertAfter(&head, 3, 2); printList(head); return 0; } 循环双向链表遍历和插入算法的复杂性
遍历
时间复杂度
- 平均情况
要遍历完整的双向链表，我们必须访问每个节点。如果具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。
- 最佳情况
最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。
- 最坏情况
最差的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。
空间复杂度
遍历算法的空间复杂度为 O(1)，因为除了 curr 指针外不需要其他空间。
插入
时间复杂度
- 平均情况
要在 tail 和 head 处插入要插入的元素，最多需要更改 4 个链接，因此时间复杂度为 O(1)。但是要在两者之间插入，我们可能必须移动 n-1 个节点，因此时间复杂度为 O(n)。
- 最佳情况
对于所有 3 情况，最佳情况下的时间复杂度为 O(1)。
- 最坏情况
对于前两种情况，最坏情况下的时间复杂度为 O(1)，对于第三种情况为 O(n)。它与平均情况下的时间复杂度相同。
空间复杂度
对于所有 3 种类型的插入，插入算法的空间复杂度为 O(1)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn