動態鏈表（List）的基本概念

動態鏈表是一種線性數據結構，通過節點間的指針連接實現動態內存分配。與數組不同，鏈表的大小可隨需增減，插入和刪除操作的時間復雜度為 O(1)（已知位置時），但隨機訪問需要 O(n) 時間。

常見動態鏈表類型

1. 單向鏈表
   每個節點包含數據和指向下一個節點的指針。

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

2. 雙向鏈表
   節點包含指向前驅和后繼的指針，支持雙向遍歷。

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

3. 循環鏈表
   尾節點指向頭節點，形成閉環。

動態鏈表的操作

插入節點
在頭部插入：

new_node = Node(data)
new_node.next = head
head = new_node

在中間插入（已知前驅節點 prev_node）：

new_node.next = prev_node.next
prev_node.next = new_node

刪除節點
刪除頭節點：

head = head.next

刪除中間節點（已知前驅節點 prev_node）：

prev_node.next = prev_node.next.next

動態鏈表的優缺點

優點

• 內存按需分配，避免靜態數組的浪費。
• 插入/刪除高效，無需移動其他元素。

缺點

• 隨機訪問效率低。
• 需要額外空間存儲指針。

動態鏈表的應用場景

• 實現棧、隊列等抽象數據類型。
• 內存管理中的動態分配（如操作系統的空閑內存塊管理）。
• 需要頻繁插入/刪除的場景（如實時系統）。

示例：單向鏈表的完整實現

class LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturnlast = self.headwhile last.next:last = last.nextlast.next = new_nodedef print_list(self):current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")

注意事項

• 動態鏈表需手動管理內存（如 C/C++ 中需釋放節點）。
• 在 Python/Java 等語言中，垃圾回收機制自動處理內存釋放。