前幾天我們把單向鏈結串列和雙向鏈結串列都學過了，今天我們要來看環狀鏈結串列~
這篇就先主要以介紹單向環狀鏈結串列和他的基本應用為主

什麼是環狀鏈結串列 ?

環狀鏈結串列是一種特殊結構，最後一個節點不指向NULL，而是指向第一個節點
然後串列中任何一個節點，都可以達到此串列內的其他節點。

• 優點 : 任何一個節點都能走訪到所有節點
• 缺點 : 需要多一個鏈結空間

單向環狀鏈結串列

雙向環狀鏈結串列

節點結構

單向環狀鏈結串列和單向鏈結串列一樣
差別只在於「指標怎麼接」,不是節點本身有什麼不同

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

建立一個簡單的環狀鏈結串列

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};
head->next->next->next = head;   // 最後一個節點指回head,形成環

複習 : 設定資料 Day 8 - 單向鏈結串列(Singly Linked list)

head->data = 10;
head->next = nullptr; //Node* head = new Node{10,nullptr}

跟 Day 8 的建立方式幾乎一樣,只差最後一行不是讓最後一個節點指向 nullptr,
而是讓它指回 head

走訪環狀鏈結串列

和一般走訪的判斷不一樣
一般來說我們的走訪通常會用下列程式來判斷

while(current != nullptr)

但在這裡完全不行，因為環狀鏈結串列裡面沒有任何一個指標是nullptr
每個節點都指向下一個節點，最後一個節點指回head,用上述寫法會造成無窮迴圈

正確的寫法應該要判斷 是否繞回head 來結束

void traverse(Node* head) {
    if (head == nullptr) return;   // 空串列,直接返回

    Node* current = head;
    do {
        cout << current->data << " ";
        current = current->next;
    } while (current != head);// 走到繞回head才停止,而不是判斷nullptr
}

為什麼用do-while而不是while勒?

因為如果用 while(current != head)，一開始的 current 就是 head，
那迴圈跟本執行不了
所以用do-while還能確保先執行一次再判斷

刪除環狀鏈結串列節點

void deleteAfter(Node* p) {
    if (p->next == p) return;  // 只剩自己一個節點,不能再刪了

    Node* target = p->next;
    p->next = target->next;
    delete target;
}

刪除第一個節點(head)

void deleteHead() {
    if (head == nullptr) return; // 空串列,沒有東西可刪

    if (head->next == head) { // 只剩一個節點的情況
        delete head;
        head = nullptr; // 刪完之後串列變空
        return;
    }

    Node* current = head;
    while (current->next != head) {
        current = current->next; //找到最後一個節點並記下來
    }
    Node* tail = current;

    Node* oldHead = head; // 先記住要刪除的節點
    head = head->next; 
    tail->next = head;
    delete oldHead;  // 釋放原本head的記憶體
}

插入節點

於指定 節點p 後插入新的節點

void insertAfter(Node* p, int data) {
    Node* newNode = new Node{data, nullptr};
    newNode->next = p->next;
    p->next = newNode;
}

一般鏈結串列 vs 環狀鏈結串列

參考資料和書籍

1. https://hackmd.io/@sysprog/c-linked-list
2. https://medium.com/@racktar7743/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E9%9B%99%E5%90%91%E7%92%B0%E7%8B%80%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%95%99%E5%AD%B8-1-%E6%96%B0%E5%A2%9E%E8%88%87%E5%8D%B0%E5%87%BA-308ee6370e1c
3. 圖解資料結構×演算法:運用C++ 胡昭明
4. 資料結構初學指引:入門精要版 陳錦輝