C 語言實作單向循環鏈表：帶頭節點的尾插法建立

資料結構定義

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

完整建立函式

Node *create(void)
{
    const int n = 20;                 // 固定建立 20 個節點
    Node *pNew, *pTail, *pHead;

    // 1. 建立頭節點，next 指向自己，構成空循環表
    pHead = (Node *)malloc(sizeof(Node));
    if (!pHead) { perror("malloc head"); exit(EXIT_FAILURE); }
    pHead->next = pHead;

    pTail = pHead;                    // 尾指標初始指向頭節點

    // 2. 尾插法建立 20 個節點，data 為 1..20
    for (int i = 1; i <= n; i++) {
        pNew = (Node *)malloc(sizeof(Node));
        if (!pNew) { perror("malloc node"); exit(EXIT_FAILURE); }
        pNew->data = i;

        if (pHead->next == pHead) {   // 空表：第一個節點
            pHead->next = pNew;
            pTail = pNew;
        } else {                      // 非空表：接在尾部
            pTail->next = pNew;
            pTail = pNew;
        }
    }

    // 3. 閉合循環：尾節點 next 指向頭節點
    pTail->next = pHead;

    return pTail;                     // 回傳尾節點（亦可回傳 pHead）
}

關鍵設計點解析

1. 頭節點

• 不存放有效資料，僅作為入口哨兵。
• 空表時 head->next == head，判斷空表極簡單。
• 統一了「第一個節點」與「後續節點」的插入邏輯（雖本範例仍用 if 分支，純尾插法可完全統一）。

2. 尾指標

• 維護 pTail 指向最後一個資料節點，尾插時間複雜度 O(1)。
• 每次新增節點後更新 pTail = pNew。

3. 循環閉合

建立完成後必須執行 pTail->next = pHead，使最後一個節點指回頭節點，形成完整循環。

4. 回傳值選擇

• 回傳 pTail：便於後續尾插操作（直接用尾指標）。
• 回傳 pHead：便於遍歷、搜尋等從頭開始的操作。
• 視使用場景決定，亦可定義結構體同時包含頭尾指標。

常見操作範例

遍歷列印

void print_list(Node *head)
{
    Node *cur = head->next;
    while (cur != head) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    putchar('\n');
}

釋放記憶體

void free_list(Node *head)
{
    Node *cur = head->next;
    while (cur != head) {
        Node *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(head);
}

優化建議

• 將節點數 n 參數化，而非硬編碼。
• 錯誤處理改為回傳錯誤碼，而非直接 exit()，提高函式復用性。
• 考慮使用 calloc 自動歸零指標欄位。