鏈表核心結構
typedef struct Node {
int data; // 數據域，實際項目中用 void* 實現泛型
struct Node* next; // 指針域，指向下一個節點
} Node;
五大基本操作（含圖解邏輯）
1. 創建節點
Node* create_node(int val) {
Node* p = (Node*)malloc(sizeof(Node));
if (!p) return NULL; // 內存分配失敗檢查
p->data = val;
p->next = NULL;
return p;
}
2. 尾插法建表
Node* build_list(int arr[], int n) {
Node head = {0, NULL}; // 虛擬頭節點，簡化邊界處理
Node* tail = &head;
for (int i = 0; i < n; i++) {
tail->next = create_node(arr[i]);
tail = tail->next;
}
return head.next; // 返回真實頭節點
}
3. 遍歷打印
void print_list(Node* head) {
for (Node* p = head; p; p = p->next)
printf("%d -> ", p->data);
puts("NULL");
}
4. 指定位置插入/刪除
// 插入：在第 pos 個節點前插入 (pos 從 0 開始)
bool insert_node(Node** head, int pos, int val) {
Node* prev = NULL;
Node* curr = *head;
for (int i = 0; i < pos && curr; i++) {
prev = curr; curr = curr->next;
}
Node* node = create_node(val);
if (!node) return false;
node->next = curr;
if (prev) prev->next = node;
else *head = node; // 插入頭部
return true;
}
5. 銷毀鏈表（防內存洩漏）
void free_list(Node* head) {
while (head) {
Node* tmp = head;
head = head->next;
free(tmp);
}
}
進階話題
- 雙向鏈表：添加
prev 指針，支持 O(1) 反向遍歷與刪除；
- 循環鏈表：尾節點指向頭節點，適用於輪詢調度；
- 無鎖鏈表：CAS 原子操作實現併發安全，Linux Kernel 大量使用；
- 內存池優化：預分配大塊內存，減少
malloc/free 系統調用開銷。
調試技巧
- GDB 觀察鏈表：
print *(Node*)0x55... 逐個 follow next；
- Valgrind 檢測內存洩漏：
valgrind --leak-check=full ./a.out；
- 可視化工具：
gdb-python 腳本自動打印鏈表結構。
