資料結構教材實作：雙向循環鏈表完整原始碼

資料結構教材實作：雙向循環鏈表完整原始碼

結構特性

雙向循環鏈表將頭尾相連，每個節點同時擁有 prior（前驅）與 next（後繼）指標，支援雙向遍歷，解決了單鏈表無法回溯的缺陷。

插入與刪除指標操作示意

型別定義 (DualCycleLinkedList.h)

typedef int ElemType;
typedef struct DulNode {
    ElemType data;
    struct DulNode *prior, *next;
} DulNode, *DuLinkList;

核心操作：插入節點

Status ListInsert(DuLinkList &L, int i, ElemType e) {
    DuLinkList p = GetElemP(L, i);  // 定位第 i 個節點
    if (!p) return ERROR;
    DuLinkList s = (DuLinkList)malloc(sizeof(DulNode));
    s->data = e;
    s->prior = p->prior;
    s->next = p;
    p->prior->next = s;
    p->prior = s;
    return OK;
}

核心操作：刪除節點

Status ListDelete(DuLinkList &L, int i, ElemType &e) {
    DuLinkList p = GetElemP(L, i);
    if (!p) return ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}

測試結果

工程應用提示

雙向循環鏈表常用於LRU 快取淘汰鏈表、記憶體管理空閒塊鏈表、音樂播放列表等需要頻繁雙向遍歷與 O(1) 刪除的場景。