C語言單鏈表完整實現：帶頭節點版教學

編輯：關於C語言

引言

單鏈表是動態數據結構的基礎，透過指針串聯節點，支援高效的插入與刪除。本文提供一套帶頭節點的單鏈表 C 語言實現，涵蓋建立、銷毀、查找、插入、刪除、遍歷等核心操作，代碼結構清晰，適合教學與項目參考。

一、標頭檔 `list.h`

typedef int ElementType;
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List CreateList();
void DisposeList(List L);
List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
void SetAdvance(Position P, Position NextP);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif // LIST_H_INCLUDED

二、錯誤處理 `fatal.h`

#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str) FatalError(Str)
#define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED

三、核心實現 `list.c`

#include "list.h"
#include "fatal.h"

struct Node {
    ElementType Element;
    Position Next;
};

List CreateList() {
    List L = malloc(sizeof(struct Node));
    if (L == NULL) FatalError("Out of space!!!");
    L->Next = NULL;
    return L;
}

void DisposeList(List L) {
    MakeEmpty(L);
    free(L);
}

List MakeEmpty(List L) {
    if (L == NULL) Error("Must use CreateList first");
    if (L->Next != NULL) DeleteList(L);
    return L;
}

int IsEmpty(List L) { return L->Next == NULL; }

int IsLast(Position P, List L) { return P->Next == NULL; }

Position Find(ElementType X, List L) {
    Position P = L->Next;
    while (P != NULL && P->Element != X) P = P->Next;
    return P;
}

void Delete(ElementType X, List L) {
    Position P = FindPrevious(X, L);
    if (!IsLast(P, L)) {
        Position TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

Position FindPrevious(ElementType X, List L) {
    Position P = L;
    while (P->Next != NULL && P->Next->Element != X) P = P->Next;
    return P;
}

void Insert(ElementType X, List L, Position P) {
    Position TmpCell = malloc(sizeof(struct Node));
    if (TmpCell == NULL) FatalError("Out of space!!!");
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

void DeleteList(List L) {
    Position P = L->Next;
    L->Next = NULL;
    while (P != NULL) {
        Position Tmp = P->Next;
        free(P);
        P = Tmp;
    }
}

Position Header(List L) { return L; }
Position First(List L) { return L->Next; }
Position Advance(Position P) { return P->Next; }
ElementType Retrieve(Position P) { return P->Element; }
void SetAdvance(Position P, Position NextP) { P->Next = NextP; }

四、設計亮點解析

4.1 頭節點優勢

引入虛擬頭節點可統一插入/刪除邏輯，無需對首元素特判，代碼更簡潔健壯。

4.2 記憶體管理

CreateList 分配頭節點，DisposeList 先清空再釋放頭節點，避免洩漏。
Insert 動態分配新節點，Delete 與 DeleteList 及時 free。

4.3 介面設計

提供 Header、First、Advance、Retrieve 等抽象操作，上層邏輯無需直接操作指針，封裝性良好。

五、使用範例

List L = CreateList();
Insert(10, L, Header(L));
Insert(20, L, Header(L));
Position P = Find(10, L);
if (P) printf("Found: %d\n", Retrieve(P));
Delete(10, L);
DisposeList(L);