C語言怎么實現單鏈表的基本功能

# C語言怎么實現單鏈表的基本功能

## 一、單鏈表概述

單鏈表（Singly Linked List）是最基礎的數據結構之一，它通過指針將一組零散的內存塊串聯起來。每個節點（Node）包含兩個部分：
- 數據域：存儲實際數據
- 指針域：存儲下一個節點的內存地址

### 1.1 單鏈表的特點
- 動態內存分配，不需要預先知道數據規模
- 插入/刪除時間復雜度O(1)
- 隨機訪問效率低，時間復雜度O(n)
- 需要額外空間存儲指針

### 1.2 與數組的對比
| 特性        | 數組          | 單鏈表       |
|------------|--------------|-------------|
| 內存連續性  | 連續          | 非連續       |
| 大小        | 固定          | 動態擴展     |
| 插入/刪除   | O(n)         | O(1)        |
| 隨機訪問    | O(1)         | O(n)        |

## 二、單鏈表的基本實現

### 2.1 節點結構定義
```c
typedef struct Node {
    int data;           // 數據域（以int為例）
    struct Node *next;  // 指針域
} Node;

2.2 鏈表創建

// 創建空鏈表
Node* createList() {
    return NULL;  // 返回空指針表示空鏈表
}

// 創建帶頭節點的鏈表
Node* createListWithHead() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

三、單鏈表的基本操作

3.1 插入操作

頭插法

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

尾插法

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* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

指定位置插入

void insertAtIndex(Node** head, int index, int data) {
    if (index < 0) return;
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    
    if (index == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    Node* current = *head;
    for (int i = 0; current != NULL && i < index - 1; i++) {
        current = current->next;
    }
    
    if (current == NULL) {
        free(newNode);
        return;
    }
    
    newNode->next = current->next;
    current->next = newNode;
}

3.2 刪除操作

刪除頭節點

void deleteAtHead(Node** head) {
    if (*head == NULL) return;
    
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

刪除尾節點

void deleteAtTail(Node** head) {
    if (*head == NULL) return;
    
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    free(current->next);
    current->next = NULL;
}

刪除指定位置節點

void deleteAtIndex(Node** head, int index) {
    if (*head == NULL || index < 0) return;
    
    if (index == 0) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    Node* current = *head;
    for (int i = 0; current != NULL && i < index - 1; i++) {
        current = current->next;
    }
    
    if (current == NULL || current->next == NULL) return;
    
    Node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

3.3 查找操作

按值查找

Node* searchByValue(Node* head, int value) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

按索引查找

Node* searchByIndex(Node* head, int index) {
    if (index < 0) return NULL;
    
    Node* current = head;
    for (int i = 0; current != NULL && i < index; i++) {
        current = current->next;
    }
    return current;
}

3.4 遍歷鏈表

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

3.5 鏈表長度

int getLength(Node* head) {
    int count = 0;
    Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

四、進階操作

4.1 鏈表反轉

Node* reverseList(Node* head) {
    Node *prev = NULL, *current = head, *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

4.2 檢測環

int hasCycle(Node* head) {
    if (head == NULL) return 0;
    
    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;
}

4.3 合并兩個有序鏈表

Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy = {0, NULL};
    Node* tail = &dummy;
    
    while (l1 && l2) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

五、內存管理與錯誤處理

5.1 釋放整個鏈表

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

5.2 常見錯誤

1. 空指針解引用
2. 內存泄漏（忘記free）
3. 野指針（使用已釋放的內存）
4. 越界訪問

六、完整示例程序

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// [此處插入前面定義的所有函數]

int main() {
    Node* list = createList();
    
    // 插入測試
    insertAtTail(&list, 1);
    insertAtTail(&list, 2);
    insertAtHead(&list, 0);
    insertAtIndex(&list, 1, 9);
    
    printf("Original List: ");
    traverseList(list);  // 輸出: 0 -> 9 -> 1 -> 2 -> NULL
    
    // 刪除測試
    deleteAtIndex(&list, 1);
    deleteAtHead(&list);
    
    printf("After deletion: ");
    traverseList(list);  // 輸出: 1 -> 2 -> NULL
    
    // 反轉測試
    list = reverseList(list);
    printf("Reversed List: ");
    traverseList(list);  // 輸出: 2 -> 1 -> NULL
    
    freeList(&list);
    return 0;
}

七、性能優化建議

1. 對于頻繁的尾部操作，可以維護一個尾指針
2. 考慮使用帶頭節點的鏈表簡化邊界條件處理
3. 批量操作時可以考慮緩存長度信息
4. 多線程環境下需要加鎖保護

八、應用場景

1. 實現棧、隊列等數據結構
2. 多項式運算
3. 內存管理中的空閑塊鏈表
4. 文件系統的目錄結構
5. 哈希表的鏈地址法實現

九、總結

單鏈表作為基礎數據結構，雖然簡單但功能強大。掌握其C語言實現需要理解： - 指針操作和內存管理 - 邊界條件處理 - 時間/空間復雜度分析 - 實際應用場景

通過不斷練習，可以深入理解鏈表的特性和應用，為學習更復雜的數據結構打下堅實基礎。 “`