Pada singly maupun doubly linked list biasa, tail menunjuk ke nullptr — rantai berhenti di akhir. Circular linked list mengubah ujung ini: tail menunjuk kembali ke head, sehingga list membentuk ring tanpa awal dan akhir yang kaku. Struktur ini cocok untuk masalah yang membutuhkan rotasi berulang: penjadwalan round-robin OS, ring buffer multimedia, atau permainan yang memutar giliran pemain. Pada Chapter ini kita akan membangun circular singly linked list, memahami trik menyimpan tail (bukan head), dan mengimplementasikan operasi rotate O(1) untuk round-robin scheduling.

Mengapa Circular #

Beberapa skenario alami membutuhkan struktur ring:

  1. Round-robin scheduling — CPU scheduler OS memberi tiap proses slot waktu bergantian secara siklik.
  2. Ring buffer — multimedia streaming menyimpan buffer data berputar agar slot dapat dipakai ulang.
  3. Game turn rotation — game multiplayer memutar giliran pemain 1 → 2 → 3 → 1 → 2 → …
  4. Buffer carousel — UI carousel yang berputar terus tanpa “stop” di akhir.

Tanpa circular, kita harus menulis kode if (cur == tail) cur = head; di setiap iterasi. Circular menghilangkan kasus khusus ini.

Trik Menyimpan Tail, Bukan Head #

Pada singly linked list biasa, kita menyimpan head. Pada circular singly, kita menyimpan tail dan mengakses head via tail->next. Alasannya: push_back memerlukan akses ke tail (untuk sambung ke node baru) dan ke head (untuk sambungkan tail baru ke head lama). Dengan menyimpan tail, kedua operasi tersebut O(1) tanpa traverse.

Tail (N3) menunjuk ke head (N1). Untuk traverse, kita mulai dari tail_->next (head), ikuti next, dan berhenti ketika kembali ke titik awal.

Operasi push_back #

Mekanisme: Sambungkan Tail Baru ke Head Lama #

  1. Alokasikan node baru n.
  2. Bila list kosong: n->next = n — node menunjuk ke dirinya sendiri, membentuk ring satu node.
  3. Bila tidak:
    • n->next = tail_->next — node baru menunjuk ke head lama.
    • tail_->next = n — tail lama menunjuk ke node baru.
    • tail_ = n — perbarui tail.

Operasi rotate: Geser Head ke Node Berikutnya #

Mekanisme: Mundur Tail Satu Langkah #

Pada circular list, “rotate” berarti memajukan head ke node berikutnya. Karena head = tail->next, kita bisa geser head dengan cara mundur tail:

cpp 
tail_ = tail_->next;

Sekarang tail_->next (head baru) adalah node kedua sebelumnya. Operasi O(1) tanpa traverse. Inilah pondasi round-robin scheduling.

Kode Circular Linked List #

cpp 
#include <iostream>

template <typename T>
struct Node {
    T nilai;
    Node* next;
    Node(const T& v) : nilai(v), next(nullptr) {}
};

template <typename T>
class CircularLinkedList {
public:
    CircularLinkedList() : tail_(nullptr), size_(0) {}
    ~CircularLinkedList() { clear(); }

    void push_back(const T& v) {
        Node<T>* n = new Node<T>(v);
        if (tail_ == nullptr) {
            n->next = n;       // node menunjuk ke dirinya sendiri
            tail_ = n;
        } else {
            n->next = tail_->next;   // n->next = head lama
            tail_->next = n;         // tail lama -> n
            tail_ = n;
        }
        ++size_;
    }

    void rotate() {
        if (tail_ != nullptr) tail_ = tail_->next;  // pindah tail ke head lama
    }

    void traverse(int langkah) const {
        if (tail_ == nullptr) {
            std::cout << "(kosong)\n";
            return;
        }
        Node<T>* cur = tail_->next;  // mulai dari head
        std::cout << "[";
        for (int i = 0; i < langkah; ++i) {
            std::cout << cur->nilai;
            if (i + 1 < langkah) std::cout << " -> ";
            cur = cur->next;
        }
        std::cout << " -> (kembali ke head)]\n";
    }

    void clear() {
        if (tail_ == nullptr) return;
        Node<T>* cur = tail_->next;
        while (size_ > 0) {
            Node<T>* nx = cur->next;
            delete cur;
            cur = nx;
            --size_;
        }
        tail_ = nullptr;
    }

    std::size_t size() const { return size_; }

private:
    Node<T>* tail_;
    std::size_t size_;
};

int main() {
    CircularLinkedList<std::string> cll;
    cll.push_back("A");
    cll.push_back("B");
    cll.push_back("C");
    cll.push_back("D");

    std::cout << "list awal:\n";
    cll.traverse(6);  // cetak 6 langkah — akan mutar penuh + 2 ekstra
    std::cout << "size = " << cll.size() << "\n\n";

    std::cout << "--- Round-robin: rotate 3x ---\n";
    for (int i = 1; i <= 3; ++i) {
        cll.rotate();
        std::cout << "setelah rotate " << i << ": ";
        cll.traverse(4);
    }
    return 0;
}

Output yang Dihasilkan:

text 
list awal:
[A -> B -> C -> D -> A -> B -> (kembali ke head)]
size = 4

--- Round-robin: rotate 3x ---
setelah rotate 1: [B -> C -> D -> A -> (kembali ke head)]
setelah rotate 2: [C -> D -> A -> B -> (kembali ke head)]
setelah rotate 3: [D -> A -> B -> C -> (kembali ke head)]
  1. Baris n->next = n; (di push_back, kasus list kosong): node menunjuk ke dirinya sendiri — ring satu node. Tidak ada nullptr di circular list; setiap next valid.
  2. Baris n->next = tail_->next; tail_->next = n; tail_ = n; (di push_back, kasus umum): tiga langkah untuk menyisipkan node di akhir ring. Pertama node baru menunjuk head lama, lalu tail lama menunjuk node baru, terakhir tail diperbarui.
  3. Baris tail_ = tail_->next; (di rotate): trik elegan — dengan menggeser tail satu langkah, head otomatis bergeser ke node kedua. O(1) tanpa traverse.
  4. Method traverse(int langkah): traverse melingkar tidak berhenti secara alami (tidak ada nullptr). Kita harus pakai counter langkah untuk menghindari loop tak terhingga.
  5. Hasil rotate 3x: setelah tiga rotate, head berpindah dari A → B → C → D. Pola ini persis dengan round-robin scheduler yang memberi giliran CPU.

Circular Doubly Linked List #

Kita juga bisa membuat circular doubly: tail->next = head dan head->prev = tail. Inilah struktur yang dipakai std::list dengan sentinel node — sebuah node dummy yang next menunjuk ke head asli dan prev menunjuk ke tail asli. Sentinel menyederhanakan kasus khusus (list kosong tidak perlu penanganan terpisah).

Aplikasi: Round-Robin Scheduler Sederhana #

Bayangkan kita ingin memodelkan CPU scheduler yang memberi tiap proses kuantum waktu 4 ms secara berputar. Circular linked list cocok karena rotasi O(1) dan tidak ada kasus “list habis”:

text 
[Kondisi awal]  A -> B -> C -> D -> (kembali ke A)
[Rotate 1]      B -> C -> D -> A -> (kembali ke B)   # A selesai kuantum, lanjut B
[Rotate 2]      C -> D -> A -> B -> (kembali ke C)   # B selesai, lanjut C

Tanpa circular, kita harus menulis if (cur->next == nullptr) cur = head; di setiap iterasi. Circular menghilangkan pengecekan ini — cur->next selalu valid.

Perbandingan Varian Linked List #

VarianAkhir dari tailPush_back O(1)Traverse mundurUse case
SinglynullptrYa (dengan tail)TidakStack, queue sederhana
DoublynullptrYaYaLRU cache, deque, undo
Circular singlyheadYaTidakRound-robin, ring buffer
Circular doublyhead (kedua arah)YaYaSTL std::list w/ sentinel

Ringkasan #

  • Circular linked list menyambungkan tail ke head, membentuk ring tanpa akhir.
  • Trik menyimpan tail_ (bukan head) membuat push_back dan rotate keduanya O(1).
  • Operasi rotate O(1) dengan tail_ = tail_->next — pondasi round-robin scheduler.
  • Traverse circular memerlukan counter atau kondisi berhenti eksplisit karena tidak ada nullptr yang mengakhiri loop.
  • Varian circular doubly + sentinel dipakai STL std::list untuk menghilangkan kasus khusus list kosong.