Circular Linked List

Motivasi: Perjalanan Tanpa Ujung

Pernahkah Anda memutar daftar lagu dengan mode Repeat All? Saat lagu terakhir selesai, pemutar musik tidak akan berhenti, melainkan otomatis kembali memutar lagu pertama. Atau, pernahkah Anda memikirkan bagaimana sistem operasi komputer membagi waktu prosesor secara adil untuk semua aplikasi yang sedang berjalan secara bergantian?

Itulah pesona dari Circular Linked List (List Sirkuler). Jika pada Single Linked List elemen terakhirnya selalu menunjuk ke jalan buntu (NULL), maka ciri khas utama List Sirkuler adalah tidak ada pointer next yang bernilai NULL. Elemen terakhir list akan menunjuk kembali ke alamat elemen pertama (first).

Perbandingan Struktur

Konsep Inti

Karena semua elemen list sirkuler saling terkait seperti cincin, list ini secara konsep sebenarnya tidak mempunyai ujung yang pasti. Kondisi list kosong tetap ditandai dengan first bernilai NULL.

Namun, jika list hanya berisi 1 elemen, maka elemen tersebut akan menunjuk ke dirinya sendiri (N->next = first).

Penelusuran (Traversal)

Menelusuri list sirkuler membutuhkan trik khusus. Anda tidak bisa lagi menggunakan NULL sebagai tanda berhenti karena akan menyebabkan putaran tanpa henti.

void PrintInfo(List *L) {
    if (IsEmpty(L)) {
        cout << "List kosong!" << endl;
        return;
    }
    
    Node *temp = L->first;
    // Menggunakan do-while agar elemen pertama tercetak dulu baru dicek kondisinya
    do {
        cout << temp->info << " ";
        temp = temp->next;
    } while (temp != L->first); 
}

Operasi Dasar

Karena struktur ini membentuk lingkaran, setiap kali kita menambah atau menghapus gerbong di posisi first, kita memiliki tugas tambahan: memberitahu gerbong paling belakang (ekor) bahwa ada "kepala" kereta yang baru!

Menambah di Awal

Penyisipan di awal berakibat kita harus melakukan penelusuran untuk mengubah next dari elemen ekor agar menunjuk ke first yang baru.

void InsertFirst(List *L, int x) {
    Node *N = Allocation(x);
    
    if (IsEmpty(L)) {
        // Jika list kosong, elemen menunjuk dirinya sendiri
        L->first = N;
        N->next = L->first;
    } else {
        // 1. Cari elemen terakhir dulu
        Node *temp = L->first;
        while (temp->next != L->first) { 
            temp = temp->next;
        }
        
        // 2. Sisipkan elemen baru di depan
        N->next = L->first;
        L->first = N;
        
        // 3. Kaitkan kembali ekor ke First yang baru
        temp->next = L->first; 
    }
}