資料結構：鏈結串列
鏈結串列（Linked List）是資料結構中一種靈活且重要的線性資料結構。與陣列不同，鏈結串列的記憶體分配是非連續的，它透過節點（Node）之間的指標（Pointer）來串接元素。這種特性賦予鏈結串列較高的插入與刪除效率，尤其在處理大量資料或頻繁變更資料時，鏈結串列具有顯著優勢。
一、鏈結串列的定義
鏈結串列是一種由一連串節點所組成的資料結構，每個節點包含兩個部分：
- 資料（Data）：儲存具體的資料值。
- 指標（Pointer）：指向下一個節點的記憶體位址。
第一個節點稱為”頭節點”（Head），最後一個節點的指標為空（NULL），表示串列結束。
二、鏈結串列的種類
1. 單向鏈結串列（Singly Linked List）
每個節點只包含一個指向下一個節點的指標。
2. 雙向鏈結串列（Doubly Linked List）
每個節點包含兩個指標，分別指向前一個節點和下一個節點。
3. 環狀鏈結串列（Circular Linked List）
最後一個節點的指標指向頭節點，形成一個環狀結構。
三、鏈結串列的基本操作
1. 初始化鏈結串列
建立一個空的鏈結串列。
2. 插入節點
- 在頭部插入
- 在尾部插入
- 在特定位置插入
3. 刪除節點
- 刪除頭節點
- 刪除尾節點
- 刪除特定位置的節點
4. 查詢節點
根據索引或值找到對應的節點。
5. 遍歷鏈結串列
從頭節點開始依序訪問每個節點。
四、鏈結串列的程式碼範例
以下為 C++ 單向鏈結串列的基本範例：
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
void printList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
printList(head);
return 0;
}五、鏈結串列的特性
- 動態記憶體分配：節點可以根據需要動態分配記憶體，不會浪費空間。
- 插入與刪除操作高效：不需要移動其他元素，只需調整指標即可。
- 不支持隨機存取：只能順序遍歷節點。
六、鏈結串列的時間與空間複雜度
| 操作 | 時間複雜度 |
|---|---|
| 插入 | O(1)（在頭或尾插入）/ O(n)（在特定位置插入） |
| 刪除 | O(1)（刪除頭）/ O(n)（刪除特定位置） |
| 查詢 | O(n) |
| 遍歷 | O(n) |
空間複雜度：O(n)，n 為節點數量。
七、鏈結串列的應用場景
- 動態資料管理：適用於需要頻繁插入與刪除的場景。
- 記憶體有限環境：避免陣列所需的連續空間分配。
- 建構其他資料結構：如堆疊、佇列等底層可用鏈結串列實作。
八、鏈結串列的優缺點
優點：
- 動態分配記憶體，避免空間浪費。
- 插入、刪除操作靈活且效率高。
缺點：
- 不支持隨機存取。
- 額外的指標空間消耗。
九、最佳實踐
- 優先考慮 STL 提供的
list容器，避免手動處理指標。 - 插入和刪除操作時，注意邏輯完整性，避免遺漏指標更新導致記憶體洩漏或錯誤。
- 根據需求選擇單向、雙向或環狀鏈結串列。
十、結論
鏈結串列是一種彈性且實用的資料結構，特別適合處理插入與刪除操作頻繁的場景。理解鏈結串列的種類、操作方式及特性，能夠幫助程式設計師選擇最適合的資料結構，提高程式效能與可讀性。