您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

數據結構詳解：單鏈表的 C 語言實現與核心操作

編輯：關於C

鏈式存儲核心思想

單鏈表以離散的記憶體節點儲存線性表，每個節點包含數據域與指針域，透過指針串聯邏輯順序。優勢在於插入/刪除無需移動元素，只需修改指針；缺點是無法隨機存取，查找為 O(n)。

節點結構定義

typedef char DataType;               // 假設數據為字符
typedef struct Node {
    DataType data;                   // 數據域
    struct Node *next;               // 指針域，指向後繼節點
} ListNode;

typedef ListNode *LinkList;          // 鏈表頭指針類型
LinkList head;                       // 頭指針變量
ListNode *p;                         // 普通節點指針

關鍵約定： 終端節點的 next = NULL；鏈表由頭指針唯一確定。

頭指針與頭節點的區別

頭指針：指向第一個數據節點（或 NULL 表示空表），必須存在。
頭節點（可選）：附加在第一個數據節點前的哨兵節點，data 通常不存有效數據，便於統一插入/刪除邏輯（無需特判頭節點）。

節點的動態生成與釋放

// 生成節點
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p->data = 'A';
p->next = NULL;

// 訪問成員：兩種等價寫法
(*p).data;   // 解引用後取成員
p->data;     // 箭頭運算符，更常用

// 釋放節點
free(p);
p = NULL; // 防野指標

指針變量 vs 節點變量

	指針變量	節點變量
定義	編譯期顯式聲明	運行期 `malloc` 生成
值	節點地址	節點內容（數據+指針）
操作	直接用變量名	透過指針間接訪問

基本操作代碼範式

1. 尾插法建表

LinkList create_list_tail(DataType a[], int n) {
    LinkList head = (LinkList)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *tail = head;
    for (int i = 0; i < n; i++) {
        ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
        newnode->data = a[i];
        newnode->next = NULL;
        tail->next = newnode;
        tail = newnode;
    }
    return head;
}

2. 指定位置插入

bool insert_node(LinkList head, int pos, DataType val) {
    ListNode *pre = head;
    int i = 0;
    while (pre && i < pos - 1) { pre = pre->next; i++; }
    if (!pre) return false;
    ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
    newnode->data = val;
    newnode->next = pre->next;
    pre->next = newnode;
    return true;
}

3. 刪除節點

bool delete_node(LinkList head, int pos) {
    ListNode *pre = head;
    int i = 0;
    while (pre->next && i < pos - 1) { pre = pre->next; i++; }
    if (!pre->next) return false;
    ListNode *del = pre->next;
    pre->next = del->next;
    free(del);
    return true;
}