資料結構教科書精華：線性表的三種鏈式儲存結構——單循環、雙向、靜態鏈表

2.5 線性表的其他表示形式

1. 單循環鏈表

將單鏈表尾節點 next 指向頭節點，形成環。
優勢：從尾節點可 O(1) 到達頭節點，適合頻繁頭尾操作。
合併兩表 O(1) 技巧：

q = r1->next;           // 保存 L1 頭節點
r1->next = r2->next->next; // L1 尾接 L2 首數據節點
free(r2->next);         // 釋放 L2 頭節點
r2->next = q;           // L2 尾接 L1 頭，成環

2. 雙向鏈表

節點增設 prior 指向前驅，next 指向後繼。

typedef struct DuNode {
    DataType data;
    struct DuNode *prior, *next;
} DuNode, *DuLinkList;

s->prior = q->prior;   // (1)
q->prior = s;          // (2) (1)(2)順序不可換，否則丟失 q 原前驅
q->prior->next = s;
s->next = q;

q->next->prior = q->prior; // (1)
q->prior->next = q->next;  // (2)
free(q);

3. 靜態鏈表

以陣列模擬鏈表，指標改為陣列下標 (靜態指標)，空指標用 -1 表示。

#define MAXSIZE 1000
typedef struct {
    DataType data;
    int next;  // 下一節點下標
} SNode;
SNode S[MAXSIZE];
int SL, SX;  // SL: 用戶鏈表頭, SX: 空閒鏈表頭

if (SX != -1) {
    t = SX;
    SX = S[SX].next;
}

S[t].next = SX;
SX = t;

三種結構對比

總結

單循環鏈表優化頭尾連接，雙向鏈表以空間換雙向 O(1) 操作，靜態鏈表以陣列下標替代指標適配受限環境。掌握三者節點定義、指標/下標維護邏輯與典型操作，是資料結構工程落地的核心基本功。