2024-12-21 約 1600 字預計閱讀 8 分鐘

Linked List（鏈結串列）完整教學

什麼是 Linked List？

Linked List（鏈結串列）是一種線性的資料結構，其中的元素不是儲存在連續的記憶體位置，而是透過指標（pointer）相互連接。每個元素稱為節點（Node），包含兩個部分：

資料（Data）：儲存實際的值
指標（Next）：指向下一個節點的參考

視覺化表示

[Data|Next] -> [Data|Next] -> [Data|Next] -> None
     ↑              ↑              ↑
   Node 1        Node 2        Node 3

為什麼需要 Linked List？

與 Python List（Array）的比較

# Python List（動態陣列）
python_list = [1, 2, 3, 4, 5]
# 記憶體中連續存放：[1][2][3][4][5]

# Linked List
# 記憶體中分散存放：
# [1|→] -----> [2|→] -----> [3|→] -----> [4|→] -----> [5|None]

優缺點比較

操作	Python List	Linked List
訪問第 i 個元素	O(1)	O(n)
在開頭插入	O(n)	O(1)
在結尾插入	O(1)*	O(n)
在中間插入	O(n)	O(1)**
刪除元素	O(n)	O(1)**
記憶體使用	連續	分散

* 平均情況，可能需要擴容 ** 如果已經有該位置的參考

基本實作

1. 節點類別（Node Class）

class Node:
    """鏈結串列的節點"""
    def __init__(self, data):
        self.data = data  # 儲存資料
        self.next = None  # 指向下一個節點
    
    def __repr__(self):
        return f"Node({self.data})"

# 建立節點
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

# 手動連接節點
node1.next = node2
node2.next = node3

# 視覺化：node1 -> node2 -> node3 -> None
print(node1)        # Node(10)
print(node1.next)   # Node(20)
print(node1.next.next)  # Node(30)
print(node1.next.next.next)  # None

2. 鏈結串列類別（LinkedList Class）

class LinkedList:
    """單向鏈結串列"""
    def __init__(self):
        self.head = None  # 指向第一個節點
        self.size = 0     # 記錄串列大小
    
    def __len__(self):
        return self.size
    
    def is_empty(self):
        """檢查串列是否為空"""
        return self.head is None
    
    def __repr__(self):
        """視覺化顯示串列"""
        if self.is_empty():
            return "LinkedList()"
        
        result = []
        current = self.head
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result) + " -> None"

# 使用範例
ll = LinkedList()
print(ll)  # LinkedList()
print(ll.is_empty())  # True

基本操作實作

1. 在開頭插入（Prepend）

def prepend(self, data):
    """在串列開頭插入新節點 - O(1)"""
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
    self.size += 1

# 加入方法到 LinkedList 類別
LinkedList.prepend = prepend

# 使用範例
ll = LinkedList()
ll.prepend(10)
ll.prepend(20)
ll.prepend(30)
print(ll)  # 30 -> 20 -> 10 -> None

2. 在結尾插入（Append）

def append(self, data):
    """在串列結尾插入新節點 - O(n)"""
    new_node = Node(data)
    self.size += 1
    
    if self.is_empty():
        self.head = new_node
        return
    
    # 找到最後一個節點
    current = self.head
    while current.next:
        current = current.next
    current.next = new_node

LinkedList.append = append

# 使用範例
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
print(ll)  # 10 -> 20 -> 30 -> None

3. 在指定位置插入

def insert(self, index, data):
    """在指定位置插入新節點 - O(n)"""
    if index < 0 or index > self.size:
        raise IndexError("Index out of range")
    
    if index == 0:
        self.prepend(data)
        return
    
    new_node = Node(data)
    current = self.head
    
    # 移動到插入位置的前一個節點
    for _ in range(index - 1):
        current = current.next
    
    new_node.next = current.next
    current.next = new_node
    self.size += 1

LinkedList.insert = insert

# 使用範例
ll = LinkedList()
ll.append(10)
ll.append(30)
ll.insert(1, 20)  # 在索引 1 插入 20
print(ll)  # 10 -> 20 -> 30 -> None

4. 刪除節點

def remove(self, data):
    """刪除第一個符合的節點 - O(n)"""
    if self.is_empty():
        raise ValueError("List is empty")
    
    # 如果要刪除的是第一個節點
    if self.head.data == data:
        self.head = self.head.next
        self.size -= 1
        return True
    
    # 尋找要刪除的節點
    current = self.head
    while current.next:
        if current.next.data == data:
            current.next = current.next.next
            self.size -= 1
            return True
        current = current.next
    
    return False

def remove_at(self, index):
    """刪除指定位置的節點 - O(n)"""
    if index < 0 or index >= self.size:
        raise IndexError("Index out of range")
    
    if index == 0:
        self.head = self.head.next
        self.size -= 1
        return
    
    # 移動到要刪除位置的前一個節點
    current = self.head
    for _ in range(index - 1):
        current = current.next
    
    current.next = current.next.next
    self.size -= 1

LinkedList.remove = remove
LinkedList.remove_at = remove_at

# 使用範例
ll = LinkedList()
for i in [10, 20, 30, 40]:
    ll.append(i)

print(ll)  # 10 -> 20 -> 30 -> 40 -> None
ll.remove(20)
print(ll)  # 10 -> 30 -> 40 -> None
ll.remove_at(1)
print(ll)  # 10 -> 40 -> None

5. 查找與訪問

def find(self, data):
    """查找資料是否存在 - O(n)"""
    current = self.head
    index = 0
    
    while current:
        if current.data == data:
            return index
        current = current.next
        index += 1
    
    return -1

def get(self, index):
    """取得指定位置的資料 - O(n)"""
    if index < 0 or index >= self.size:
        raise IndexError("Index out of range")
    
    current = self.head
    for _ in range(index):
        current = current.next
    
    return current.data

LinkedList.find = find
LinkedList.get = get

# 使用範例
ll = LinkedList()
for i in [10, 20, 30]:
    ll.append(i)

print(ll.find(20))  # 1
print(ll.find(40))  # -1
print(ll.get(1))    # 20

進階操作

1. 反轉鏈結串列

def reverse(self):
    """反轉整個串列 - O(n)"""
    prev = None
    current = self.head
    
    while current:
        next_node = current.next  # 保存下一個節點
        current.next = prev       # 反轉指標
        prev = current           # 移動 prev
        current = next_node      # 移動 current
    
    self.head = prev

LinkedList.reverse = reverse

# 使用範例
ll = LinkedList()
for i in [1, 2, 3, 4, 5]:
    ll.append(i)

print("原始：", ll)  # 1 -> 2 -> 3 -> 4 -> 5 -> None
ll.reverse()
print("反轉：", ll)  # 5 -> 4 -> 3 -> 2 -> 1 -> None

2. 合併兩個已排序的串列

@staticmethod
def merge_sorted(list1, list2):
    """合併兩個已排序的串列 - O(n + m)"""
    # 建立虛擬頭節點
    dummy = Node(0)
    current = dummy
    
    p1, p2 = list1.head, list2.head
    
    while p1 and p2:
        if p1.data <= p2.data:
            current.next = p1
            p1 = p1.next
        else:
            current.next = p2
            p2 = p2.next
        current = current.next
    
    # 連接剩餘的節點
    current.next = p1 if p1 else p2
    
    # 建立新的串列
    result = LinkedList()
    result.head = dummy.next
    result.size = list1.size + list2.size
    
    return result

LinkedList.merge_sorted = merge_sorted

# 使用範例
ll1 = LinkedList()
for i in [1, 3, 5]:
    ll1.append(i)

ll2 = LinkedList()
for i in [2, 4, 6]:
    ll2.append(i)

merged = LinkedList.merge_sorted(ll1, ll2)
print(merged)  # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

3. 檢測循環

def has_cycle(self):
    """使用 Floyd's Cycle Detection (快慢指標) - O(n)"""
    if self.is_empty():
        return False
    
    slow = fast = self.head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

LinkedList.has_cycle = has_cycle

# 使用範例
ll = LinkedList()
for i in [1, 2, 3, 4]:
    ll.append(i)

print(ll.has_cycle())  # False

# 手動建立循環
current = ll.head
while current.next:
    current = current.next
current.next = ll.head.next  # 最後一個節點指向第二個節點

print(ll.has_cycle())  # True

完整的 LinkedList 實作

class Node:
    """鏈結串列節點"""
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __repr__(self):
        return f"Node({self.data})"

class LinkedList:
    """單向鏈結串列完整實作"""
    
    def __init__(self):
        self.head = None
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def __repr__(self):
        if self.is_empty():
            return "LinkedList()"
        
        result = []
        current = self.head
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result) + " -> None"
    
    def __iter__(self):
        """使串列可迭代"""
        current = self.head
        while current:
            yield current.data
            current = current.next
    
    def is_empty(self):
        return self.head is None
    
    def prepend(self, data):
        """在開頭插入 - O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def append(self, data):
        """在結尾插入 - O(n)"""
        new_node = Node(data)
        self.size += 1
        
        if self.is_empty():
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def insert(self, index, data):
        """在指定位置插入 - O(n)"""
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")
        
        if index == 0:
            self.prepend(data)
            return
        
        new_node = Node(data)
        current = self.head
        
        for _ in range(index - 1):
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        self.size += 1
    
    def remove(self, data):
        """刪除第一個符合的節點 - O(n)"""
        if self.is_empty():
            raise ValueError("List is empty")
        
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return True
        
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        
        return False
    
    def remove_at(self, index):
        """刪除指定位置的節點 - O(n)"""
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        
        if index == 0:
            self.head = self.head.next
            self.size -= 1
            return
        
        current = self.head
        for _ in range(index - 1):
            current = current.next
        
        current.next = current.next.next
        self.size -= 1
    
    def find(self, data):
        """查找資料位置 - O(n)"""
        current = self.head
        index = 0
        
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        
        return -1
    
    def get(self, index):
        """取得指定位置的資料 - O(n)"""
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        
        current = self.head
        for _ in range(index):
            current = current.next
        
        return current.data
    
    def reverse(self):
        """反轉串列 - O(n)"""
        prev = None
        current = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
    
    def clear(self):
        """清空串列 - O(1)"""
        self.head = None
        self.size = 0
    
    def to_list(self):
        """轉換為 Python list - O(n)"""
        return list(self)

# 使用範例
def demo_linked_list():
    print("=== Linked List 示範 ===\n")
    
    # 建立串列
    ll = LinkedList()
    print(f"空串列: {ll}")
    
    # 新增元素
    for i in [10, 20, 30]:
        ll.append(i)
    print(f"Append 10,20,30: {ll}")
    
    # 在開頭插入
    ll.prepend(5)
    print(f"Prepend 5: {ll}")
    
    # 在中間插入
    ll.insert(2, 15)
    print(f"Insert 15 at index 2: {ll}")
    
    # 查找
    print(f"Find 20: index = {ll.find(20)}")
    print(f"Get index 2: {ll.get(2)}")
    
    # 刪除
    ll.remove(15)
    print(f"Remove 15: {ll}")
    
    # 反轉
    ll.reverse()
    print(f"Reverse: {ll}")
    
    # 迭代
    print("Iterate:", end=" ")
    for value in ll:
        print(value, end=" ")
    print()
    
    # 轉換為 list
    print(f"To list: {ll.to_list()}")

demo_linked_list()

時間複雜度總結

操作	時間複雜度	說明
prepend()	O(1)	在開頭插入
append()	O(n)	需要遍歷到結尾
insert()	O(n)	需要遍歷到指定位置
remove()	O(n)	需要查找元素
find()	O(n)	需要遍歷查找
get()	O(n)	需要遍歷到指定位置
reverse()	O(n)	需要遍歷整個串列

使用場景

適合使用 Linked List 的情況：

頻繁在開頭插入/刪除：如實作 Stack
不需要隨機訪問：只需要順序遍歷
資料大小不確定：動態增長
實作其他資料結構：如 Queue、Graph

不適合使用 Linked List 的情況：

需要頻繁隨機訪問：使用 Array
需要二分搜尋：需要 O(1) 的訪問時間
Cache 效能重要：Array 有更好的局部性

變種：雙向鏈結串列

class DoublyNode:
    """雙向鏈結串列節點"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None  # 新增：指向前一個節點

class DoublyLinkedList:
    """雙向鏈結串列"""
    def __init__(self):
        self.head = None
        self.tail = None  # 新增：指向最後一個節點
        self.size = 0
    
    def append(self, data):
        """在結尾插入 - O(1)"""
        new_node = DoublyNode(data)
        self.size += 1
        
        if not self.head:
            self.head = self.tail = new_node
            return
        
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
    
    def prepend(self, data):
        """在開頭插入 - O(1)"""
        new_node = DoublyNode(data)
        self.size += 1
        
        if not self.head:
            self.head = self.tail = new_node
            return
        
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    
    def remove_node(self, node):
        """直接刪除節點 - O(1)"""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        
        self.size -= 1

# 使用範例
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.prepend(5)
print(f"Size: {dll.size}")  # Size: 3

總結

Linked List 是一種基礎但重要的資料結構：

優點：
- 動態大小
- 在開頭插入/刪除效率高
- 記憶體使用靈活
缺點：
- 無法隨機訪問
- 需要額外的記憶體儲存指標
- Cache 效能較差
應用：
- 實作 Stack 和 Queue
- 處理大量插入/刪除操作
- 實作更複雜的資料結構

理解 Linked List 的原理和實作，是學習更進階資料結構的重要基礎！

Linked List（鏈結串列）完整指南