Penelusuran dan penyisipan

Menyisipkan dan menghapus node pada linked list adalah pekerjaan merapikan tautan, dan hampir semua kekeliruannya berasal dari tautan yang hilang atau urutan merapikan yang salah. Topik ini melatih disiplin pointer untuk kedua operasi tersebut, lengkap dengan diagram urutan re-link yang benar, yakni penataan ulang tautan. Di bagian akhir, trik dummy head, yakni node pembuka tanpa data yang tidak dihitung sebagai isi list, dipakai untuk menghilangkan kasus khusus sisip dan hapus di posisi paling depan.

Disiplin pointer, jangan sampai ada yang terlepas#

Setiap node hanya dapat dicapai lewat tautan dari node di depannya, sehingga satu tautan yang tertimpa memutus seluruh bagian di belakangnya. Kekeliruan klasik terjadi saat menyisipkan di tengah, yaitu menulis kini.next = baru lebih dulu, padahal sisa list hanya tersimpan di kini.next. Setelah posisi itu ditimpa, alamat node-node sesudah kini tidak dimiliki siapa pun lagi, dan list diam-diam terpotong tanpa error apa pun.

# tidak-dijalankan
# sisa list setelah kini hanya tersimpan di kini.next, jangan ditimpa lebih dulu
kini.next = baru
baru.next = kini.next      # yang terbaca malah node baru, bukan sisa list
# akibatnya seluruh node di belakang kini terlepas dan tidak bisa dijangkau

Potongan di atas sengaja tidak dijalankan karena hasilnya list yang terpotong. Aturan penyelamatnya sederhana, yaitu menyimpan alamat yang akan hilang sebelum menimpanya. Kebiasaan yang tumbuh dari aturan itu adalah menggambar dua node beserta panahnya di kertas sebelum menulis baris re-link, persis seperti diagram pada bagian berikutnya.

Akibat tautan yang hilang sifatnya senyap, jauh dari akses indeks di luar batas yang langsung menghentikan program. List yang terpotong tetap tercetak normal dari head, tetapi datanya tinggal separuh. Karena itu pemeriksaan utamanya berupa membandingkan panjang list sebelum dan sesudah operasi, bukan menunggu pesan error.

Urutan re-link yang benar#

Penyisipan node baru di antara kini dan node sesudahnya hanya membuat dua tautan baru, tetapi urutannya menentukan segalanya. Langkah pertama mengarahkan baru.next ke node sesudah kini, sehingga sisa list sudah aman tersimpan. Langkah kedua baru mengarahkan kini.next ke baru, yang memutus tautan lama sekaligus menyelesaikan penyisipan.

Diagram berikut memperlihatkan kedua langkah itu beserta tautan lama yang akan diputus. Angka 1 dan 2 menandai urutan pembuatan tautannya.

Menghapus node memakai disiplin yang sama dengan satu tautan saja. Node sebelum target, yang pada kode nantinya bernama sebelum, mengambil alih tautan target dengan sebelum.next = kini.next, dan sisa list di belakang target tidak pernah hilang karena tidak ada yang ditimpa sebelum dibaca. Tidak ada data yang digeser, hanya satu penulisan tautan, sehingga penghapusan setelah posisi yang diketahui berbiaya $O(1)$.

Dummy head, kasus khusus yang menghilang#

Menyisipkan atau menghapus node di posisi paling depan selalu butuh perlakuan khusus pada list biasa, karena head adalah satu-satunya pintu masuk dan harus ikut diperbarui. Trik dummy head menghapus dua kasus khusus itu sekaligus, karena penelusuran dimulai dari node pembuka alih-alih dari head. Dengan begitu, posisi sebelum node pertama selalu tersedia dan tidak ada operasi yang perlu menyentuh head secara langsung.

Head yang nyata menjadi dummy.next, dan node pembukanya hidup sepanjang list itu ada dengan harga hanya satu node tambahan. Pola ini juga menjadi bahan dasar banyak soal pada judge daring, yakni layanan penilai kode otomatis, terutama soal yang hasil akhirnya berupa head baru. Karena head hasil tidak diketahui sejak awal, node pembuka menampung sementara posisi itu tanpa percabangan tambahan.

Demo: sisip pada posisi ke-k dan hapus berdasar nilai#

Berkas berikut memuat kelas ListDummy dengan dua operasi yang bekerja di atas dummy head. Metode sisip_pada(k, data) berjalan k langkah dari node pembuka sehingga node baru menempati posisi ke-k, sedangkan hapus_nilai(nilai) berjalan sambil mengawasi sebelum.next.data agar berhenti tepat sebelum target. Keduanya memakai urutan re-link dari bagian sebelumnya.

"""Penyisipan pada posisi ke-k dan penghapusan berdasar nilai dengan dummy head."""


class Node:
    """Satu node menyimpan data dan tautan next menuju node sesudahnya."""

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


class ListDummy:
    """Linked list dengan dummy head yang tidak pernah menyimpan data."""

    def __init__(self):
        self.dummy = Node()      # sentinel: selalu ada, tanpa data

    def sisip_pada(self, k, data):
        """Sisipkan node baru sehingga menempati posisi ke-k (mulai dari 0)."""
        sebelum = self.dummy
        for _ in range(k):
            sebelum = sebelum.next
        baru = Node(data)
        baru.next = sebelum.next   # sisa list disimpan lebih dulu
        sebelum.next = baru        # baru disambungkan setelahnya
        return

    def hapus_nilai(self, nilai):
        """Hapus node pertama yang datanya sama, tanpa kasus khusus di head."""
        sebelum = self.dummy
        while sebelum.next is not None and sebelum.next.data != nilai:
            sebelum = sebelum.next
        if sebelum.next is not None:
            sebelum.next = sebelum.next.next
        return

    def __str__(self):
        bagian = []
        kini = self.dummy.next
        while kini is not None:
            bagian.append(str(kini.data))
            kini = kini.next
        if not bagian:
            return "(kosong)"
        return " -> ".join(bagian)


if __name__ == "__main__":
    a = ListDummy()
    a.sisip_pada(0, 5)
    a.sisip_pada(1, 9)
    a.sisip_pada(1, 7)
    print("list sekarang       :", a)
    a.hapus_nilai(9)
    print("hapus 9             :", a)
    a.hapus_nilai(5)
    print("hapus 5 di head     :", a)
    a.hapus_nilai(99)
    print("hapus 99 (tak ada)  :", a)
    a.sisip_pada(0, 2)
    print("sisip 2 di posisi 0 :", a)

list sekarang       : 5 -> 7 -> 9
hapus 9             : 5 -> 7
hapus 5 di head     : 7
hapus 99 (tak ada)  : 7
sisip 2 di posisi 0 : 2 -> 7

Perhatikan pemanggilan sisip_pada(0, 2) pada baris terakhir demo. Nilai k sama dengan 0 membuat perulangan range(k) tidak berjalan sama sekali, sehingga sebelum tetap berada di node pembuka dan node baru otomatis menjadi head baru. Pada versi tanpa dummy, baris itu adalah kasus khusus yang butuh percabangan tersendiri, dan di sinilah trik dummy head terasa manfaatnya.

Pemanggilan hapus_nilai(99) menunjukkan perilaku yang aman ketika nilai tidak ditemukan, yaitu perulangan berhenti di ujung tanpa mengubah apa pun. Kondisi sebelum.next is not None diperiksa lebih dulu, sehingga data milik node null tidak pernah diakses. Dua sifat itu membuat kedua metode aman dipanggil pada list kosong sekalipun.

Kesalahan umum#

Kesalahan pada topik ini jarang berupa sintaks, melainkan urutan baris yang tampak benar tetapi salah jalannya. Ketiga butir berikut lahir dari kekeliruan yang paling sering dijumpai saat menyisipkan dan menghapus node. Ujilah dengan list berisi satu node, karena di sanalah kasus tepi tersembunyi. Pesan error yang muncul biasanya menunjuk posisi barisnya, bukan urutan tautan yang salah.

1. Menimpa kini.next sebelum sisa list disimpan. Urutan baru.next = kini.next lalu kini.next = baru wajib dipatuhi, dan urutan terbaliknya memotong list tanpa error. Menggambar panahnya di kertas lebih cepat daripada menelusuri perilakunya berulang kali.
2. Menganggap node pembuka sebagai bagian dari data. Dummy head tidak menyimpan data dan tidak dihitung, sehingga tampilan isi list harus dimulai dari dummy.next. Mencetak node pembuka langsung hanya memunculkan node kosong yang membingungkan.
3. Berhenti di node target alih-alih node sebelumnya. Penghapusan membutuhkan node sebelum target, sehingga perulangannya mengawasi sebelum.next.data dan bukan sebelum.data. Terlewat, tautan penggantinya tidak bisa ditulis.

Ringkasan#

• Penyisipan di antara dua node menulis baru.next lebih dulu, baru kini.next, agar sisa list tidak terlepas.
• Penghapusan menyerahkan tautan target kepada node sebelumnya dengan satu penulisan tautan berbiaya $O(1)$.
• Dummy head menghilangkan kasus khusus sisip dan hapus di depan karena posisi sebelum head selalu tersedia.
• Demo sisip_pada(0, ...) bekerja tanpa percabangan karena perulangan k langkah diam saja di node pembuka.

Referensi#

• Linked list — Wikipedia — urutan operasi penyisipan dan penghapusan beserta jebakannya.
• Data Structures — Python Software Foundation — dokumentasi list Python sebagai pembanding operasi sisip bawaan.
• VisuAlgo — visualisasi langkah demi langkah penyisipan dan penghapusan node.