Setelah bisa membaca kompleksitas, kita masuk ke struktur data yang paling mendasar: cara menyimpan barisan data. Java menyediakan ArrayList dan LinkedList di pustaka java.util, tetapi keduanya sebenarnya pembungkus dari dua gagasan yang berbeda: blok memori berurutan dan rantai node yang saling bertaut. Memahami mekanisme di balik keduanya menentukan apakah kita memilih struktur yang tepat untuk soal di tangan. Chapter ini membangun linked list secara manual dari class Node, menghitung biaya tiap operasi dengan penghitung langkah, lalu menjelaskan mengapa array dalam praktik sering menang meski di atas kertas kompleksitasnya sama.

Array Menyimpan Berurutan di Memori #

Ketika new int[1000] dieksekusi, JVM mengalokasikan satu blok memori utuh untuk 1000 bilangan int yang berdempetan. Karena setiap int memakai 4 byte dan posisinya berurutan, alamat elemen ke-i bisa dihitung langsung: alamat dasar ditambah i × 4. Inilah mesin di balik akses array[i] yang berbiaya O(1) — JVM tidak menelusuri apa pun, melainkan menghitung satu alamat lalu membacanya. Konsekuensi pembelian desain ini: menyisipkan elemen baru di tengah memaksa semua elemen di belakangnya bergeser, dan ukuran alokasi awal tidak bisa ditambah seenaknya (ArrayList mengatasi hal terakhir dengan mengalokasikan ulang ke array yang lebih besar saat kapasitas habis).

Linked List Menyimpan Node Bertaut #

Linked list memilih jalan sebaliknya: data boleh tersebar di mana pun di heap, asal setiap node menyimpan tautan ke node berikutnya. Kita bangun versi manualnya dengan class Node berisi dua field — data dan next — lalu method tambahBelakang, ambil, dan hapus yang menelusuri tautan satu per satu:

java LinkedListManual.java 
public class LinkedListManual {

    // Node: satu kotak data plus satu tautan ke node berikutnya.
    static class Node {
        String data;
        Node next;

        Node(String data) {
            this.data = data;
        }
    }

    private Node kepala;
    private int ukuran;

    // Penghitung node yang dikunjungi: deterministik, bukan pengukuran waktu.
    static long kunjungan;

    public static void main(String[] args) {
        LinkedListManual list = new LinkedListManual();
        list.tambahBelakang("Budi");
        list.tambahBelakang("Siti");
        list.tambahBelakang("Dewi");
        list.tambahBelakang("Andi");
        list.tambahBelakang("Rina");

        System.out.print("Isi list: ");
        cetak(list.kepala);
        System.out.println("Ukuran  : " + list.ukuran);

        System.out.println();
        System.out.println("Akses per indeks (jumlah node yang dikunjungi):");
        for (int indeks : new int[] {0, 2, 4}) {
            kunjungan = 0;
            String nilai = list.ambil(indeks);
            System.out.printf("  ambil(%d) -> %s, node dikunjungi: %d%n",
                    indeks, nilai, kunjungan);
        }

        System.out.println();
        System.out.println("Hapus node di tengah:");
        kunjungan = 0;
        boolean terhapus = list.hapus("Dewi");
        System.out.printf("  hapus Dewi -> %s, node dikunjungi: %d%n",
                terhapus ? "berhasil" : "gagal", kunjungan);
        System.out.print("Isi list: ");
        cetak(list.kepala);
        System.out.println("Ukuran  : " + list.ukuran);
    }

    void tambahBelakang(String data) {
        Node baru = new Node(data);
        if (kepala == null) {
            kepala = baru;
        } else {
            Node sekarang = kepala;
            while (sekarang.next != null) {
                sekarang = sekarang.next;
            }
            sekarang.next = baru;
        }
        ukuran++;
    }

    String ambil(int indeks) {
        Node sekarang = kepala;
        for (int i = 0; i < indeks; i++) {
            sekarang = sekarang.next;
            kunjungan++;        // satu lompatan tautan
        }
        kunjungan++;            // node tujuan juga dikunjungi
        return sekarang.data;
    }

    boolean hapus(String data) {
        Node sekarang = kepala;
        Node sebelum = null;
        while (sekarang != null) {
            kunjungan++;
            if (sekarang.data.equals(data)) {
                if (sebelum == null) {
                    kepala = sekarang.next;     // node pertama digeser keluar
                } else {
                    sebelum.next = sekarang.next; // tautan dilewati satu node
                }
                ukuran--;
                return true;
            }
            sebelum = sekarang;
            sekarang = sekarang.next;
        }
        return false;
    }

    static void cetak(Node kepala) {
        Node sekarang = kepala;
        StringBuilder sb = new StringBuilder();
        while (sekarang != null) {
            sb.append(sekarang.data);
            if (sekarang.next != null) {
                sb.append(" -> ");
            }
            sekarang = sekarang.next;
        }
        System.out.println(sb);
    }
}

Output yang Dihasilkan:

text 
Isi list: Budi -> Siti -> Dewi -> Andi -> Rina
Ukuran  : 5

Akses per indeks (jumlah node yang dikunjungi):
  ambil(0) -> Budi, node dikunjungi: 1
  ambil(2) -> Dewi, node dikunjungi: 3
  ambil(4) -> Rina, node dikunjungi: 5

Hapus node di tengah:
  hapus Dewi -> berhasil, node dikunjungi: 3
Isi list: Budi -> Siti -> Andi -> Rina
Ukuran  : 4

Output memperlihatkan pola khas akses linked list: ambil(0) cukup mengunjungi 1 node, ambil(2) mengunjungi 3 node, dan ambil(4) mengunjungi seluruh 5 node. Mari kita bedah bagian intinya:

  1. Baris 4-12 (static class Node): node hanya tahu dua hal — datanya sendiri dan node berikutnya. Field next bernilai null pada node terakhir, itulah penanda ujung rantai.
  2. Baris 51-63 (tambahBelakang): kalau list masih kosong, node baru langsung menjadi kepala. Kalau tidak, method berjalan menyusuri tautan sampai menemukan node yang next-nya null, lalu menambalkan node baru di sana. Tanpa penunjuk ekor (tail), operasi ini O(n); menyimpan tail membuatnya O(1).
  3. Baris 65-73 (ambil): tidak ada perhitungan alamat seperti array. Satu-satunya cara mencapai indeks ke-i adalah mengikuti i kali tautan next, sehingga biayanya O(n).
  4. Baris 75-95 (hapus): dua referensi berjalan berdampingan — sekarang yang diperiksa dan sebelum yang menyimpan node sebelumnya. Ketika data ditemukan, cukup sebelum.next = sekarang.next agar node terhapus dilompati oleh rantai; node yang dilewati menjadi milik garbage collector.

Tabel Biaya Operasi #

Kedua struktur saling mengalahkan di operasi yang berbeda. Tabel berikut merangkum biaya pada kasus umum:

OperasiArrayLinked List
Akses indeks ke-iO(1)O(n)
Sisip/hapus di depanO(n) — semua elemen bergeserO(1) — ubah satu tautan
Sisip/hapus di akhirO(1) amortized (ArrayList)O(1) dengan pointer tail
Sisip di tengah (posisi sudah dipegang)O(n) — geser elemenO(1) — sambung ulang tautan
Pencarian nilaiO(n)O(n)
Jejak memori per elemenrapat, tanpa tautanekstra satu referensi per node

Pola umumnya: operasi yang bermain dengan posisi acak berpihak ke array; operasi yang bermain dengan penyambungan ulang tautan berpihak ke linked list. Program berikut mengadu keduanya pada dua operasi berlawanan dengan penghitung langkah nyata:

java AksesVsPenelusuran.java 
public class AksesVsPenelusuran {

    static class Node {
        int data;
        Node next;

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

    // Penghitung langkah nyata yang dilakukan tiap operasi.
    static long langkah;

    public static void main(String[] args) {
        int n = 1000;

        // Siapkan array dan linked list dengan isi identik: 0..999.
        int[] array = new int[n];
        Node kepala = new Node(0);
        Node ekor = kepala;
        for (int i = 1; i < n; i++) {
            array[i] = i;
            ekor.next = new Node(i);
            ekor = ekor.next;
        }

        System.out.println("n = " + n);
        System.out.println();
        System.out.println("=== Akses satu indeks (jumlah langkah) ===");
        System.out.println("indeks | array | linked list");
        for (int indeks : new int[] {0, 250, 500, 999}) {
            langkah = 0;
            int nilaiArray = aksesArray(array, indeks);
            long dariArray = langkah;

            langkah = 0;
            int nilaiList = aksesList(kepala, indeks);
            long dariList = langkah;

            System.out.printf("%6d | %5d | %12d  (nilai sama: %b)%n",
                    indeks, dariArray, dariList, nilaiArray == nilaiList);
        }

        System.out.println();
        System.out.println("=== Sisip satu nilai di posisi paling depan ===");
        langkah = 0;
        int[] arrayBaru = sisipDepanArray(array, 9999);
        long geserArray = langkah;

        langkah = 0;
        Node kepalaBaru = sisipDepanList(kepala, 9999);
        long tautanList = langkah;

        System.out.println("Array      : " + geserArray + " pergeseran elemen");
        System.out.println("Linked list: " + tautanList + " penugasan tautan");
        System.out.println("Nilai paling depan array      : " + arrayBaru[0]);
        System.out.println("Nilai paling depan linked list: " + kepalaBaru.data);
    }

    static int aksesArray(int[] a, int indeks) {
        langkah++;      // satu perhitungan alamat: alamat dasar + indeks
        return a[indeks];
    }

    static int aksesList(Node kepala, int indeks) {
        Node sekarang = kepala;
        langkah++;      // mengunjungi node kepala
        for (int i = 0; i < indeks; i++) {
            sekarang = sekarang.next;
            langkah++;  // satu lompatan mengikuti tautan
        }
        return sekarang.data;
    }

    static int[] sisipDepanArray(int[] a, int nilai) {
        int[] hasil = new int[a.length + 1];
        hasil[0] = nilai;
        for (int i = 0; i < a.length; i++) {
            langkah++;  // satu elemen bergeser satu posisi ke kanan
            hasil[i + 1] = a[i];
        }
        return hasil;
    }

    static Node sisipDepanList(Node kepala, int nilai) {
        Node baru = new Node(nilai);
        langkah++;      // satu penugasan tautan baru
        baru.next = kepala;
        return baru;
    }
}

Output yang Dihasilkan:

text 
n = 1000

=== Akses satu indeks (jumlah langkah) ===
indeks | array | linked list
     0 |     1 |            1  (nilai sama: true)
   250 |     1 |          251  (nilai sama: true)
   500 |     1 |          501  (nilai sama: true)
   999 |     1 |         1000  (nilai sama: true)

=== Sisip satu nilai di posisi paling depan ===
Array      : 1000 pergeseran elemen
Linked list: 1 penugasan tautan
Nilai paling depan array      : 9999
Nilai paling depan linked list: 9999

Hasilnya seimbang tapi tegas: akses indeks 999 memaksa linked list mengunjungi 1000 node lawan 1 langkah milik array; sebaliknya, sisip di depan memaksa array menggeser 1000 elemen lawan 1 penugasan tautan milik linked list. Method sisipDepanList menyelesaikan pekerjaannya hanya dengan baru.next = kepala — node lama tidak dipindahkan satu pun.

Mengapa Array Sering Menang Praktis #

Tabel di atas menyembunyikan satu faktor perangkat keras: locality of reference. Elemen array berdempetan di memori, sehingga ketika prosesor membaca array[250], cache menarik sekaligus satu cache line berisi tetangga terdekatnya — array[251], array[252], dan seterusnya sudah tersedia. Node linked list tersebar di heap, dan setiap lompatan next bisa mendarat di alamat yang jauh sehingga cache harus diisi ulang. Efek ini membuat penelusuran array O(n) secara nyata jauh lebih cepat daripada penelusuran linked list O(n) pada data besar, karena Big-O menghitung langkah logika, bukan biaya memori per langkah.

Dua struktur berikutnya membatasi cara akses jauh lebih ketat daripada array dan linked list: stack hanya membuka satu pintu di ujung, queue membuka dua pintu yang berbeda arah. Pembatasan yang tampak sebagai kelemahan itu justru sumber kekuatannya.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

AksesVsPenelusuran.java

Unduh berkas
java 
public class AksesVsPenelusuran {

    static class Node {
        int data;
        Node next;

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

    // Penghitung langkah nyata yang dilakukan tiap operasi.
    static long langkah;

    public static void main(String[] args) {
        int n = 1000;

        // Siapkan array dan linked list dengan isi identik: 0..999.
        int[] array = new int[n];
        Node kepala = new Node(0);
        Node ekor = kepala;
        for (int i = 1; i < n; i++) {
            array[i] = i;
            ekor.next = new Node(i);
            ekor = ekor.next;
        }

        System.out.println("n = " + n);
        System.out.println();
        System.out.println("=== Akses satu indeks (jumlah langkah) ===");
        System.out.println("indeks | array | linked list");
        for (int indeks : new int[] {0, 250, 500, 999}) {
            langkah = 0;
            int nilaiArray = aksesArray(array, indeks);
            long dariArray = langkah;

            langkah = 0;
            int nilaiList = aksesList(kepala, indeks);
            long dariList = langkah;

            System.out.printf("%6d | %5d | %12d  (nilai sama: %b)%n",
                    indeks, dariArray, dariList, nilaiArray == nilaiList);
        }

        System.out.println();
        System.out.println("=== Sisip satu nilai di posisi paling depan ===");
        langkah = 0;
        int[] arrayBaru = sisipDepanArray(array, 9999);
        long geserArray = langkah;

        langkah = 0;
        Node kepalaBaru = sisipDepanList(kepala, 9999);
        long tautanList = langkah;

        System.out.println("Array      : " + geserArray + " pergeseran elemen");
        System.out.println("Linked list: " + tautanList + " penugasan tautan");
        System.out.println("Nilai paling depan array      : " + arrayBaru[0]);
        System.out.println("Nilai paling depan linked list: " + kepalaBaru.data);
    }

    static int aksesArray(int[] a, int indeks) {
        langkah++;      // satu perhitungan alamat: alamat dasar + indeks
        return a[indeks];
    }

    static int aksesList(Node kepala, int indeks) {
        Node sekarang = kepala;
        langkah++;      // mengunjungi node kepala
        for (int i = 0; i < indeks; i++) {
            sekarang = sekarang.next;
            langkah++;  // satu lompatan mengikuti tautan
        }
        return sekarang.data;
    }

    static int[] sisipDepanArray(int[] a, int nilai) {
        int[] hasil = new int[a.length + 1];
        hasil[0] = nilai;
        for (int i = 0; i < a.length; i++) {
            langkah++;  // satu elemen bergeser satu posisi ke kanan
            hasil[i + 1] = a[i];
        }
        return hasil;
    }

    static Node sisipDepanList(Node kepala, int nilai) {
        Node baru = new Node(nilai);
        langkah++;      // satu penugasan tautan baru
        baru.next = kepala;
        return baru;
    }
}

LinkedListManual.java

Unduh berkas
java 
public class LinkedListManual {

    // Node: satu kotak data plus satu tautan ke node berikutnya.
    static class Node {
        String data;
        Node next;

        Node(String data) {
            this.data = data;
        }
    }

    private Node kepala;
    private int ukuran;

    // Penghitung node yang dikunjungi: deterministik, bukan pengukuran waktu.
    static long kunjungan;

    public static void main(String[] args) {
        LinkedListManual list = new LinkedListManual();
        list.tambahBelakang("Budi");
        list.tambahBelakang("Siti");
        list.tambahBelakang("Dewi");
        list.tambahBelakang("Andi");
        list.tambahBelakang("Rina");

        System.out.print("Isi list: ");
        cetak(list.kepala);
        System.out.println("Ukuran  : " + list.ukuran);

        System.out.println();
        System.out.println("Akses per indeks (jumlah node yang dikunjungi):");
        for (int indeks : new int[] {0, 2, 4}) {
            kunjungan = 0;
            String nilai = list.ambil(indeks);
            System.out.printf("  ambil(%d) -> %s, node dikunjungi: %d%n",
                    indeks, nilai, kunjungan);
        }

        System.out.println();
        System.out.println("Hapus node di tengah:");
        kunjungan = 0;
        boolean terhapus = list.hapus("Dewi");
        System.out.printf("  hapus Dewi -> %s, node dikunjungi: %d%n",
                terhapus ? "berhasil" : "gagal", kunjungan);
        System.out.print("Isi list: ");
        cetak(list.kepala);
        System.out.println("Ukuran  : " + list.ukuran);
    }

    void tambahBelakang(String data) {
        Node baru = new Node(data);
        if (kepala == null) {
            kepala = baru;
        } else {
            Node sekarang = kepala;
            while (sekarang.next != null) {
                sekarang = sekarang.next;
            }
            sekarang.next = baru;
        }
        ukuran++;
    }

    String ambil(int indeks) {
        Node sekarang = kepala;
        for (int i = 0; i < indeks; i++) {
            sekarang = sekarang.next;
            kunjungan++;        // satu lompatan tautan
        }
        kunjungan++;            // node tujuan juga dikunjungi
        return sekarang.data;
    }

    boolean hapus(String data) {
        Node sekarang = kepala;
        Node sebelum = null;
        while (sekarang != null) {
            kunjungan++;
            if (sekarang.data.equals(data)) {
                if (sebelum == null) {
                    kepala = sekarang.next;     // node pertama digeser keluar
                } else {
                    sebelum.next = sekarang.next; // tautan dilewati satu node
                }
                ukuran--;
                return true;
            }
            sebelum = sekarang;
            sekarang = sekarang.next;
        }
        return false;
    }

    static void cetak(Node kepala) {
        Node sekarang = kepala;
        StringBuilder sb = new StringBuilder();
        while (sekarang != null) {
            sb.append(sekarang.data);
            if (sekarang.next != null) {
                sb.append(" -> ");
            }
            sekarang = sekarang.next;
        }
        System.out.println(sb);
    }
}