目次
1. 前言
C 語言是一種廣泛應用於系統程式設計與嵌入式系統開發的程式語言。其中，「鏈結串列結構」（List Structure）是一種在資料管理與操作上非常便利的工具。本文將深入介紹 C 語言中的鏈結串列結構，從基本概念到具體的實作範例，為讀者提供完整的解說。
鏈結串列結構的重要性
鏈結串列結構是一種能夠保留資料順序並加以管理的資料結構，特別適用於以下情況：
- 管理有順序的資料
- 需要動態新增或刪除資料時
- 有效利用記憶體資源
例如，在任務管理應用程式中，由於經常需要新增與刪除任務，相較於陣列，更靈活的鏈結串列結構會更適合。
本文目的
本篇文章將示範如何在 C 語言中實作鏈結串列結構，並透過具體的程式碼範例介紹操作方法。最終，讀者將能理解鏈結串列的基本概念與實際應用方式，並能在自己的程式中加以運用。
學習目標
- 理解鏈結串列結構的基本概念。
- 學會在 C 語言中實作鏈結串列。
- 參考實用的程式碼範例，培養應用能力。
2. 什麼是鏈結串列結構
鏈結串列結構是一種用於有序管理資料的資料結構。本節將介紹鏈結串列的基本概念與類型。
鏈結串列的基本概念
鏈結串列由多個節點（Node）串接而成，每個節點包含以下兩部分：
- 資料區塊：用於儲存實際的值。
- 鏈結區塊：用於儲存指向下一個節點的參考（指標）。
透過這種結構，可以動態新增或刪除資料，適合處理長度可變的資料。
陣列與鏈結串列的差異
鏈結串列與陣列在資料管理方式上有以下不同：
| 項目 | 陣列 | 鏈結串列 |
|---|---|---|
| 大小 | 固定（宣告時決定） | 可變（可動態調整） |
| 資料存取 | 可透過索引直接存取 | 需從開頭依序搜尋 |
| 記憶體管理 | 使用連續記憶體空間 | 使用分散記憶體空間 |
| 新增/刪除資料 | 成本高（需移動其他元素） | 成本低（僅需調整指標） |
總結來說，鏈結串列適合需要高度靈活性的情境，而陣列則適合需要快速存取的場合。
鏈結串列概述與特點
鏈結串列的代表性例子是「單向鏈結串列」，其特點包括：
- 可動態調整大小
可依需求新增或刪除節點，有效利用記憶體。 - 節點插入與刪除容易
僅需調整指標即可操作，即使在中間或末端也可輕鬆處理。 - 搜尋速度較慢
存取資料時需從頭依序搜尋，定位特定元素耗時。
鏈結串列的種類
鏈結串列主要分為三種：
- 單向鏈結串列
每個節點僅指向下一個節點。
- 記憶體消耗少，結構簡單。
- 只能向後移動，不能向前。
- 雙向鏈結串列
每個節點同時指向前後節點。
- 可前後移動，操作靈活。
- 記憶體使用量較多。
- 循環鏈結串列
最後一個節點指回第一個節點。
- 可無限循環，適合迴圈處理。
- 適用於特殊用途。
下一節將介紹「C 語言中鏈結串列的實作方法」，並附上完整程式碼範例。
3. 使用 C 語言實作鏈結串列
本節將示範如何使用 C 語言實作鏈結串列，並提供完整的程式碼範例與說明。
鏈結串列的基本結構
鏈結串列由以下要素構成：
- 節點定義
- 每個節點包含資料與指向下一個節點的指標。
- 頭指標（Head Pointer）
- 指向鏈結串列開頭的指標，用來管理整個串列。
程式碼範例：鏈結串列的基本實作
以下為一個簡單的鏈結串列操作範例：
#include <stdio.h>
#include <stdlib.h>
// 節點定義
typedef struct Node {
int data; // 資料區塊
struct Node* next; // 指向下一個節點的指標
} Node;
// 建立新節點
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 動態分配記憶體
if (newNode == NULL) {
printf("記憶體分配失敗。\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL; // 預設下一個節點為 NULL
return newNode;
}
// 在串列頭部插入節點
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// 列印串列內容
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 釋放串列記憶體
void freeList(Node* head) {
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
Node* head = NULL; // 初始化空串列
// 新增資料
insertAtHead(&head, 3);
insertAtHead(&head, 2);
insertAtHead(&head, 1);
// 列印串列
printList(head);
// 釋放記憶體
freeList(head);
return 0;
}程式碼解說
- 建立節點
- 透過
malloc()進行動態記憶體分配建立新節點。
- 插入節點
- 可在頭部或尾部插入資料，擴展串列內容。
- 刪除節點
- 移除符合條件的節點，並釋放其記憶體。
- 記憶體管理
- 透過
free()釋放已使用的記憶體，避免記憶體洩漏。
4. 鏈結串列的種類
本節將介紹鏈結串列的主要類型與各自的特點，並分析其優缺點，幫助您根據需求選擇合適的結構。
1. 單向鏈結串列
每個節點僅指向下一個節點。
特點：
- 節點只能單方向移動。
- 記憶體消耗少，結構簡單。
優點：
- 可動態調整大小，靈活性高。
- 新增與刪除操作效率佳。
缺點：
- 無法反向遍歷，逆向搜尋效率低。
2. 雙向鏈結串列
每個節點同時指向前一個與下一個節點。
特點：
- 具備前後兩個指標。
- 可雙向移動，操作靈活。
優點：
- 雙向移動方便，刪除與搜尋容易。
- 可直接反向操作。
缺點：
- 比單向串列佔用更多記憶體。
- 實作較複雜。
3. 循環鏈結串列
最後一個節點指向第一個節點，形成循環結構。
特點：
- 無終點，可不斷循環。
- 可為單向或雙向形式。
優點：
- 可方便地在首尾之間切換，適合迴圈處理。
- 適用於佇列與緩衝區實作。
缺點：
- 由於無終點，刪除與搜尋需格外小心。
5. 鏈結串列的操作
本節將詳細介紹鏈結串列的基本操作，包括插入、刪除與搜尋，並附上程式碼範例。
1. 插入元素
在鏈結串列中插入元素主要有三種方式：
(1) 在串列開頭插入
在串列的開頭新增節點。
void insertAtHead(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = *head; // 新節點指向原本的頭節點
*head = newNode; // 更新頭節點
}(2) 在串列尾端插入
在串列末尾新增節點。
void insertAtTail(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) { // 串列為空
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) { // 移動到最後一個節點
temp = temp->next;
}
temp->next = newNode; // 新節點接到尾端
}2. 刪除元素
刪除鏈結串列中的元素。
(1) 刪除開頭元素
void deleteAtHead(Node** head) {
if (*head == NULL) {
printf("串列為空。\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
free(temp); // 釋放記憶體
}(2) 刪除特定值的節點
void deleteNode(Node** head, int key) {
Node* temp = *head;
Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("找不到指定值。\n");
return;
}
prev->next = temp->next;
free(temp);
}3. 搜尋元素
搜尋鏈結串列中是否存在指定值。
int search(Node* head, int key) {
Node* temp = head;
int position = 0;
while (temp != NULL) {
if (temp->data == key) {
return position; // 回傳位置
}
temp = temp->next;
position++;
}
return -1; // 未找到
}4. 顯示串列內容
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}小結
- 插入操作可在開頭、尾端或任意位置新增元素。
- 刪除操作可移除開頭元素或特定值的節點。
- 搜尋操作可找到元素位置並回傳。
6. 記憶體管理注意事項
在鏈結串列實作中，記憶體管理至關重要。本節將說明動態記憶體分配與避免記憶體洩漏的方法。
1. 什麼是動態記憶體分配？
在 C 語言中，建立鏈結串列節點時通常需要使用 malloc() 動態分配記憶體，確保執行階段可靈活配置所需的空間。
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("記憶體分配失敗。\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}2. 記憶體釋放的重要性
如果在刪除節點後沒有適時釋放記憶體，就會造成記憶體洩漏。
void freeList(Node* head) {
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}3. 避免記憶體洩漏的最佳實踐
- 務必釋放不再使用的記憶體
- 使用偵錯工具（如 Valgrind、AddressSanitizer）檢測洩漏位置
- 明確管理指標，使用後將其設為
NULL防止誤用
valgrind --leak-check=full ./a.out小結
- 動態記憶體分配是鏈結串列靈活性的基礎。
- 忘記釋放記憶體會造成程式不穩定。
- 善用工具檢查可避免潛在問題。
7. 應用範例與實務活用
本節將介紹鏈結串列在實務上的應用，包括堆疊（Stack）與佇列（Queue）的實作，展示其靈活性與實用性。
1. 堆疊實作範例
堆疊是一種後進先出（LIFO）的資料結構，最後加入的元素會最先被取出。
程式碼範例：使用鏈結串列實作堆疊
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void push(Node** top, int data) {
Node* newNode = createNode(data);
newNode->next = *top;
*top = newNode;
}
int pop(Node** top) {
if (*top == NULL) {
printf("堆疊為空。\n");
exit(1);
}
Node* temp = *top;
int poppedData = temp->data;
*top = (*top)->next;
free(temp);
return poppedData;
}
void printStack(Node* top) {
while (top != NULL) {
printf("%d -> ", top->data);
top = top->next;
}
printf("NULL\n");
}
int main() {
Node* stack = NULL;
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("堆疊內容: ");
printStack(stack);
printf("彈出值: %d\n", pop(&stack));
printf("彈出值: %d\n", pop(&stack));
printf("堆疊內容: ");
printStack(stack);
return 0;
}2. 佇列實作範例
佇列是一種先進先出（FIFO）的資料結構，最先加入的元素會最先被取出。
程式碼範例：使用鏈結串列實作佇列
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct Queue {
Node* front;
Node* rear;
} Queue;
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
void enqueue(Queue* q, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
int dequeue(Queue* q) {
if (q->front == NULL) {
printf("佇列為空。\n");
exit(1);
}
Node* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return data;
}
void printQueue(Queue* q) {
Node* temp = q->front;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
Queue* q = createQueue();
enqueue(q, 1);
enqueue(q, 2);
enqueue(q, 3);
printf("佇列內容: ");
printQueue(q);
printf("取出值: %d\n", dequeue(q));
printf("取出值: %d\n", dequeue(q));
printf("佇列內容: ");
printQueue(q);
return 0;
}小結
- 堆疊：適合遞迴運算與表達式求值等 LIFO 場景。
- 佇列：適合緩衝區、任務排程等 FIFO 場景。
8. 總結
本文詳細介紹了 C 語言中的鏈結串列，從基本概念、實作範例到應用案例，幫助讀者建立完整的理解與實作能力。
1. 重點回顧
鏈結串列基礎
- 鏈結串列可動態調整大小，靈活性高。
- 與陣列相比，新增與刪除更高效，但搜尋速度較慢。
實作與操作
- 示範了節點建立、插入、刪除、搜尋等操作。
- 強調了正確的記憶體管理以防止記憶體洩漏。
種類與用途
- 單向鏈結串列：結構簡單，適合輕量處理。
- 雙向鏈結串列：適合需要前後移動的情境。
- 循環鏈結串列：適合重複處理與迴圈操作。
應用範例
- 使用鏈結串列實作堆疊與佇列，展示其靈活應用能力。
2. 學習成果與應用能力
- 理解資料結構原理
- 提升 C 語言程式設計能力
- 增強解決問題的能力
3. 後續學習方向
- 資料結構進階
- 樹狀結構（例如二元樹、AVL 樹）
- 圖形演算法（BFS、DFS）
- 進階資料管理
- 雜湊表（Hash Table）與映射結構
- 動態陣列與鏈結串列混合設計
- 演算法最佳化
- 排序與搜尋演算法的效能優化
- 時間與空間複雜度分析
4. 實務應用建議
- 任務管理應用程式
- 模擬系統
- 資料分析工具
5. 結語
鏈結串列雖屬於基礎資料結構，但應用範圍廣泛，對複雜系統的開發也極具價值。透過本文的內容，相信讀者已能從基礎到進階全面掌握鏈結串列，並靈活運用於實務專案中。
