前幾天我們看過了單向鏈結串列與他的實作，今天我們來看雙向鏈結串列吧 !

昨天在做 Reverse Linked List 時，我們發現一件事：

1 → 2 → 3 → 4

如果目前站在節點 3：

1 → 2 → 3 → 4
        ↑

我們可以知道：

node->next

也就是：4

但卻不知道：2

什麼是雙向鏈結串列？

為了解決這個問題，
我們可以讓每個節點除了記錄下一個節點之外，再額外記錄前一個節點

節點結構

單向鏈結串列

struct Node{
    int data;
    Node* next;
};

雙向鏈結串列

struct Node{
    int data;
    Node* prev;
    Node* next;
};

data：存放資料
prev：指向前一個節點
next：指向下一個節點

每個節點都同時知道「前面是誰」跟「後面是誰」，
頭節點(head)的 prev 和尾節點(tail)的 next 則指向 nullptr。

建立一個節點

Node* node=new node{10,nullptr,nullptr};

data = 10
prev = nullptr
next = nullptr

昨天寫 Reverse Linked List 時，用了 prev 和 cur 兩個指標邊走邊反轉：

ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
    ListNode* next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
}

回頭看這段程式碼會發現一件事：
prev 和 cur 這兩個指標，其實就是在模擬雙向鏈結串列節點裡的 prev 和 next
只是單向鏈結串列本身沒有 prev 這個欄位，所以只能用額外的變數，在走訪過程中暫借這個角色，一步一步把方向接起來

換句話說：

• 雙向鏈結串列：每個節點永久存著 prev 和 next，隨時可以雙向查詢。
• 單向鏈結串列反轉：用 prev、cur 這兩個暫時性的外部指標，在走訪的當下模擬出「知道前一個節點是誰」的效果，走過去之後這個資訊就跟著指標移動，不會留在節點本身

常見的用法

正向/反向走訪

void printForward() {
    Node* cur = head;
    while (cur != nullptr) {
        cout << cur->data << " ";
        cur = cur->next;
    }
}

void printBackward() {
    Node* cur = tail;
    while (cur != nullptr) {
        cout << cur->data << " ";
        cur = cur->prev;
    }
}

單向鏈結串列做不到這件事(除非額外用堆疊或遞迴模擬)

建立一個雙向鏈結串列

(尾端插入)

struct Node{
    int data;
    Node *prev;
    Node *next;
    Node(int x){
        data=x;
        prev=nullptr;
        next=nullptr;
    }
};

Node* head=nullptr;
Node* tail=nullptr;
void insertAtTail(int data){
    Node* newNode = new Node(data);
    if (head == nullptr) {
        head = tail = newNode;
        return;
    }
    tail -> next = newNode;
    newNode ->prev = tail;
    tail = newNode;
}
int main(){
    insertAtTail(10);//從0開始依序插入 10 -> 20 -> 30 -> 40
    insertAtTail(20);
    insertAtTail(30);
    insertAtTail(40);
    return 0;
}

頭端插入

void insertAtHead(int data){
    Node* newNode= new Node(data);
    if(head = nullptr){
        head = tail = newNode;
        return;
    }
    newNode -> next = head;
    head -> prev = newNode;
    head = newNode;
}

刪除節點

void deleteNode(Node* target) {
    if (target == nullptr) return;

    if (target->prev != nullptr) {
        target->prev->next = target->next;   // 前一個節點跳過 target
    } else {
        head = target->next;                  // target 是 head,更新 head
    }

    if (target->next != nullptr) {
        target->next->prev = target->prev;   // 後一個節點跳過 target
    } else {
        tail = target->prev;                  // target 是 tail,更新 tail
    }

    delete target;
}

跟單向鏈結串列比較

終於撐到第 10 天了，這幾天真的遇到好多事情@@，那接下來幾天繼續加油吧

參考資料和書籍

1. https://medium.com/@racktar7743/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E9%9B%99%E5%90%91%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%95%99%E5%AD%B8-3-%E5%88%AA%E9%99%A4%E7%B5%90%E9%BB%9E-40724ac8de5d
2. https://www.hello-algo.com/zh-hant/chapter_array_and_linkedlist/linked_list/#423