循环双向链表
循环双向链表是循环链表和双向链表的组合。它的两个节点由上一个和下一个指针连接。最后一个节点的下一个指针指向第一个节点，第一个节点的上一个指针指向最后一个节点。它可以从两个方向遍历，也可以从尾巴到头部或从头到尾跳跃。它还用于实现高级数据结构，如斐波那契堆。
循环双向链表遍历
我们只需检查迭代中的下一个节点不是 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