C 語言中的鏈結串列（Linked Lists）詳解

### C 語言中的鏈結串列（Linked Lists）詳解

（全文約 1000 字）

#### **1. 基本概念**

鏈結串列是一種**動態資料結構**，由多個節點（Node）組成。每個節點包含：

- **資料欄位**：儲存實際資料（如整數、字元等）。

- **指標欄位**：指向下一個節點的記憶體地址。

```c

typedef struct node {

int data; // 資料

struct node *next; // 指向下一個節點的指標

} Node;

```

- **頭指標（Head）**：指向第一個節點，是存取整個串列的入口。

- **結尾標誌**：最後一個節點的指標指向 `NULL`，表示串列結束。

#### **2. 與陣列的關鍵差異**

| 特性 | 陣列 | 鏈結串列 |

|---------------|--------------------------|------------------------------|

| **記憶體分配** | 靜態連續記憶體 | 動態非連續記憶體 |

| **大小調整** | 固定大小，不可擴充 | 執行期動態擴充 |

| **插入/刪除** | 需移動元素（O(n)） | 修改指標即可（O(1)） |

| **存取方式** | 隨機存取（O(1)） | 順序存取（O(n)） |

#### **3. 核心操作詳解**

**(1) 建立串列與節點**

```c

Node* create_node(int value) {

Node* new_node = (Node*)malloc(sizeof(Node));

new_node->data = value;

new_node->next = NULL;

return new_node;

}

```

**(2) 插入節點**

- **頭部插入**：

```c

void insert_head(Node **head, int value) {

Node* new_node = create_node(value);

new_node->next = *head; // 新節點指向原頭部

*head = new_node; // 更新頭指標

}

```

- **尾部插入**：

```c

void insert_tail(Node **head, int value) {

Node* new_node = create_node(value);

if (*head == NULL) {

*head = new_node;

return;

}

Node* temp = *head;

while (temp->next != NULL) { // 遍歷至尾端

temp = temp->next;

}

temp->next = new_node; // 尾節點指向新節點

}

```

**(3) 刪除節點**

```c

void delete_node(Node **head, int value) {

Node *temp = *head, *prev = NULL;

// 刪除頭節點

if (temp != NULL && temp->data == value) {

*head = temp->next;

free(temp);

return;

}

// 尋找目標節點

while (temp != NULL && temp->data != value) {

prev = temp;

temp = temp->next;

}

// 若找不到則返回

if (temp == NULL) return;

// 跳過目標節點並釋放記憶體

prev->next = temp->next;

free(temp);

}

```

**(4) 遍歷串列**

```c

void print_list(Node *head) {

Node* temp = head;

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next;

}

printf("NULL\n");

}

```

**(5) 釋放記憶體**

```c

void free_list(Node **head) {

Node *current = *head, *next;

while (current != NULL) {

next = current->next;

free(current);

current = next;

}

*head = NULL; // 避免懸吊指標

}

```

#### **4. 優點與缺點分析**

- **優點**：

- **動態擴充**：記憶體按需分配，無需預先宣告大小。

- **高效插入/刪除**：僅需修改指標（O(1)），無需移動大量元素。

- **記憶體利用率**：可靈活利用零散記憶體區塊。

- **缺點**：

- **存取效率低**：存取第 k 個元素需遍歷 k 步（O(n)）。

- **額外記憶體開銷**：每個節點需儲存指標（通常 4/8 bytes）。

- **不支援隨機存取**：無法直接透過索引定位（如 `array[i]`）。

#### **5. 應用場景**

1. **動態資料管理**：

需頻繁插入/刪除的場景（如即時交易系統）。

2. **實現其他資料結構**：

堆疊（Stack）、佇列（Queue）、圖的鄰接表（Adjacency List）。

3. **記憶體受限系統**：

避免陣列預分配造成的記憶體浪費。

4. **檔案系統**：

用鏈結串列管理磁碟區塊（如 FAT 檔案系統）。

#### **6. 常見變形**

- **雙向鏈結串列（Doubly Linked List）**：

節點含兩個指標（`prev` 和 `next`），可雙向遍歷。

```c

typedef struct node {

int data;

struct node *prev, *next;

} DNode;

```

- **環狀鏈結串列（Circular Linked List）**：

尾節點指向頭節點，形成迴圈。

#### **7. 重要注意事項**

- **記憶體洩漏**：

動態分配的節點必須手動釋放（`free()`）。

- **指標安全性**：

操作後需檢查邊界條件（如頭指標為 `NULL`）。

- **效率取捨**：

若需頻繁存取元素，應選擇陣列或雜湊表。

> **總結**：鏈結串列是 C 語言中管理動態資料的核心結構。其非連續儲存特性犧牲了存取效率，但換來插入/刪除的高效性。理解指標操作與記憶體管理是掌握鏈結串列的關鍵，也是進階資料結構（如樹、圖）的基礎。