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