ArrayList

ArrayList adalah implementasi List yang paling banyak dipakai di kode Java sehari-hari, dan alasan utamanya sederhana: ArrayList membungkus array mentah dengan kemampuan tumbuh otomatis. Nama “array” di depannya bukan kebetulan — di balik layar, objek ArrayList memang menjaga satu array internal sebagai wadah elemennya. Dengan begitu, ArrayList mewarisi keunggulan terbesar array (akses posisi secara instan) sekaligus menutup kelemahan terbesarnya (panjang tetap). Pada Chapter ini kita bedah mekanisme internalnya, membuktikan perilaku akses dan penghapusan lewat indeks, lalu menyusun ulang isi dengan sort.

Array Internal dan Pertumbuhan Kapasitas #

Setiap objek ArrayList menyimpan dua ukuran yang berbeda. Capacity adalah panjang array internal — berapa banyak elemen yang masih bisa ditampung tanpa realokasi — sedangkan size adalah jumlah elemen yang benar-benar terisi. Ketika kita membuat new ArrayList<>(), array internalnya masih kosong dan hanya dialokasikan saat add pertama tiba, dengan kapasitas awal 10. Selama size masih di bawah capacity, method add hanya menulis ke slot kosong berikutnya — operasi yang sangat cepat.

Kapasitas 10 itu tentu cepat terlampaui. Saat add menemukan array penuh, ArrayList membuat array baru sekitar 1,5 kali lipat kapasitas lama (rumus kapasitas + (kapasitas >> 1)), menyalin seluruh elemen ke sana, lalu membuang array lama agar dijemput garbage collector. Penyalinan itu membuat satu add tertentu lebih lambat, tetapi biaya tersebut terdistribusi rata ke seluruh operasi penambahan sehingga biaya rata-ratanya konstan — istilah teknisnya amortized O(1). Itulah sebabnya menambah ribuan elemen di ekor ArrayList tetap terasa cepat.

Akses Acak dan Pergeseran Saat Penghapusan #

Karena elemen berdampingan dalam satu array, get(indeks) cukup menghitung alamat slot ke-indeks — tidak ada penelusuran elemen demi elemen. Konsekuensinya ada di penghapusan: mencabut elemen di tengah meninggalkan lubang, dan ArrayList menutupnya dengan menggeser semua elemen di kanan satu posisi ke kiri. Program berikut memperlihatkan kedua perilaku tersebut lewat cetakan indeks:

import java.util.*;

public class AksesAcak {
    public static void main(String[] args) {
        List<String> rak = new ArrayList<>(List.of("Beras", "Telur", "Minyak", "Gula", "Kopi", "Teh"));

        // Akses acak: get(i) langsung menuju posisi i, dari ujung mana pun.
        System.out.println("get(0): " + rak.get(0));
        System.out.println("get(5): " + rak.get(5));
        cetak(rak);

        // Hapus di tengah (indeks 2), lalu amati pergeseran indeks.
        rak.remove(2);
        System.out.println("Setelah remove(2):");
        cetak(rak);
    }

    private static void cetak(List<String> daftar) {
        for (int i = 0; i < daftar.size(); i++) {
            System.out.println("  indeks " + i + " : " + daftar.get(i));
        }
    }
}

Output yang Dihasilkan:

get(0): Beras
get(5): Teh
  indeks 0 : Beras
  indeks 1 : Telur
  indeks 2 : Minyak
  indeks 3 : Gula
  indeks 4 : Kopi
  indeks 5 : Teh
Setelah remove(2):
  indeks 0 : Beras
  indeks 1 : Telur
  indeks 2 : Gula
  indeks 3 : Kopi
  indeks 4 : Teh

Mari kita bedah baris-baris pentingnya:

1. Baris 6 (List.of(...) dibungkus new ArrayList<>()): List.of menghasilkan list unmodifiable, sehingga kita membungkusnya dengan ArrayList untuk mendapatkan salinan yang bisa diubah.
2. Baris 9-10 (rak.get(0) dan rak.get(5)): mengakses elemen pertama dan terakhir memakan waktu yang sama — keduanya satu lompatan aritmetika alamat, O(1).
3. Baris 16-18 (rak.remove(2)): elemen indeks 2 (Minyak) dihapus; Gula, Kopi, dan Teh bergeser masing-masing dari indeks 3, 4, 5 ke 2, 3, 4.
4. Method cetak: loop klasik berindeks sengaja dipakai agar pembaca melihat pemetaan posisi-ke-nilai secara eksplisit; jumlah elemen yang bergeser membesar seiring posisi penghapusan makin ke depan.

Penggeseran itulah sumber biaya O(n) penghapusan di tengah. Untuk daftar belanja puluhan item, biaya tersebut tidak terasa; untuk jutaan elemen dengan penghapusan frekuensi tinggi di tengah, struktur lain seperti LinkedList atau desain berbasis antrean layak dipertimbangkan.

Menyusun Ulang Isi dengan sort #

ArrayList mewarisi method sort(Comparator) dari kontrak List. Method tersebut mengurutkan di tempat (isi list berubah, tidak membuat list baru) dan dijamin stabil — elemen yang dianggap setara oleh comparator mempertahankan urutan relatifnya. Program berikut mengurutkan daftar stok gudang dua kali dengan dua comparator berbeda:

import java.util.*;

public class SusunStok {
    public static void main(String[] args) {
        // Variabel bertipe ArrayList: bisa memanggil trimToSize().
        ArrayList<String> gudang = new ArrayList<>(List.of("Minyak", "Gula", "Beras", "Telur", "Kopi"));

        gudang.sort(Comparator.naturalOrder());
        System.out.println("Urut A-Z     : " + gudang);

        // sort stabil: urutan A-Z dipertahankan untuk nama yang sama panjang.
        gudang.sort(Comparator.comparingInt(String::length));
        System.out.println("Urut panjang : " + gudang);

        // Pangkas kapasitas internal menjadi sama dengan size; isi tak berubah.
        gudang.trimToSize();
        System.out.println("Setelah trim : " + gudang + " (ukuran " + gudang.size() + ")");
    }
}

Output yang Dihasilkan:

Urut A-Z     : [Beras, Gula, Kopi, Minyak, Telur]
Urut panjang : [Gula, Kopi, Beras, Telur, Minyak]
Setelah trim : [Gula, Kopi, Beras, Telur, Minyak] (ukuran 5)

Poin bedahnya:

1. Baris 6 (sort(Comparator.naturalOrder())): mengurutkan alfabetis dari Beras hingga Telur.
2. Baris 10 (Comparator.comparingInt(String::length)): mengurutkan berdasarkan panjang nama. Hasilnya [Gula, Kopi, Beras, Telur, Minyak] — pasangan yang sama panjang (Gula/Kopi dan Beras/Telur) tetap mengikuti urutan A-Z dari sort sebelumnya karena sort bersifat stabil.
3. Baris 14 (trimToSize()): memangkas array internal hingga panjangnya persis size. Tidak ada efek pada isi maupun size(), tetapi metode ini berguna ketika sebuah ArrayList besar sudah selesai diisi dan kapasitas cadangannya tidak lagi diperlukan.

Ringkasan Kinerja Operasi #

Tabel berikut merangkum karakteristik biaya operasi ArrayList yang paling sering dipakai:

Kekuatan ArrayList sekaligus menjadi kelemahannya: array menjadikan akses posisi sangat cepat, tetapi penyisipan dan penghapusan di tengah memicu pergeseran massal. Bagaimana jika aplikasi kita justru sering menyisip dan menghapus di ujung-ujung struktur? Chapter berikutnya membahas LinkedList, implementasi List yang menukar array dengan rantai node.

Referensi #

• Java API Specification: java.util.ArrayList
• Java API Specification: java.util.List
• Dev.java: The Java Collections Framework

import java.util.*;

public class AksesAcak {
    public static void main(String[] args) {
        List<String> rak = new ArrayList<>(List.of("Beras", "Telur", "Minyak", "Gula", "Kopi", "Teh"));

        // Akses acak: get(i) langsung menuju posisi i, dari ujung mana pun.
        System.out.println("get(0): " + rak.get(0));
        System.out.println("get(5): " + rak.get(5));
        cetak(rak);

        // Hapus di tengah (indeks 2), lalu amati pergeseran indeks.
        rak.remove(2);
        System.out.println("Setelah remove(2):");
        cetak(rak);
    }

    private static void cetak(List<String> daftar) {
        for (int i = 0; i < daftar.size(); i++) {
            System.out.println("  indeks " + i + " : " + daftar.get(i));
        }
    }
}

import java.util.*;

public class SusunStok {
    public static void main(String[] args) {
        // Variabel bertipe ArrayList: bisa memanggil trimToSize().
        ArrayList<String> gudang = new ArrayList<>(List.of("Minyak", "Gula", "Beras", "Telur", "Kopi"));

        gudang.sort(Comparator.naturalOrder());
        System.out.println("Urut A-Z     : " + gudang);

        // sort stabil: urutan A-Z dipertahankan untuk nama yang sama panjang.
        gudang.sort(Comparator.comparingInt(String::length));
        System.out.println("Urut panjang : " + gudang);

        // Pangkas kapasitas internal menjadi sama dengan size; isi tak berubah.
        gudang.trimToSize();
        System.out.println("Setelah trim : " + gudang + " (ukuran " + gudang.size() + ")");
    }
}