Linked list tunggal

Struktur node dan implementasi singly linked list dari nol pada Python dan Java.

Daftar isi

Linked list menyimpan setiap elemen di dalam sebuah node yang berisi data sekaligus tautan menuju node berikutnya, sehingga rantainya dapat tumbuh dan menyusut tanpa menggeser elemen lain. Topik ini membahas anatomi node, cara head bekerja sebagai satu-satunya pintu masuk, dan perbandingan biayanya dengan array. Setelah konsepnya beres, satu singly linked list, yaitu list bertaut satu arah, dibangun dari nol pada Python dan Java, lengkap dengan operasi append, prepend, search, dan delete beserta keluaran aslinya.

Node, next, dan head#

Sebuah node, yakni satu simpul penyimpan tunggal, memuat dua bagian: data yang hendak disimpan dan next, yaitu petunjuk menuju node sesudahnya. Node paling belakang menuliskan next dengan nilai null, sehingga null menjadi penanda bahwa rantai sudah habis. Satu-satunya cara memasuki rantai adalah lewat head, yaitu petunjuk menuju node pertama. Karena setiap node hanya mengenali tetangga sesudahnya, tidak ada jalur lain menuju node-node yang berada di belakang head. Hilangnya head berarti hilangnya seluruh list.

Diagram berikut menunjukkan rantai tiga node berisi 3, 7, dan 11. Panah keluar dari bagian next setiap node, lalu rantainya berakhir di null. Perhatikan bahwa alamat ketiga node boleh tersebar di memori, karena penyatunya adalah tautan next dan bukan letak memorinya.

Rantai tiga node pada singly linked list, dari head menuju null

Membaca elemen kelima dari list berarti berjalan empat langkah dari head, karena tidak ada rumus alamat seperti pada array. Perjalanan berurutan inilah sumber biaya akses $O(n)$ yang dibedah pada bagian berikutnya. Di sisi lain, sifat rantai yang longgar justru membuat penyisipan di depan menjadi sangat murah.

Perbandingan biaya dengan array#

Array menaruh semua elemen pada blok memori berurutan, sehingga alamat elemen ke-i dapat dihitung langsung dari indeksnya dan aksesnya berbiaya $O(1)$ . Linked list tidak punya kemewahan itu, karena satu-satunya jalan menuju elemen ke-i adalah menelusuri tautan dari head sebanyak $O(n)$ langkah. Sebaliknya, menyisipkan node baru di depan hanya merapikan dua tautan dan berbiaya $O(1)$ , sedangkan array harus menggeser seluruh elemen lama yang berbiaya $O(n)$ . Perbandingan lengkapnya dirangkum pada tabel berikut.

Operasi	Array	Singly linked list
Akses elemen ke-i	$O(1)$	$O(n)$
Mencari sebuah nilai	$O(n)$	$O(n)$
Menyisipkan di depan	$O(n)$	$O(1)$
Menghapus di depan	$O(n)$	$O(1)$
Menambah di ujung	$O(1)$ bila kapasitas tersisa	$O(n)$ tanpa pointer tail

Baris terakhir tabel menunjukkan titik lemah yang sering mengejutkan, yaitu append pada implementasi tanpa pointer tail, yakni petunjuk tambahan menuju node terakhir. Tanpa tail, penambahan di ujung harus menelusuri seluruh rantai sehingga biayanya $O(n)$ . Dengan tail, operasi itu turun menjadi $O(1)$ , tetapi satu tautan lagi harus dirawat setiap kali list berubah. Harga lain yang selalu dibayar adalah satu ruang memori ekstra per node untuk menyimpan next. Sementara itu, array lebih ramah cache, yakni memori cepat yang menguntungkan data yang berdekatan.

Implementasi dari nol pada Python#

Berkas berikut memuat kelas Node dan kelas LinkedList yang lengkap dengan empat operasinya. Metode append berjalan sampai menemukan node yang next-nya null, prepend hanya merapikan satu tautan, search menelusuri sambil membandingkan data, dan delete berdiri satu langkah di belakang target sebelum melewatinya. Metode __str__ menghabiskan rantai dari head sampai null sehingga isi list dapat dicetak sebagai teks.

python singly.py

"""Singly linked list dari nol: kelas Node, kelas LinkedList, dan demo singkat."""


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

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


class LinkedList:
    """Singly linked list dengan head sebagai satu-satunya pintu masuk."""

    def __init__(self):
        self.head = None

    def prepend(self, data):
        """Sisipkan node baru di depan, biayanya O(1)."""
        baru = Node(data)
        baru.next = self.head
        self.head = baru

    def append(self, data):
        """Tambahkan node baru di ujung, biayanya O(n) karena menelusuri."""
        baru = Node(data)
        if self.head is None:
            self.head = baru
            return
        kini = self.head
        while kini.next is not None:
            kini = kini.next
        kini.next = baru

    def search(self, nilai):
        """Kembalikan nilai yang dicari bila ada, atau None bila tidak ada."""
        kini = self.head
        while kini is not None:
            if kini.data == nilai:
                return kini.data
            kini = kini.next
        return None

    def delete(self, nilai):
        """Hapus node pertama yang bernilai sama, diam bila tidak ada."""
        if self.head is None:
            return
        if self.head.data == nilai:
            self.head = self.head.next
            return
        sebelum = self.head
        while sebelum.next is not None:
            if sebelum.next.data == nilai:
                sebelum.next = sebelum.next.next
                return
            sebelum = sebelum.next

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


if __name__ == "__main__":
    a = LinkedList()
    a.append(3)
    a.append(7)
    a.append(11)
    print("append 3, 7, 11 :", a)
    a.prepend(1)
    print("prepend 1       :", a)
    print("cari 7          :", a.search(7))
    print("cari 99         :", a.search(99))
    a.delete(7)
    print("hapus 7         :", a)
    a.delete(1)
    print("hapus 1 di head :", a)

text Keluaran

append 3, 7, 11 : 3 -> 7 -> 11 -> None
prepend 1       : 1 -> 3 -> 7 -> 11 -> None
cari 7          : 7
cari 99         : None
hapus 7         : 1 -> 3 -> 11 -> None
hapus 1 di head : 3 -> 11 -> None

Cara kerja delete patut dicermati, karena penghapusan pada singly linked list selalu membutuhkan node sebelum target agar tautan dapat dipindahkan. Itulah alasan perulangannya mengawasi sebelum.next, bukan sebelum. Karena perulangan hanya mengenali target lewat pendahulunya, kasus penghapusan di head ditangani terpisah di awal metode. Seluruh operasi hanya memindahkan tautan, tidak pernah menyalin atau menggeser data seperti pada array.

Versi Java dan cara menjalankannya#

Versi Java meniru struktur yang sama, dengan kelas Node bersarang di dalam kelas SinglyList dan metode-metode yang setara. Perbedaannya ada pada tipe, karena data dideklarasikan sebagai int, hasil search berupa boolean, dan penulisan isi list memakai StringBuilder di dalam toString. Simpan berkasnya sebagai SinglyList.java, lalu jalankan langsung dengan perintah java SinglyList.java yang didukung sejak Java 11 tanpa tahap kompilasi manual.

java SinglyList.java

public class SinglyList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    void prepend(int data) {
        Node baru = new Node(data);
        baru.next = head;
        head = baru;
    }

    void append(int data) {
        Node baru = new Node(data);
        if (head == null) {
            head = baru;
            return;
        }
        Node kini = head;
        while (kini.next != null) {
            kini = kini.next;
        }
        kini.next = baru;
    }

    boolean search(int nilai) {
        Node kini = head;
        while (kini != null) {
            if (kini.data == nilai) {
                return true;
            }
            kini = kini.next;
        }
        return false;
    }

    void delete(int nilai) {
        if (head == null) {
            return;
        }
        if (head.data == nilai) {
            head = head.next;
            return;
        }
        Node sebelum = head;
        while (sebelum.next != null) {
            if (sebelum.next.data == nilai) {
                sebelum.next = sebelum.next.next;
                return;
            }
            sebelum = sebelum.next;
        }
    }

    @Override
    public String toString() {
        if (head == null) {
            return "null";
        }
        StringBuilder teks = new StringBuilder();
        Node kini = head;
        while (kini != null) {
            teks.append(kini.data);
            teks.append(" -> ");
            kini = kini.next;
        }
        teks.append("null");
        return teks.toString();
    }

    public static void main(String[] args) {
        SinglyList a = new SinglyList();
        a.append(3);
        a.append(7);
        a.append(11);
        System.out.println("append 3, 7, 11 : " + a);
        a.prepend(1);
        System.out.println("prepend 1       : " + a);
        System.out.println("cari 7          : " + a.search(7));
        System.out.println("cari 99         : " + a.search(99));
        a.delete(7);
        System.out.println("hapus 7         : " + a);
        a.delete(1);
        System.out.println("hapus 1 di head : " + a);
    }
}

text Keluaran

append 3, 7, 11 : 3 -> 7 -> 11 -> null
prepend 1       : 1 -> 3 -> 7 -> 11 -> null
cari 7          : true
cari 99         : false
hapus 7         : 1 -> 3 -> 11 -> null
hapus 1 di head : 3 -> 11 -> null

Keluaran Java hampir identik dengan versi Python, hanya berakhir di null dan menjawab pencarian dengan true atau false. Kedua versi menghitung hal yang sama, sehingga perbedaannya murni gaya bahasa dan bukan mekanisme. Membangunnya dua kali dengan dua bahasa berbeda memaksa mekanisme tautannya dipahami, bukan dihafal dari satu sintaks.

Setiap node pada Java adalah objek yang hidup di heap, yakni area memori yang dipakai untuk objek saat program berjalan, dan null pada next menandai ujung rantai persis seperti None pada Python. Tautan yang diputus pada delete membuat node lama tidak lagi dirujuk, lalu pengelola memori Java membersihkannya di belakang layar. Python mencapai akhir yang sama lewat penghitungan rujukannya, sehingga kedua bahasa tidak menuntut pembersihan manual.

Bentuk bersarang static class Node dipilih agar berkasnya tetap tunggal dan bisa dijalankan langsung tanpa kompilasi terpisah. Demo pada main merakit list pendek lewat beberapa pemanggilan append dan prepend, sedangkan list yang panjang dirakit dengan perulangan yang memanggil append berulang kali. Untuk data selain bilangan bulat, tipe int diganti tipe lain dan logikanya tidak berubah.

Kesalahan umum#

Ketiga kekeliruan berikut paling sering muncul saat list pertama kali dibangun. Semuanya tidak memunculkan pesan yang jelas pada awalnya, sehingga gejalanya baru terasa ketika keluaran meleset atau program berhenti. Menelusurinya dengan mencetak isi list setelah setiap operasi membantu mempersempit letak masalahnya.

Mencampur kondisi berhenti perulangan. Bentuk while kini is not None berjalan sampai null dan cocok untuk pencarian, sedangkan while kini.next is not None berhenti di node terakhir dan cocok untuk append. Tertukar, program memunculkan AttributeError atau NullPointerException ketika null diakses.
Mengira append selalu murah. Tanpa pointer tail, append menelusuri seluruh list dan berbiaya $O(n)$ , jauh dari kesan cukup menempel di ujung. Biayanya hanya turun menjadi $O(1)$ setelah tail disimpan dan dirawat.
Menghapus node tanpa menyiapkan node sebelumnya. Pada singly linked list, tautan hanya bisa dipindahkan oleh node di depan target, sehingga perulangan penghapusan harus berdiri satu langkah di belakangnya dan kasus head ditangani terpisah.

Ringkasan#

Node menyimpan data dan next, dan head menjadi satu-satunya pintu masuk rantai yang berakhir di null.
Akses elemen ke-i menelusuri $O(n)$ tautan, sedangkan array mencapainya dalam $O(1)$ lewat rumus alamat.
Penyisipan dan penghapusan di depan hanya merapikan tautan sehingga berbiaya $O(1)$ , sesuatu yang tidak mampu dilakukan array tanpa menggeser $O(n)$ elemen.
Implementasi Python dan Java di atas memakai mekanisme yang sama, dan versi Java dijalankan langsung lewat java SinglyList.java.

Referensi#

Linked list — Wikipedia — gambaran umum singly dan doubly linked list beserta biaya operasinya.
Data Structures — Python Software Foundation — dokumentasi resmi yang membandingkan list Python dengan struktur lain.
LinkedList (Java Platform SE 8) — Oracle — dokumentasi LinkedList bawaan Java sebagai pembanding versi buatan sendiri.
Algorithms, 4th Edition — Princeton University — bab Stack dan Queue Princeton yang membangun linked list untuk keperluan yang sama.
VisuAlgo — visualisasi interaktif linked list yang memperlihatkan pergerakan tautan.