列表：單向串列和雙向串列

5.1 定義列表及其種類

列表 是一種動態的數據結構，由元素（節點）組成，其中每個節點包含數據和指向其他節點的鏈接。與數組不同，列表可以在程式運行時改變其大小。

重要！ 這裡指的不是Python中的list類，而是算法理論中的數據結構。

列表的種類：

• 單向串列 (Singly Linked List)： 每個節點包含數據和指向下一個節點的鏈接。
• 雙向串列 (Doubly Linked List)： 每個節點包含數據、指向下一個節點的鏈接和指向前一個節點的鏈接。

5.2 單向串列的運行原理

單向串列的結構：

• 節點 (Node)： 由兩部分組成：數據和指向下一個節點的鏈接。
• 頭 (Head)： 指向列表的第一個節點。

運作原理：

• 添加節點： 通過創建新節點並更新最後一個節點的鏈接到新節點來實現。
• 刪除節點： 需要更新前一個節點的鏈接到被刪除節點的下一個節點。

實作範例：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用範例：
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 輸出: 1 -> 2 -> 3 -> None

5.3 雙向串列的運行原理

雙向串列的結構：

• 節點 (Node)： 由三部分構成：數據、指向下一個節點的鏈接和指向前一個節點的鏈接。
• 頭 (Head)： 指向列表的第一個節點。
• 尾 (Tail)： 指向列表的最後一個節點（非必要，但經常使用）。

運作原理：

• 添加節點： 通過創建新節點並更新最後一個節點和新節點的鏈接來實現。
• 刪除節點： 需要更新被刪除節點的前一個和下一個節點的鏈接。

實作範例：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# 使用範例：
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # 輸出: 1 <-> 2 <-> 3 <-> None

5.4 基本操作

基本操作：插入、刪除、搜尋

插入：

• 單向串列： 在列表末尾插入新節點 需要遍歷所有節點到達最後一個並更新最後一個節點的鏈接。
• 雙向串列： 在列表末尾插入新節點類似於單向串列，但也需要更新新節點的prev鏈接到前一個節點。

刪除：

• 單向串列： 刪除節點 需要遍歷列表到達需要刪除的節點，並更新前一個節點的鏈接到被刪除節點的下一個節點。
• 雙向串列： 刪除節點需要更新被刪除節點鄰近節點的next和prev鏈接。

搜尋： 從頭到尾遍歷列表並比較每個節點的數據與搜索值。時間複雜度為O(n)。

5.5 列表使用範例

讓我們實作一個基於單向串列的堆疊作為範例。

堆疊可以通過單向串列輕鬆實作，使用push和pop方法來添加和刪除元素。它應該有兩個方法：

• push — 在列表末尾添加新元素
• pop — 從列表末尾提取最後一個元素

實作範例：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用範例：
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # 輸出: 3 -> 2 -> 1 -> None
print(stack.pop())  # 輸出: 3
stack.display()  # 輸出: 2 -> 1 -> None