單向循環鏈表：尾指針表示法的優勢與 C 實現

單向循環鏈表：尾指針表示法的優勢與 C 實現

單向循環鏈表是鏈式存儲結構的重要變體。本文採用 尾指針表示法：頭結點的 next 指向首元結點，尾指針 tail 指向尾結點，尾結點 next 指向頭結點，形成閉環。相較頭指針表示法，尾指針法在首尾節點訪問上均達到 O(1) 時間複雜度。

結構定義與初始化

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

void Initial_SCL_tail(LinkList* L) {
    *L = (LinkList)malloc(sizeof(Node));
    if (!*L) exit(1);
    (*L)->next = *L; // 空表：尾指針指向頭結點，頭結點next指向自身
}

核心操作：尾插法建表

void Create_SCLtail(LinkList* L, int number) {
    LinkList tail = *L, newNode;
    for (int i = 1; i <= number; i++) {
        newNode = (LinkList)malloc(sizeof(Node));
        scanf("%d", &newNode->data);
        tail->next = newNode;   // 原尾結點指向新結點
        newNode->next = *L;     // 新結點指向頭結點
        tail = newNode;         // 更新尾指針
    }
    *L = tail; // 函數返回時，L 指向尾結點
}

鏈表合併：O(1) 連接兩個循環鏈表

void connect(LinkList LA, LinkList* LB) {
    // LA、LB 均為尾指針
    LinkList temp = LA->next;       // LA 首元結點
    LinkList temp1 = (*LB)->next;   // LB 頭結點
    LA->next = (*LB)->next->next;   // LA 尾接 LB 首元
    (*LB)->next = temp;             // LB 尾接 LA 首元
    free(temp1);                    // 釋放 LB 頭結點
}

此操作無需遍歷，僅調整 4 個指針即可完成合併，體現尾指針法的高效優勢。

遍歷顯示

void Display_SCLtail(LinkList L) {
    LinkList temp = L->next->next; // 首元結點
    while (temp != L->next) {      // 直到回到頭結點
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

總結

尾指針表示法通過犧牲常數級空間（額外維護尾指針），換取首尾操作 O(1) 的時間效能，特別適合頻繁在表尾插入、合併鏈表的場景。理解「頭結點不存數據、尾結點 next 指向頭結點」的環狀拓撲關係，是正確實現的關鍵。