Java Academy · Pelajaran

Perbandingan LinkedList dan ArrayList

Bandingkan kinerja penyisipan, penghapusan, dan akses acak untuk memilih tipe list yang tepat.

Pelajaran 3 dari 413 langkah

Perbandingan LinkedList dan ArrayList adalah pelajaran Java Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Java Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Java Academy mencakup 4 pelajaran total.

Pertanyaan Inti

ArrayList dan LinkedList sama-sama mengimplementasikan List, sehingga keduanya memiliki API yang sama. Perbedaannya terletak pada struktur data internal dan operasi yang dapat dilakukan secara efisien oleh masing-masing.

Struktur Internal ArrayList

ArrayList menyimpan elemen dalam larik yang bersebelahan. Saat larik penuh, larik tersebut diganti dengan larik baru yang berukuran 1,5× lebih besar dan semua elemen disalin.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Meninjau Kembali Struktur Internal LinkedList

Setiap elemen berada di objek Node tersendiri dengan penunjuk prev/next. Tidak ada memori yang bersebelahan — simpul dapat berada di mana saja dalam heap.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Akses Acak: ArrayList Unggul

ArrayList.get(i) adalah O(1) — indeks larik diakses secara langsung. LinkedList.get(i) adalah O(n) — menelusuri hingga n/2 simpul.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Penyisipan di Awal: LinkedList Unggul

Menambahkan pada indeks 0 dalam ArrayList memerlukan pergeseran semua elemen — O(n). LinkedList hanya memperbarui dua penunjuk — O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Penyisipan di Akhir: Kurang Lebih Sama

ArrayList dan LinkedList sama-sama menyediakan penambahan di akhir dengan biaya diamortisasi O(1). ArrayList sesekali memicu penyalinan saat ukurannya diperbesar, tetapi secara diamortisasi tetap O(1). LinkedList mengalokasikan simpul baru — tidak memerlukan perubahan ukuran.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Penggunaan Memori

ArrayList: ~8 byte per elemen (satu referensi dalam larik). LinkedList: ~48 byte per elemen (objek Node dengan data, prev, next, serta header objek). Untuk kumpulan data besar, ArrayList menggunakan jauh lebih sedikit memori.

Kinerja Iterasi

Iterasi berurutan (for-each atau iterator) adalah O(n) untuk keduanya. Namun, ArrayList memperoleh manfaat dari prapengambilan cache CPU — elemen-elemennya tersimpan bersebelahan dalam memori. Simpul LinkedList tersebar di seluruh heap sehingga menyebabkan cache miss.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Penyisipan/Penghapusan di Tengah

Keduanya memerlukan O(n) untuk menemukan posisi. Setelah posisi ditemukan, ArrayList menggeser elemen dalam O(n); LinkedList hanya melepaskan tautan dalam O(1). Jadi, untuk perubahan di tengah yang sering dilakukan ketika Anda sudah memegang iterator, LinkedList lebih unggul; jika tidak, keduanya serupa.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Panduan Pengambilan Keputusan

Pilih berdasarkan operasi yang paling dominan:

ArrayList: akses acak, iterasi, penambahan di akhir — mencakup 90% kasus penggunaan
LinkedList: penyisipan/penghapusan yang sering di awal/akhir, penerapan antrean/antrean dua ujung/tumpukan
ArrayDeque: jika Anda memerlukan antrean atau tumpukan murni (lebih baik daripada LinkedList)

Ringkasan Tolok Ukur

Model mental untuk kinerja:

get(i): ArrayList O(1) dibandingkan LinkedList O(n)
add(0,x): ArrayList O(n) dibandingkan LinkedList O(1)
add(x): Keduanya diamortisasi O(1)
Penghapusan iterator: Keduanya O(1) setelah posisinya ditemukan
Memori per elemen: ArrayList ~8B dibandingkan LinkedList ~48B

Pemeriksaan Singkat

Anda sedang membuat antrean tugas yang elemennya ditambahkan ke bagian akhir dan dihapus dari bagian depan jutaan kali per detik. Struktur data manakah yang paling sesuai?

Jawab di pelajaran interaktif

Ringkasan: LinkedList vs ArrayList

Inti penting:

ArrayList unggul untuk akses acak (O(1)) dan iterasi yang ramah cache
LinkedList unggul untuk operasi pada bagian awal/akhir dengan kompleksitas O(1)
Memori: ArrayList sekitar 8B/elemen; LinkedList sekitar 48B/elemen
Untuk antrean/tumpukan, lebih baik gunakan ArrayDeque daripada LinkedList
ArrayList adalah pilihan bawaan yang tepat untuk sebagian besar skenario

Gratis untuk memulai

Belajar Java dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus: 104
Pelajaran: 374

Mulai belajar gratis Lihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Perbandingan LinkedList dan ArrayList” gratis?

Ya — teks lengkap “Perbandingan LinkedList dan ArrayList” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Java Academy, upgrade ke CoddyKit PRO. Kursus Java Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Perbandingan LinkedList dan ArrayList”?

Bandingkan kinerja penyisipan, penghapusan, dan akses acak untuk memilih tipe list yang tepat. Kamu berlatih Java Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Java Academy?

Tidak diperlukan pengalaman sebelumnya. Java Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Perbandingan LinkedList dan ArrayList” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy