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