【初階數據結構】鏈表的柔光之美

一、為什么需要鏈表？

二、鏈表與數組的對比

三、鏈表節點定義

四、鏈表基本操作

1. 創建鏈表

2. 插入節點

頭插法（時間復雜度O(1)）

尾插法（時間復雜度O(n)）

3. 刪除節點

4. 遍歷鏈表

五、進階操作

1. 反轉鏈表（迭代法）

2. 檢測環（快慢指針法）

六、內存管理要點

七、常見錯誤排查

八、鏈表變體

十、完整示例代碼

總結

路過的佬們點點關注哦~

你們的鼓勵是我前進的動力~

一、為什么需要鏈表？

在C語言程序設計中，數組是最基礎的數據結構，但它存在明顯的局限性：

固定長度，無法動態擴展
插入/刪除元素需要大量數據移動
內存空間要求連續

鏈表（Linked List）通過動態內存分配和指針連接完美解決了這些問題。每個元素（節點）包含：

數據域 - 存儲實際數據
指針域 - 存儲下一個節點的地址

二、鏈表與數組的對比

三、鏈表節點定義

typedef struct Node {int data;           // 數據域struct Node *next;  // 指針域
} Node;

四、鏈表基本操作

1. 創建鏈表

Node* createList(int data) {Node* head = (Node*)malloc(sizeof(Node));if (head == NULL) {printf("內存分配失敗！");exit(1);}head->data = data;head->next = NULL;return head;
}

2. 插入節點

頭插法（時間復雜度O(1)）

void insertAtHead(Node** head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = *head;*head = newNode;
}

尾插法（時間復雜度O(n)）

void insertAtTail(Node* head, int data) {Node* current = head;while (current->next != NULL) {current = current->next;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;current->next = newNode;
}

3. 刪除節點

void deleteNode(Node** head, int key) {Node *temp = *head, *prev;// 刪除頭節點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) return;// 解除鏈接并釋放內存prev->next = temp->next;free(temp);
}

4. 遍歷鏈表

void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}

五、進階操作

1. 反轉鏈表（迭代法）

void reverseList(Node** head) {Node *prev = NULL;Node *current = *head;Node *next = NULL;while (current != NULL) {next = current->next;  // 保存下一個節點current->next = prev;  // 反轉指針prev = current;        // 前移prevcurrent = next;        // 前移current}*head = prev;
}

2. 檢測環（快慢指針法）

int hasCycle(Node *head) {Node *slow = head, *fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {return 1;  // 存在環}}return 0;  // 無環
}

六、內存管理要點

必須檢查malloc返回值

Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {// 處理內存分配失敗
}

及時釋放內存

void freeList(Node* head) {Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}

避免野指針

free(temp);
temp = NULL;  // 釋放后立即置空

七、常見錯誤排查

段錯誤（Segmentation Fault）
- 訪問已釋放的內存
- 指針未初始化就使用
內存泄漏
- 使用valgrind工具檢測
- 確保每個malloc都有對應的free
邏輯錯誤
- 忘記更新頭指針
- 指針操作順序錯誤

八、鏈表變體

雙向鏈表

typedef struct DNode {int data;struct DNode *prev;struct DNode *next;
} DNode;

循環鏈表

// 尾節點指向頭節點
head->next = head;

帶頭節點的鏈表

統一操作邏輯
簡化邊界條件處理

九、應用場景

實現棧/隊列
多項式運算
文件系統目錄結構
圖結構的鄰接表
內存管理系統

十、完整示例代碼

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;// [此處插入上述各個函數實現]int main() {Node* list = createList(5);insertAtHead(&list, 2);insertAtTail(list, 8);printf("原始鏈表: ");printList(list);  // 輸出: 2 -> 5 -> 8 -> NULLreverseList(&list);printf("反轉后: ");printList(list);  // 輸出: 8 -> 5 -> 2 -> NULLdeleteNode(&list, 5);printf("刪除后: ");printList(list);  // 輸出: 8 -> 2 -> NULLfreeList(list);return 0;
}