Mengenal Linked List: Perbedaan Singly dan Doubly Linked List

Pendahuluan

Halo, teman-teman developer! Senang sekali bisa bertemu kembali di artikel ketiga dalam seri struktur data kita. Pada artikel sebelumnya, kita sudah berhasil menguasai penggunaan Array untuk mengelola data dalam sebuah antrian. Kita belajar bagaimana mengakses, menambah, dan menghapus elemen pada indeks tertentu. Namun, sebagai developer berpengalaman, kita pasti pernah menghadapi situasi di mana Array mulai terasa “berat” atau tidak efisien, terutama saat kita harus melakukan operasi hapus atau tambah di tengah-tengah data yang jumlahnya ribuan.

Di sinilah kita membutuhkan struktur data lain yang lebih fleksibel secara dinamis: Linked List. Jika Array ibarat deretan kursi bioskop yang sudah dipesan nomornya secara tetap, maka Linked List ibarat barisan orang yang sedang mengantri di sebuah bank atau gerai Tokopedia yang bisa bertambah atau berkurang kapan saja tanpa perlu merombak seluruh susunan kursi.

Dalam tutorial ini, kita akan membedah dua jenis Linked List yang paling fundamental, yaitu Singly Linked List dan Doubly Linked List. Kita juga akan melihat bagaimana keunggulan struktur data ini dapat kita terapkan langsung ke dalam proyek Sistem Antrian yang sedang kita bangun. Di akhir artikel, kamu akan memahami kapan harus menggunakan salah satunya agar aplikasimu berjalan dengan performa optimal.

Mengenal Singly Linked List

Singly Linked List adalah bentuk paling dasar dari Linked List. Bayangkan sebuah gerbong kereta api di mana setiap gerbong hanya memiliki satu sambungan ke gerbong di depannya. Di dalam pemrograman, kita menyebut setiap gerbong ini sebagai Node.

Setiap Node dalam Singly Linked List memiliki dua komponen utama:

1. Data: Nilai yang ingin kita simret (misalnya: nama nasabah).
2. Next: Sebuah pointer atau referensi yang menunjuk ke Node berikutnya dalam urutan.

Karakteristik utama dari Singly Linked List adalah arah pergerakannya yang hanya satu arah (maju). Kamu bisa dengan mudah berpindah dari Budi ke Siti, tapi kamu tidak bisa kembali dari Siti ke Budi tanpa memulai pencarian dari awal (dari head).

Mari kita lihat implementasi sederhananya menggunakan Python:

class Node:
    """Representasi satu elemen dalam linked list."""
    def __init__(self, data):
        self.data = data  # Menyimpan data (misal: Nama Nasabah)
        self.next = None  # Pointer ke node selanjutnya

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # Node pertama dalam list

    def tambah_di_akhir(self, data):
        """Menambahkan node baru di ujung list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        # Kita harus melakukan traversal (berjalan) sampai ke ujung
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def tampilkan_list(self):
        """Menampilkan semua data dalam list."""
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(elements) if elements else "List Kosong")

# Penggunaan Singly Linked List
antrian_singles = SinglyLinkedList()
antrian_singles.tambah_di_akhir("Budi")
antrian_singles.tambah_di_akhir("Siti")
antrian_singles.tambah_di_akhir("Andi")

print("Antrian Singly Linked List:")
antrian_singly.tampilkan_list()
# Output: Budi -> Siti -> Andi

Pada kode di atas, perhatikan fungsi tambah_di_akhir. Jika kita ingin menambah data di ujung, kita harus melakukan traversal (berjalan) dari head sampai menemukan node yang next-nya adalah None. Inilah kelemahan Singly Linked List: jika datanya sangat banyak, proses pencarian ujungnya memakan waktu lebih lama (O(n)).

Mengenal Doubly Linked List

Sekarang, mari kita tingkatkan levelnya. Bagaimana jika kita ingin bisa bergerak mundur? Misalnya, dalam sistem antrian, seorang petugas ingin mengecek nasabah sebelumnya karena ada kesalahan input. Di sinilah Doubly Linked List berperan.

Dalam Doubly Linked List, setiap Node memiliki tiga komponen:

1. Data: Nilth yang disimpan.
2. Next: Pointer ke node berikutnya.
3. Prev: Pointer ke node sebelumnya.

Dengan adanya pointer prev, kita bisa melakukan navigasi dua arah (maju dan mundur). Hal ini sangat berguna untuk operasi seperti menghapus node di tengah atau melakukan reverse traversal.

Berikut adalah implementasinya:

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None # Kita simpan tail agar tambah data lebih cepat

    def tambah_di_akhir(self, data):
        new_node = DoublyNode(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return

        # Menghubungkan tail saat ini ke node baru
        self.tail.next = new_node
        new_node.prev = self.tail  # Menghubungkan node baru ke tail lama
        self.tail = new_node

    def tampilkan_list(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" <-> ".join(elements) if elements else "List Kosong")

# Penggunaan Doubly Linked List
antrian_doubly = DoublyLinkedList()
antrian_doubly.tambah_di_akhir("Dewi")
antrian_doubly.tambah_di_akhir("Reza")
antrian_doubly.tambah_di_akhir("Siti")

print("\nAntrian Doubly Linked List:")
antrian_doubly.tampilkan_list()
# Output: Dewi <-> Reza <-> Siti

Keuntungan utama Doubly Linked List adalah kita bisa menghapus node dengan lebih efisien jika kita sudah memegang referensi ke node tersebut, karena kita tahu siapa tetangga sebelumnya (prev) tanpa harus melakukan iterasi dari awal lagi.

Perbandingan Ringkas

Implementasi Akhir: Sistem Antrian Bank

Mari kita gabungkan semua konsep ini ke dalam sebuah kelas yang lebih nyata. Kita akan membuat sistem manajemen antrian sederhana menggunakan prinsip Doubly Linked List untuk memudahkan penghapusan nasabah yang membatalkan antrean.

class NasabahNode:
    def __init__(self, nama):
        self.nama = nama
        self.next = None
        self.prev = None

class SistemAntrian:
    def __init__(self):
        self.head = None
        self.tail = None
        self.jumlah_antrian = 0

    def tambah_antrian(self, nama):
        baru = NasabahNode(nama)
        if not self.head:
            self.head = self.tail = baru
        else:
            self.tail.next = baru
            baru.prev = self.tail
            self.tail = baru
        self.jumlah_antrian += 1
        print(f"✅ {nama} berhasil masuk antrean.")

    def panggil_nasabah(self):
        if not self.head:
            print("⚠️ Antrean kosong!")
            return
        
        dipanggil = self.head.nama
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        
        self.jumlah_antrian -= 1
        print(f"🔔 Panggilan: Nasabah '{dipanggil}' silakan menuju teller.")
        return dipanggil

    def batal_antrian(self, nama):
        # Mencari nasabah berdasarkan nama (simulasi sederhana)
        current = self.head
        while current:
            if current.nama == nama:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                
                self.jumlah_antrian -= 1
                print(f"❌ Antrean '{nama}' telah dibatalkan.")
                return True
            current = current.next
        print(f"❓ Nasabah '{nama}' tidak ditemukan di antrean.")
        return False

    def tampilkan_antrean(self):
        if not self.head:
            print("Antrean saat ini: [Kosong]")
            return
        
        print("Daftar Antrean Saat Ini:")
        current = self.head
        idx = 1
        while current:
            print(f"{idx}. {current.nama}")
            current = current.next
            idx += 1

# --- Uji Coba Sistem ---
bank_abc = SistemAntrian()
bank_abc.tambah_antrian("Budi")
bank_abc.tambah_antrian("Santi")
bank_abc.tambah_antrian("Andi")

bank_abc.tampilkan_antrean()

print("\n--- Proses Pembatalan ---")
bank_abc.batal_antrian("Santi")

print("\n--- Proses Pemanggilan ---")
bank_abc.panggil_nasabah()

print("\n--- Kondisi Akhir ---")
bank_abc.tampilkan_antrean()

Dengan menggunakan Doubly Linked List, proses batal_antrian menjadi sangat efisien karena kita bisa langsung menghubungkan prev ke next tanpa harus melakukan looping ulang dari awal untuk mencari siapa pendahulu dari node yang dihapus.

Demikian pembahasan mengenai Linked List. Pemahaman mendalam tentang struktur data ini akan menjadi fondasi kuat saat Anda mulai mempelajari struktur data yang lebih kompleks seperti Tree atau Graph!