雙向連結列表
雙向連結列表是線性資料結構。它是定義為節點的物件的集合。但是與連結列表不同，該節點有兩個指標，一個是前一個指標，另一個是下一個指標。就像連結串列節點儲存在記憶體中的隨機位置中，而不是儲存在連續位置中一樣。
雙向連結列表 vs 連結列表
- 雙向連結列表允許我們在向前和向後的方向上遍歷連結列表，但這是以
prev指標為每個節點所需的額外空間為代價的。 - 在雙向連結串列中插入元素非常容易，因為我們不必維護多個指標或遍歷連結串列來查詢先前的指標，但是與連結串列相比，我們必須修改更多的指標。
雙向連結列表遍歷演算法
前進方向
令 head 成為連結列表的第一個節點。
-
初始化
curr，指向連結列表的head節點。 -
雖然
curr尚未到達列表的末尾，即curr！=NULL，但請執行以下操作：- 列印儲存在當前節點內的資料。
curr=curr->next;- 如果是最後一個節點，則儲存為
tail，以方便向後遍歷。
同樣，我們可以通過從 tail 開始並將 curr 更改為 curr->prev 來進行向後遍歷。
反方向
令 tail 為連結串列的最後一個節點。
-
初始化
curr，指向連結列表的tail節點。 -
雖然
curr尚未到達列表的開頭，即curr!=NULL，但請執行以下操作：- 列印儲存在當前節點內的資料。
curr = curr->上一個
雙向連結列表插入
雙向連結列表在插入元素時有 4 種情況，就像連結串列一樣。
將節點插入 DLL push() 的開頭
-
使用資料
x和prev建立為NULL的新節點temp。 -
將
temp->next設定為head，將head->prev設定為temp，以在head之前插入temp。 -
將
temp設定為連結列表的開頭。
在 Append()DLL 末尾插入節點
-
建立一個新節點
temp，其資料為x，並且其prev為NULL。 -
初始化指向
head的tail。 -
如果連結列表為空，則將
temp設定為連結列表的head，然後返回。 -
否則，迭代連結列表的末尾，使
tail->next！=NULL，以便你到達最後一個元素 -
將
tail->next設定為temp，將temp->prev設定為tail。
在給定節點 insertBefore() 之前插入節點
-
如果
next==NULL，則返回； -
用資料
x建立一個新節點curr。 -
將
curr->prev設定為next->prev，以在next之前新增一個新節點，將next->prev設定為curr，以建立後向連結。 -
將
curr->next設定為next，最後檢查curr->prev是否為NULL。 -
如果不是
NULL，則將curr->prev->next設定為curr以完成插入，否則curr是連結列表的第一個節點。將head設定為curr。
在給定節點 insertAfter() 之後插入節點
-
如果
prev==NULL，則返回； -
用資料
x建立一個新節點curr。 -
將
curr->next設定為prev->next，以在prev之後新增一個新節點，並將prev->next設定為curr，以建立前向連結。 -
將
curr->prev設定為prev，最後檢查curr->next是否為 NULL。如果不是NULL，則將curr->next->prev設定為curr以完成插入。
雙向連結列表插入插圖
將節點插入 DLL push() 的開頭
在 Append()DLL 末尾插入節點
在給定節點 insertBefore() 之前插入節點
在給定節點 insertAfter() 之後插入節點
雙向連結列表遍歷和插入實現
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
};
void push(Node** head, int x) {
Node* curr = new Node();
curr->data = x;
curr->next = (*head);
curr->prev = NULL;
if ((*head) != NULL) (*head)->prev = curr;
(*head) = curr;
}
void insertAfter(Node* prev, int x) {
if (prev == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
Node* curr = new Node();
curr->data = x;
curr->next = prev->next;
prev->next = curr;
curr->prev = prev;
if (curr->next != NULL) curr->next->prev = curr;
}
void insertBefore(struct Node** head, struct Node* next, int x) {
if (next == NULL) {
return;
}
Node* curr = new Node();
curr->data = x;
curr->prev = next->prev;
next->prev = curr;
curr->next = next;
if (curr->prev != NULL)
curr->prev->next = curr;
else
(*head) = curr;
}
void append(Node** head, int x) {
Node* curr = new Node();
Node* tail = *head;
curr->data = x;
curr->next = NULL;
if (*head == NULL) {
curr->prev = NULL;
*head = curr;
return;
}
while (tail->next != NULL) tail = tail->next;
tail->next = curr;
curr->prev = tail;
return;
}
void printList(Node* node) {
Node* tail = NULL;
cout << "Forward Traversal:";
while (node != NULL) {
cout << " " << node->data << " ";
tail = node;
node = node->next;
}
cout << "\nReverse Traversal:";
while (tail != NULL) {
cout << " " << tail->data << " ";
tail = tail->prev;
}
cout << "\n";
}
int main() {
Node* head = NULL;
append(&head, 6);
push(&head, 7);
push(&head, 1);
append(&head, 4);
printList(head);
insertAfter(head->next, 8);
insertBefore(&head, head->next->next, 3);
printList(head);
return 0;
}
雙向連結列表遍歷和插入演算法的複雜性
遍歷
時間複雜度
- 平均情況
要遍歷完整的雙向連結串列，我們必須訪問每個節點。因此，如果它具有 n 個節點，則遍歷的平均情況下時間複雜度約為 O(n)。時間複雜度約為 O(n)。
- 最佳情況
最佳情況下的時間複雜度是 O(n)。它與平均情況下的時間複雜度相同。
- 最壞情況
最差的時間複雜度是 O(n)。它與最佳情況下的時間複雜度相同。
空間複雜度
遍歷演算法的空間複雜度為 O(1)，因為除 curr 指標外不需要其他空間。
插入方式
時間複雜度
- 平均情況
在所有 4 情況下插入一個元素最多需要 4 連結更改，因此插入的時間複雜度為 O(1)。
- 最佳情況
最佳情況下的時間複雜度是 O(1)。它與平均情況下的時間複雜度相同。
- 最壞情況
最壞情況下的時間複雜度是 O(1)。它與最佳情況下的時間複雜度相同。
空間複雜度
對於所有 4 種插入方式，插入演算法的空間複雜度為 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