Linked list ganda

Linked list ganda menambah satu tautan ke belakang pada setiap node, sehingga rantainya dapat ditelusuri ke dua arah dan ujung belakangnya dapat dijangkau dalam waktu tetap. Topik ini membahas node dengan prev, yakni petunjuk menuju node sebelumnya, beserta keuntungan dan harganya. Implementasi dari nol pada Python menutup pembahasan, lalu collections.deque diperkenalkan sebagai pembanding bawaan yang sudah teruji.

Node dengan dua arah#

Node pada doubly linked list, yaitu linked list bertaut dua arah, menyimpan tiga bagian sekaligus: data, prev, dan next. Tautan next bergerak maju seperti biasa, sedangkan prev mengarah ke node sebelumnya, dan kedua ujungnya ditandai null pada head.prev maupun tail.next. Pointer tail, yaitu petunjuk ke node terakhir, biasanya disimpan di samping head karena posisi ujung belakang kini tersedia tanpa menelusuri.

Diagram berikut menampilkan tiga node dengan kedua arah tautannya, lengkap dengan head di depan dan tail di belakang. Tautan maju dan mundur pada sepasang node harus selalu sepakat, karena itulah yang membuat penelusuran ke dua arah dapat dipercaya.

Menambahkan node di antara dua node yang sudah terhubung kini menyentuh empat tautan, yaitu dua di node baru dan dua pada tetangganya. Satu tautan yang terlewat membuat penelusuran ke arah lain mendarat di node lama atau null. Karena itulah setiap operasi doubly linked list sedikit lebih panjang kodenya dibanding versi tunggalnya.

Keuntungan dan harganya#

Keuntungan pertama adalah penelusuran dua arah, yang berguna ketika operasi sering berjalan mundur dari ujung belakang. Keuntungan kedua adalah penghapusan node terakhir yang menjadi $O(1)$, karena tail.prev langsung menunjuk node sebelumnya, sedangkan singly linked list harus menelusuri $O(n)$ hanya untuk mencari node itu meskipun pointer tail tersimpan. Keuntungan ketiga terletak pada penghapusan node yang posisinya sudah diketahui, karena node itu membawa alamat pendahulunya sendiri sehingga tidak perlu dicari dari head.

Harganya terbaca dari tabel yang sama. Setiap node membawa satu tautan tambahan seumur hidupnya, dan setiap operasi merawat dua arah sekaligus sehingga peluang lupa memperbarui salah satu tautan menjadi lebih besar. Ada juga biaya kesabaran, karena lebih banyak baris yang harus ditulis dan diuji untuk perilaku yang sama.

Implementasi dari nol pada Python#

Berkas berikut memuat kelas NodeDua dan kelas DoublyList dengan append, append_left, remove_node, serta dua fungsi penelusuran berlawanan arah. Setiap penyisipan merawat tautan node baru dan ujung yang lama, sementara remove_node memperbarui hingga empat tautan sekaligus dengan dua pemeriksaan tepi. Fungsi telusur_maju dan telusur_mundur membuktikan bahwa rantai dapat dibaca dari kedua ujungnya.

"""Doubly linked list dari nol: node dengan prev dan next, head dan tail."""


class NodeDua:
    """Satu node menyimpan data, tautan prev ke belakang, dan next ke depan."""

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


class DoublyList:
    """Doubly linked list dengan pointer head di ujung depan dan tail di belakang."""

    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        """Tambahkan node di ujung belakang, O(1) berkat pointer tail."""
        baru = NodeDua(data)
        if self.tail is None:        # list masih kosong
            self.head = baru
            self.tail = baru
        else:
            baru.prev = self.tail
            self.tail.next = baru
            self.tail = baru

    def append_left(self, data):
        """Tambahkan node di ujung depan, juga O(1)."""
        baru = NodeDua(data)
        if self.head is None:        # list masih kosong
            self.head = baru
            self.tail = baru
        else:
            baru.next = self.head
            self.head.prev = baru
            self.head = baru

    def remove_node(self, nilai):
        """Hapus node pertama yang datanya sama, sambil merawat head dan tail."""
        kini = self.head
        while kini is not None:
            if kini.data == nilai:
                if kini.prev is not None:
                    kini.prev.next = kini.next
                else:
                    self.head = kini.next
                if kini.next is not None:
                    kini.next.prev = kini.prev
                else:
                    self.tail = kini.prev
                return True
            kini = kini.next
        return False

    def telusur_maju(self):
        """Kumpulkan data dari head menuju tail, satu arah maju."""
        hasil, kini = [], self.head
        while kini is not None:
            hasil.append(kini.data)
            kini = kini.next
        return hasil

    def telusur_mundur(self):
        """Kumpulkan data dari tail menuju head, satu arah mundur."""
        hasil, kini = [], self.tail
        while kini is not None:
            hasil.append(kini.data)
            kini = kini.prev
        return hasil


if __name__ == "__main__":
    a = DoublyList()
    a.append(4)
    a.append(8)
    a.append(15)
    a.append_left(1)
    print("maju               :", a.telusur_maju())
    print("mundur             :", a.telusur_mundur())
    a.remove_node(8)
    print("hapus 8, maju      :", a.telusur_maju())
    print("hapus 8, mundur    :", a.telusur_mundur())
    a.remove_node(1)
    print("hapus head, mundur :", a.telusur_mundur())
    a.remove_node(15)
    print("hapus tail, maju   :", a.telusur_maju())
    print("hapus 99 (tak ada) :", a.remove_node(99))

maju               : [1, 4, 8, 15]
mundur             : [15, 8, 4, 1]
hapus 8, maju      : [1, 4, 15]
hapus 8, mundur    : [15, 4, 1]
hapus head, mundur : [15, 4]
hapus tail, maju   : [4]
hapus 99 (tak ada) : False

Cara kerja remove_node patut diikuti baris demi baris, karena di situlah empat tautan itu terlihat. Node sebelum target memperbarui tautan majunya, node sesudah target memperbarui tautan mundurnya, dan kedua pemeriksaan is not None menjaga kasus target di ujung agar head atau tail ikut dipindahkan. Pada versi tunggal, setengah pekerjaan itu tidak ada karena tautan mundur memang tidak dimiliki.

Kasus list kosong diawali lewat pemeriksaan self.tail is None pada append dan self.head is None pada append_left, dan keduanya menetapkan head serta tail sekaligus. Tanpa pemeriksaan itu, node pertama membawa tautan yang menggantung. Begitu list berisi satu node, kedua pointer menunjuk node yang sama, dan memang demikian seharusnya.

Deque bawaan sebagai pembanding#

Python menyediakan collections.deque, yaitu antrian ujung ganda yang operasinya di kedua ujung berbiaya $O(1)$. Dibalik layar, deque memakai blok-blok memori yang terhubung dua arah, bukan rantai node murni, tetapi perilakunya mengikuti semangat doubly linked list. Demo berikut memakai deque untuk beberapa tugas ringan yang masuk dari dua ujung berlawanan.

from collections import deque

tugas = deque()
tugas.append("cetak")
tugas.append("arsip")
tugas.appendleft("uji")
print("isi deque   :", list(tugas))
print("ambil kiri  :", tugas.popleft())
print("ambil kanan :", tugas.pop())
print("sisa deque  :", list(tugas))

isi deque   : ['uji', 'cetak', 'arsip']
ambil kiri  : uji
ambil kanan : arsip
sisa deque  : ['cetak']

Metode append dan pop bekerja di ujung kanan, sedangkan appendleft dan popleft bekerja di ujung kiri, dan semuanya berbiaya $O(1)$. Untuk kebutuhan nyata, deque bawaan lebih cepat dan lebih teruji daripada doubly linked list buatan sendiri, sehingga versi buatan sendiri terutama bernilai untuk memahami mekanismenya. Perilaku deque yang lebih rinci dibahas pada modul stack dan antrian.

Pemilihannya pada akhirnya bergantung kebutuhan, bukan kebiasaan. Bila yang dibutuhkan hanya operasi dua ujung, deque bawaan dipilih, sedangkan bila tautan antar node perlu diakses dan diubah sendiri, implementasi dari nol tetap dibuat. Keduanya tidak saling menggantikan karena tujuan belajar dan tujuan produksi memang berbeda.

Kesalahan umum#

Setiap butir berikut bersumber dari satu akar yang sama, yaitu dua arah tautan yang dirawat secara tidak lengkap. Gejalanya sering baru terlihat saat penelusuran mundur, karena jalur inilah yang paling jarang diuji. Sertakan telusur mundur pada setiap pengujian list ganda. Membaca empat tautan pada remove_node sambil menggambar panahnya adalah cara tercepat memahami polanya, dan setelah polanya menempel, pemeriksaannya menjadi rutinitasan yang ringan sebelum kode dijalankan.

1. Lupa memperbarui tail saat menghapus node terakhir. Tautan antar node sudah benar, tetapi tail masih menunjuk node yang sudah lepas. Metode remove_node menangani lewat pemeriksaan kini.next is not None.
2. Lupa mengatur prev node tetangga. Tautan maju saja membuat penelusuran mundur mendarat di node lama atau null. Empat penulisan tautan pada remove_node adalah paket lengkapnya.
3. Mengira deque mengekspos node internalnya. Deque hanya menawarkan operasi ujung tanpa akses ke tautan prev dan next. Struktur yang membutuhkan tautan eksplisit tetap harus dibangun sendiri.

Ringkasan#

• Node doubly linked list menyimpan data, prev, dan next, dengan null pada kedua ujungnya.
• Telusur mundur dan hapus node terakhir menjadi $O(1)$ berkat pointer tail dan tautan prev.
• Harganya satu tautan ekstra per node dan dua arah tautan yang harus dirawat pada setiap operasi.
• Untuk kebutuhan nyata, collections.deque memberikan perilaku dua ujung yang sama dengan implementasi yang lebih teruji.

Referensi#

• Doubly linked list — Wikipedia — penjelasan node dua arah beserta biaya operasinya.
• Data Structures — Python Software Foundation — dokumentasi collections.deque yang menjadi pembanding pada topik ini.
• LinkedList (Java Platform SE 8) — Oracle — contoh doubly linked list bawaan pada bahasa lain.