Double Linked List

Motivasi

Pada materi sebelumnya, kita mengibaratkan Single Linked List seperti rangkaian gerbong kereta api. Sayangnya, desain Single ibarat gerbong yang pintunya hanya bisa dilewati satu arah: Anda bisa berjalan dari lokomotif ke gerbong paling belakang, tetapi tidak bisa berjalan mundur kembali ke lokomotif. Jika Anda terlewat satu gerbong saat mencari tempat duduk, Anda harus turun, kembali ke lokomotif, dan mengulang pencarian dari awal.

Double Linked List memecahkan masalah ini dengan menambahkan satu pointer lagi. Setiap Node kini memiliki kemampuan melihat siapa elemen setelahnya dan siapa elemen sebelumnya.

Selain itu, kita juga menambahkan penunjuk di bagian ekor (Last). Jika sebelumnya kita harus menelusuri ratusan elemen satu per satu hanya untuk menambahkan data di akhir, kini kita bisa langsung melompat ke belakang karena posisi elemen terakhir sudah dicatat secara eksplisit di pointer Last.

Konsep Inti

Elemen List berpointer ganda memiliki tiga atribut utama:

1. info: Menyimpan nilai data yang sebenarnya.
2. next: Menyimpan alamat elemen selanjutnya.
3. prev: Menyimpan alamat elemen sebelumnya.

Kondisi List dikenali dari dua penunjuk utama: first dan last.

• Jika List kosong: first bernilai NULL dan last bernilai NULL.
• Jika List hanya berisi 1 elemen: pointer first dan last menunjuk ke Node yang sama, sementara prev dan next gerbong tersebut bernilai NULL.

Perbandingan Struktur

Operasi Dasar

Karena setiap elemen memiliki dua lengan (prev dan next), operasi penyambungan dan pemutusan rantai menjadi lebih banyak secara logika. Anda tidak boleh hanya mengurus satu arah, melainkan kedua arahnya.

Menambah di Awal

Berikut adalah logika untuk operasi InsertFirst:

void InsertFirst(List *L, int x) {
    Node *N = Allocation(x);
    
    if (N != NULL) {
        N->next = L->first;
        
        if (!IsEmpty(L)) {
            // Jika list sudah ada isinya, gerbong pertama lama menunjuk mundur ke gerbong baru
            L->first->prev = N; 
        } else {
            // Jika list kosong, maka gerbong baru ini juga sekaligus menjadi Last
            L->last = N; 
        }
        
        // Pindahkan gelar First ke gerbong baru
        L->first = N; 
    }
}

Navigasi Maju dan Mundur

Keunggulan utama struktur ini adalah fleksibilitas pembacaan data. Kita bisa mencetak data secara terbalik dengan memulai dari pointer last dan menelusuri mundur menggunakan prev.

void PrintMaju(List L) {
    cout << "Dari Depan  : ";
    Node *temp = L.first;
    while (temp != NULL) {
        cout << temp->info << " ";
        temp = temp->next;
    }
    cout << "\n";
}

void PrintMundur(List L) {
    cout << "Dari Belakang: ";
    Node *temp = L.last;
    while (temp != NULL) {
        cout << temp->info << " ";
        temp = temp->prev;
    }
    cout << "\n";
}