迴圈雙向連結串列
迴圈雙向連結串列是迴圈連結串列和雙向連結串列的組合。它的兩個節點由上一個和下一個指標連線。最後一個節點的下一個指標指向第一個節點,第一個節點的上一個指標指向最後一個節點。它可以從兩個方向遍歷,也可以從尾巴到頭部或從頭到尾跳躍。它還用於實現高階資料結構,如斐波那契堆。
迴圈雙向連結串列遍歷
我們只需檢查迭代中的下一個節點不是 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