資料結構：單向鏈表（C語言描述）

編輯：關於C語言

單向鏈表核心概念

單向鏈表是動態資料結構，由節點組成，每個節點包含資料域與指標域（指向下一節點）。特點：

記憶體不需連續，動態申請/釋放
插入/刪除 O(1)（已知位置），查找 O(n)
無隨機訪問能力

節點結構定義

typedef struct Node {
    int data;           // 資料域，可擴展為任意型別
    struct Node *next;  // 指標域，指向下一節點
} Node, *LinkList;

基本操作實現

1. 初始化（帶頭節點）

LinkList InitList() {
    LinkList L = (LinkList)malloc(sizeof(Node));
    if (!L) exit(OVERFLOW);
    L->next = NULL;
    return L;
}

2. 尾插法建表

void CreateList_Tail(LinkList L, int n) {
    LinkList r = L, p;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Node));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

3. 按位序插入

bool ListInsert(LinkList L, int i, int e) {
    LinkList p = L;
    int j = 0;
    while (p && j < i - 1) { p = p->next; j++; }
    if (!p || j > i - 1) return false;
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

4. 按位序刪除

bool ListDelete(LinkList L, int i, int *e) {
    LinkList p = L;
    int j = 0;
    while (p->next && j < i - 1) { p = p->next; j++; }
    if (!p->next || j > i - 1) return false;
    LinkList q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return true;
}

5. 按值查找

LinkList LocateElem(LinkList L, int e) {
    LinkList p = L->next;
    while (p && p->data != e) p = p->next;
    return p;  // 找到返回節點指標，否則 NULL
}

6. 遍歷輸出

void PrintList(LinkList L) {
    LinkList p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

7. 銷毀鏈表

void DestroyList(LinkList L) {
    LinkList p = L, q;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
}

進階操作

鏈表逆置（就地逆置）

void ReverseList(LinkList L) {
    LinkList p = L->next, q;
    L->next = NULL;
    while (p) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

合併兩有序鏈表

LinkList MergeList(LinkList La, LinkList Lb) {
    LinkList Lc = InitList(), pc = Lc;
    LinkList pa = La->next, pb = Lb->next;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pa = pa->next;
        } else {
            pc->next = pb; pb = pb->next;
        }
        pc = pc->next;
    }
    pc->next = pa ? pa : pb;
    free(Lb);
    return Lc;
}

單向鏈表 vs 陣列

操作	單向鏈表	陣列
存取第 i 個	O(i)	O(1)
插入/刪除（已知位置）	O(1)	O(n)
記憶體利用	動態、無碎片	靜態、可能浪費/不足
空間開銷	額外指標域	無額外開銷