Python 資料結構：雙向鏈結串列（Doubly Linked List）(03)

在學習了鏈結串列（Linked List）之後，接下來要進一步認識 雙向鏈結串列（Doubly Linked List）。
它是一種能夠同時往前與往後遍歷的資料結構，為許多需要雙向導航的應用場景提供了便利。

---

什麼是雙向鏈結串列？

雙向鏈結串列與單向鏈結串列相似，都是由一系列節點（Node）組成。但 Doubly Linked List 的節點比單向串列更聰明，因為它除了記錄 下一個節點的連結（next），還會額外儲存 前一個節點的連結（prev）。

特性

• 雙向遍歷：不僅能從頭走到尾，還能從尾回到頭。
• 頭尾指標：同時維護 head 與 tail，大幅提升操作效率。
• 靈活操作：能在串列的開頭、結尾，甚至任意位置快速插入或刪除。

---

Node 與 Doubly Linked List 類別

一個 Doubly Linked List 的基本組成包含兩個部分：

1. Node 類別：保存數值、前一個節點指標（prev）、下一個節點指標（next）。
2. Doubly Linked List 類別：保存整個串列的頭部（head）與尾部（tail），並提供操作方法。

初始化時，head 與 tail 都會設為 None，代表串列是空的。

---

核心功能設計

雙向鏈結串列的價值在於它能支援更多、更靈活的操作。以下是實作時常見的核心功能與用途：

1. 新增到頭部（Add to Head）

• 將新節點插入到串列最前端。
• 需要同時更新新節點的 next 指向舊 head，並更新舊 head 的 prev。
• 如果原本串列是空的，還要將尾部（tail）一併更新。
• 用途：適合需要頻繁在開頭新增元素的情境，例如佇列的「快速入隊」。

def add_to_head(self, new_value):
    new_head = Node(new_value)
    current_head = self.head_node
    
    if current_head != None:
        current_head.set_prev_node(new_head)
        new_head.set_next_node(current_head)
    
    self.head_node = new_head
    
    if self.tail_node == None:
        self.tail_node = new_head

---

2. 新增到尾部（Add to Tail）

• 將新節點插入到串列最後端。
• 由於 DLL 保持 tail 指標，不必遍歷即可完成操作。
• 需要讓新節點的 prev 指向舊 tail，舊 tail 的 next 指向新節點，最後更新 tail。
• 用途：適合需要快速在末尾插入元素的應用，例如音樂播放清單或工作任務隊列。

def add_to_tail(self, new_value):
    new_tail = Node(new_value)
    current_tail = self.tail_node
    
    if current_tail != None:
        current_tail.set_next_node(new_tail)
        new_tail.set_prev_node(current_tail)
    
    self.tail_node = new_tail
    
    if self.head_node == None:
        self.head_node = new_tail

---

3. 移除頭部節點（Remove Head）

• 移除串列最前端的節點，並更新 head 為下一個節點。
• 若新 head 存在，需將它的 prev 設為 None。
• 如果移除的節點同時也是尾節點（僅一個元素的情況），則需要額外處理 tail。
• 用途：模擬 FIFO（先進先出）的結構，常見於排程或緩衝區。

def remove_head(self):
    removed_head = self.head_node
    if removed_head == None:
        return None

    self.head_node = removed_head.get_next_node()

    if self.head_node != None:
        self.head_node.set_prev_node(None)
    if removed_head == self.tail_node:
        self.remove_tail()
    return removed_head.get_value()

---

4. 移除尾部節點（Remove Tail）

• 移除串列最後端的節點，並更新 tail 為前一個節點。
• 若新 tail 存在，需將它的 next 設為 None。
• 如果移除的節點同時是 head，則需要額外處理 head。
• 用途：在 LRU Cache 或瀏覽器歷史記錄中，用來快速丟棄最新或最舊的資料。

def remove_tail(self):
    removed_tail = self.tail_node
    if removed_tail == None:
        return None
   
    self.tail_node = removed_tail.get_prev_node()
   
    if self.tail_node != None:
        self.tail_node.set_next_node(None)
    if removed_tail == self.head_node:
        self.remove_head()
    return removed_tail.get_value()

---

5. 依值移除節點（Remove by Value）

• 從頭開始搜尋，找到第一個匹配的節點並刪除。
• 需要處理三種情況：
  1. 刪除 head：直接呼叫 remove_head()。
  2. 刪除 tail：直接呼叫 remove_tail()。
  3. 刪除中間節點：更新前後節點的指標，讓它們彼此連接，跳過被刪除的節點。
• 用途：動態資料管理，例如刪除播放清單中的指定歌曲，或從操作歷史中移除某一步驟。

def remove_by_value(self, value_to_remove):
    current_node = self.head_node
    
    while current_node != None:
        if current_node.get_value() == value_to_remove:
            # 移除頭部
            if current_node == self.head_node:
                return self.remove_head()
            # 移除尾部
            elif current_node == self.tail_node:
                return self.remove_tail()
            else:
                next_node = current_node.get_next_node()
                prev_node = current_node.get_prev_node()
                next_node.set_prev_node(prev_node)
                prev_node.set_next_node(next_node)
                return current_node.get_value()
        current_node = current_node.get_next_node()
    return None

---

實際應用場景

• 音樂播放器：支援「上一首 / 下一首」功能。
• 地鐵或公車路線：方便在站點之間前後查詢。
• 瀏覽器操作歷史：透過雙向鏈結串列管理「復原（Undo）」與「重做（Redo）」。

結語

雙向鏈結串列透過 前後指標的設計，大幅提升了資料結構的靈活性，特別適合需要 雙向導航、快速插入刪除 的場景。