LinkedList

ArrayList menyimpan elemen berdampingan dalam satu array, sehingga menyisip elemen di tengah memaksa penggeseran massal. LinkedList menawarkan jalan berbeda: setiap elemen dibungkus menjadi node yang saling terhubung seperti gerbong rangkaian kereta, sehingga menyisip atau mencabut node “cukup dengan menyambung ulang tautan” di sekitarnya. Implementasi ini juga satu-satunya class standar yang memenuhi dua kontrak besar sekaligus — List dan Deque — sehingga LinkedList bisa dibaca sebagai list berindeks sekaligus antrean dua arah. Pada Chapter ini kita bedah rantai node tersebut, membuktikan perilaku penelusuran berindeks, lalu melihat skenario mana yang benar-benar menguntungkan LinkedList.

Struktur Rantai Node #

Secara internal, java.util.LinkedList memakai doubly-linked list: setiap node menyimpan tiga hal — referensi elemen, referensi node berikutnya, dan referensi node sebelumnya. Object LinkedList sendiri hanya menyimpan dua penunjuk penting: first (node kepala) dan last (node ekor), plus sebuah penghitung size. Menyisip di depan berarti membuat node baru, mengarahkan first ke node baru tersebut, dan menyambungkan tautan balik node lama — sedikit operasi tetap berapa pun panjang rantainya. Begitu pula penyisipan di belakang lewat penunjuk last; keduanya O(1) tanpa penyalinan atau penggeseran elemen.

Biaya muncul ketika kita memakai fitur berindeks dari List. Method get(indeks) pada LinkedList harus berjalan dari kepala (atau dari ekor, mana yang lebih dekat) node demi node sampai posisi yang diminta. Berbeda dengan array yang melompat langsung ke alamat slot, penelusuran rantai membesar seiring indeks — inilah O(n).

Menelusuri Rantai Menuju Indeks #

Daripada membayangkan penelusuran secara abstrak, kita bangun dulu rantai node mini milik kita sendiri. Lima node dibuat dan disambungkan satu per satu, lalu program “berjalan” menuju indeks 3 sambil mencatat setiap langkahnya:

import java.util.*;

public class RantaiNode {
    // Simulasi node berantai: setiap node tahu tetangganya saja.
    static class NodeSederhana {
        String nilai;
        NodeSederhana berikutnya;

        NodeSederhana(String nilai) {
            this.nilai = nilai;
        }
    }

    public static void main(String[] args) {
        NodeSederhana berkas0 = new NodeSederhana("Beras");
        NodeSederhana berkas1 = new NodeSederhana("Telur");
        NodeSederhana berkas2 = new NodeSederhana("Gula");
        NodeSederhana berkas3 = new NodeSederhana("Kopi");
        NodeSederhana berkas4 = new NodeSederhana("Teh");
        berkas0.berikutnya = berkas1;
        berkas1.berikutnya = berkas2;
        berkas2.berikutnya = berkas3;
        berkas3.berikutnya = berkas4;

        // Mengambil indeks 3 berarti berjalan 3 langkah dari kepala.
        int target = 3;
        NodeSederhana sekarang = berkas0;
        for (int langkah = 1; langkah <= target; langkah++) {
            sekarang = sekarang.berikutnya;
            System.out.println("langkah " + langkah + ": sampai di " + sekarang.nilai);
        }
        System.out.println("Elemen indeks " + target + " adalah " + sekarang.nilai);
    }
}

Output yang Dihasilkan:

langkah 1: sampai di Telur
langkah 2: sampai di Gula
langkah 3: sampai di Kopi
Elemen indeks 3 adalah Kopi

Mari kita bedah baris-baris pentingnya:

1. Baris 5-12 (static class NodeSederhana): satu node hanya mengenal dua hal — nilai yang dibawanya dan node berikutnya. Mengetahui tetangga itulah satu-satunya cara berpindah dalam rantai.
2. Baris 16-24 (berkas0 hingga berkas4 beserta penyambungannya): lima node dibuat terpisah lalu disambungkan membentuk rantai Beras → Telur → Gula → Kopi → Teh. Tidak ada “lompatan” ke berkas3 dari luar — satu-satunya jalan adalah menyusuri tautan.
3. Baris 27-33 (loop penelusuran): untuk mencapai indeks 3, program melakukan tepat 3 langkah: Telur, Gula, lalu Kopi. Jumlah langkah tumbuh linier terhadap indeks — persis perilaku LinkedList.get(indeks) di pustaka standar.
4. Implikasi: mengambil get(0) hanya 0 langkah, tetapi get(999_999) menuntut hampir sejuta langkah. ArrayList menyelesaikan keduanya dalam satu lompatan aritmetika alamat.

Satu Class Dua Peran #

Karena LinkedList mengimplementasikan Deque, method-method ujung seperti addFirst, addLast, pollFirst, dan pollLast tersedia langsung — semuanya O(1). Program berikut memakai daftar tugas rumah tangga untuk memperagakan peran ganda tersebut:

import java.util.*;

public class TugasLinkedList {
    public static void main(String[] args) {
        // LinkedList sekaligus memenuhi kontrak List dan Deque.
        LinkedList<String> tugas = new LinkedList<>();
        tugas.addLast("Cuci piring");
        tugas.addLast("Belanja");
        tugas.addFirst("Sarapan");
        System.out.println("Isi        : " + tugas);

        System.out.println("getFirst() : " + tugas.getFirst());
        System.out.println("getLast()  : " + tugas.getLast());

        System.out.println("pollFirst(): " + tugas.pollFirst());
        System.out.println("pollLast() : " + tugas.pollLast());
        System.out.println("Sisa       : " + tugas);

        // Akses berindeks tetap tersedia, tetapi menelusuri rantai node.
        System.out.println("get(0)     : " + tugas.get(0));
    }
}

Output yang Dihasilkan:

Isi        : [Sarapan, Cuci piring, Belanja]
getFirst() : Sarapan
getLast()  : Belanja
pollFirst(): Sarapan
pollLast() : Belanja
Sisa       : [Cuci piring]
get(0)     : Cuci piring

Poin bedahnya:

1. Baris 7-9: addLast menempel di ekor dan addFirst menyisip di kepala. Hasil cetakan [Sarapan, Cuci piring, Belanja] menunjukkan Sarapan berada paling depan sesuai posisi penyisipannya.
2. Baris 12-13 (getFirst/getLast): membaca kedua ujung langsung dari penunjuk first/last — tidak ada penelusuran.
3. Baris 15-16 (pollFirst/pollLast): mengambil dan menghapus elemen dari ujung masing-masing; kedua operasi menyambung ulang maksimal dua tautan, tetap O(1).
4. Baris 19 (get(0)): akses berindeks tetap sah karena LinkedList adalah List — hanya saja jalurnya menelusuri rantai dari ujung terdekat.

Kapan LinkedList Unggul #

Tabel berikut membandingkan kedua implementasi List pada operasi yang paling sering dipakai:

Dari tabel tersebut terlihat pola pemilihan yang jujur. LinkedList unggul ketika operasi dominan aplikasi adalah penyisipan dan penghapusan di kedua ujung — misalnya antrean layanan pelanggan yang terus menerima dan mengeluarkan orang. Untuk akses acak berindeks, iterasi penuh, atau penghematan memori, ArrayList hampir selalu menang. Perlu dicatat juga bahwa untuk kebutuhan antrean dua ujung murni, ArrayDeque (Chapter Deque Interface) biasanya lebih cepat dan lebih hemat memori daripada LinkedList.

Kita kini sudah menyelesaikan seluruh cabang List. Berikutnya kita berpindah ke cabang kedua hierarki: Set, kontrak yang menolak duplikat dan mengubah cara kita berpikir tentang keunikan data.

Referensi #

• Java API Specification: java.util.LinkedList
• Java API Specification: java.util.Deque
• Dev.java: The Java Collections Framework

import java.util.*;

public class RantaiNode {
    // Simulasi node berantai: setiap node tahu tetangganya saja.
    static class NodeSederhana {
        String nilai;
        NodeSederhana berikutnya;

        NodeSederhana(String nilai) {
            this.nilai = nilai;
        }
    }

    public static void main(String[] args) {
        NodeSederhana berkas0 = new NodeSederhana("Beras");
        NodeSederhana berkas1 = new NodeSederhana("Telur");
        NodeSederhana berkas2 = new NodeSederhana("Gula");
        NodeSederhana berkas3 = new NodeSederhana("Kopi");
        NodeSederhana berkas4 = new NodeSederhana("Teh");
        berkas0.berikutnya = berkas1;
        berkas1.berikutnya = berkas2;
        berkas2.berikutnya = berkas3;
        berkas3.berikutnya = berkas4;

        // Mengambil indeks 3 berarti berjalan 3 langkah dari kepala.
        int target = 3;
        NodeSederhana sekarang = berkas0;
        for (int langkah = 1; langkah <= target; langkah++) {
            sekarang = sekarang.berikutnya;
            System.out.println("langkah " + langkah + ": sampai di " + sekarang.nilai);
        }
        System.out.println("Elemen indeks " + target + " adalah " + sekarang.nilai);
    }
}

import java.util.*;

public class TugasLinkedList {
    public static void main(String[] args) {
        // LinkedList sekaligus memenuhi kontrak List dan Deque.
        LinkedList<String> tugas = new LinkedList<>();
        tugas.addLast("Cuci piring");
        tugas.addLast("Belanja");
        tugas.addFirst("Sarapan");
        System.out.println("Isi        : " + tugas);

        System.out.println("getFirst() : " + tugas.getFirst());
        System.out.println("getLast()  : " + tugas.getLast());

        System.out.println("pollFirst(): " + tugas.pollFirst());
        System.out.println("pollLast() : " + tugas.pollLast());
        System.out.println("Sisa       : " + tugas);

        // Akses berindeks tetap tersedia, tetapi menelusuri rantai node.
        System.out.println("get(0)     : " + tugas.get(0));
    }
}