List

Memilih antara ArrayList dan LinkedList dengan pertukaran yang jujur, dan biasanya jawabannya ArrayList.

Daftar isi

List adalah koleksi yang menjaga urutan penyimpanan dan mengizinkan elemen yang sama muncul lebih dari sekali, sehingga cocok untuk daftar belanja, riwayat pencarian, atau antrean unduhan. Topik ini membandingkan dua implementasinya, ArrayList dan LinkedList, lewat perilaku nyata keduanya. Di akhir topik, pertukaran performa antara keduanya sudah terukur, dan keputusan pemilihannya pun punya dasar yang jelas.

ArrayList, pilihan bawaan yang jarang salah#

ArrayList menyimpan elemennya di dalam array biasa yang dibungkus agar ukurannya bisa bertambah. Karena pendiamnya array, membaca elemen pada indeks tertentu dikerjakan dengan satu lompatan alamat, dan jumlah langkahnya konstan tanpa memedulikan ukuran daftar. Menambah elemen di akhir biasanya juga cepat, kecuali ketika kapasitas array habis dan Java harus membuat array baru lalu menyalin isinya.

java DemoArrayList.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class DemoArrayList {

    public static void main(String[] args) {
        List<String> daftarBelanja = new ArrayList<>();
        daftarBelanja.add("beras");
        daftarBelanja.add("telur");
        daftarBelanja.add("minyak goreng");
        daftarBelanja.add(1, "gula");        // sisip di indeks 1

        System.out.println("daftar    : " + daftarBelanja);
        System.out.println("indeks 2  : " + daftarBelanja.get(2));
        System.out.println("indeks telur: " + daftarBelanja.indexOf("telur"));
        System.out.println("jumlah    : " + daftarBelanja.size());

        daftarBelanja.set(3, "minyak zaitun");
        daftarBelanja.remove("gula");
        System.out.println("sesudah ubah: " + daftarBelanja);
        System.out.println("elemen pertama: " + daftarBelanja.get(0));

        for (int i = 0; i < daftarBelanja.size(); i++) {
            System.out.println(i + " -> " + daftarBelanja.get(i));
        }
    }
}

text Keluaran

daftar    : [beras, gula, telur, minyak goreng]
indeks 2  : telur
indeks telur: 2
jumlah    : 4
sesudah ubah: [beras, telur, minyak zaitun]
elemen pertama: beras
0 -> beras
1 -> telur
2 -> minyak zaitun

Program di atas memperlihatkan sisi praktis ArrayList sehari-hari. Pemanggilan add(1, "gula") menyisipkan tanpa menghapus elemen lain, elemen setelahnya bergeser otomatis ke kanan. Metode indexOf("telur") mengembalikan 2 karena pencarian dilakukan dari depan, dan set(3, ...) mengganti isi tanpa mengubah jumlah elemen. Perulangan for biasa pun wajar dipakai di sini karena get(i) murah, sebuah keistimewaan yang tidak dimiliki semua koleksi.

Membangun ArrayList dari isi yang sudah ada juga cukup satu baris, yaitu new ArrayList<>(sumber) dengan sumber berupa koleksi lain. Salinan semacam ini berdiri sendiri, sehingga perubahan pada salah satunya tidak merembet ke yang lain. Kebiasaan itu berguna ketika data mentah perlu dirapikan dahulu, misalnya disalin lalu disaring, sebelum dipakai oleh bagian kode yang lain.

LinkedList dan keunggulan ujungnya#

LinkedList menyimpan setiap elemen sebagai simpul (node) yang memegang elemennya sekaligus rujukan ke simpul sebelum dan sesudahnya. Menambah atau menghapus di ujung depan maupun ujung belakang hanya memindahkan beberapa rujukan, tanpa menggeser elemen lain. Sisipan di tengah juga murah setelah posisinya ditemukan, tetapi menemukan posisi itu sendiri justru pekerjaan yang mahal.

java DemoLinkedList.java

import java.util.LinkedList;

public class DemoLinkedList {

    public static void main(String[] args) {
        LinkedList<String> riwayatCetak = new LinkedList<>();
        riwayatCetak.addLast("halaman-1.pdf");
        riwayatCetak.addLast("halaman-2.pdf");
        riwayatCetak.addFirst("sampul.pdf");

        System.out.println("antrean   : " + riwayatCetak);
        System.out.println("terdepan  : " + riwayatCetak.getFirst());
        System.out.println("terakhir  : " + riwayatCetak.getLast());

        riwayatCetak.removeFirst();
        riwayatCetak.addLast("lampiran.pdf");
        System.out.println("sesudahnya: " + riwayatCetak);

        System.out.println("elemen tengah: " + riwayatCetak.get(1));
    }
}

text Keluaran

antrean   : [sampul.pdf, halaman-1.pdf, halaman-2.pdf]
terdepan  : sampul.pdf
terakhir  : halaman-2.pdf
sesudahnya: [halaman-1.pdf, halaman-2.pdf, lampiran.pdf]
elemen tengah: halaman-2.pdf

Metode addFirst, getLast, dan removeFirst adalah wilayah nyaman LinkedList, karena semuanya hanya menyentuh simpul tepi. Perhatikan baris terakhir, get(1) masih cepat karena daftarnya pendek. Pada daftar seribu elemen, get(500) harus menyusuri simpul satu per satu dari ujung terdekat, sehingga biayanya tumbuh seiring posisi indeks yang dituju.

Cara kerja simpul itu juga menjelaskan harga memorinya. Setiap elemen tidak hanya menyimpan datanya, melainkan dua rujukan tambahan ke tetangganya, sehingga LinkedList yang berisi seribu teks pendek membawa dua ribu rujukan ekstra dibandingkan ArrayList berisi data sama. Konsekuensi lain muncul saat dibaca berurutan, karena simpul-simpul itu tersebar di memori, sedangkan isi array berdempetan dan ramah bagi cache prosesor. Dua hal ini yang membuat LinkedList jarang menang pada pemakaian sehari-hari, meski teorinya menarik.

Pertukaran yang jujur#

Perbandingan keduanya sering disederhanakan menjadi “LinkedList cepat untuk sisip dan hapus”, padahal pernyataan itu setengah benar. Tabel berikut merinci biaya operasi pada kasus yang paling sering muncul, dengan notasi $O(1)$ untuk biaya konstan dan $O(n)$ untuk biaya yang tumbuh seiring jumlah elemen $n$ .

Operasi	`ArrayList`	`LinkedList`
`get(i)` pada indeks mana pun	$O(1)$	$O(n)$
`add` di akhir	$O(1)$ diamortisasi	$O(1)$
`add` atau `remove` di awal	$O(n)$ , semua bergeser	$O(1)$
`add` atau `remove` di tengah	$O(n)$	$O(n)$ , karena mencari posisinya
konsumsi memori per elemen	kecil, satu slot array	lebih besar, tiap simpul bawa rujukan

Dari tabel itu, dua kesimpulan praktis muncul dengan sendirinya. Pertama, kasus “sisip dan hapus di tengah” ternyata mahal di keduanya, karena LinkedList harus berjalan sampai posisi itu meski pemindahannya sendiri murah. Kedua, satu-satunya wilayah kemenangan nyata LinkedList adalah operasi di ujung depan, dan kebutuhan seperti itu biasanya lebih tepat dilayani ArrayDeque, yang menjadi bahan topik Queue dan Deque.

Kesalahan umum#

Memilih LinkedList hanya karena suatu saat “mungkin sering sisip dan hapus”. Bila sisipnya di tengah dan pencariannya lewat indeks, biayanya tetap $O(n)$ . Ukur kebutuhan sebenarnya sebelum mengubah pilihan.
Menghapus elemen lewat remove(i) dalam perulangan yang indeksnya berjalan maju. Setiap penghapusan menggeser elemen setelahnya, sehingga ada elemen yang terlewat. Jalankan perulangan mundur, atau gunakan removeIf.
Mengira size() adalah metode array. Array mengenali panjangnya lewat length, sedangkan List memakai size(). Keduanya tidak saling menggantikan.
Memanggil get(i) pada LinkedList berukuran besar di dalam perulangan. Pola ini menghasilkan biaya $O(n^2)$ secara keseluruhan. Susuri daftar dengan for-each atau iterator agar biayanya linear.

Ringkasan#

List menjaga urutan penyimpanan dan menerima duplikat, dengan ArrayList dan LinkedList sebagai implementasi yang paling sering dipertimbangkan.
ArrayList dibangun di atas array, sehingga get selalu $O(1)$ , sedangkan sisip dan hapus di awal menyeret $O(n)$ .
LinkedList murah di kedua ujung dan mahal untuk pencarian indeks, sehingga keunggulannya terbatas pada operasi tepi.
Untuk mayoritas kebutuhan, ArrayList adalah pilihan yang lebih sederhana dan lebih cepat.

Referensi#

Interface List (The Java Tutorials) — Oracle — aturan kontrak List, termasuk pencarian dan perbedaan antarimplementasi.
Class ArrayList — Oracle Java SE 21 — dokumentasi ArrayList, termasuk catatan waktu konstan yang diamortisasi untuk add.
Class LinkedList — Oracle Java SE 21 — dokumentasi LinkedList beserta metode ujung depan dan belakangnya.