Optimasi Collections

Collection adalah struktur yang paling sering kita sentuh setiap hari, dan kesalahan pilihannya tidak pernah muncul sebagai error — hanya sebagai aplikasi yang lambat diam-diam. ArrayList dan LinkedList sama-sama mengimplementasikan List, sehingga compiler tidak akan pernah mengingatkan kita bahwa keduanya berbeda biaya puluhan kali lipat untuk operasi yang sama. Untuk memilih dengan sadar, kita perlu menghitung biaya operasi secara eksplisit. Chapter ini membandingkan kedua implementasi pada model kertas berbasis penghitung langkah, membedah mekanisme pertumbuhan ArrayList, lalu menyusun tabel keputusan dari pola akses ke struktur data.

Biaya Operasi pada Model Kertas #

Kompleksitas O(1) atau O(n) terasa abstrak sampai dihitung dalam langkah konkret. Untuk n = 1000: ArrayList.get(500) melakukan satu aritmetika alamat lalu satu akses memori; LinkedList.get(500) harus menelusuri 500 node dari ujung terdekat karena tidak ada jalan pintas ke tengah. Sebaliknya add(0) memaksa ArrayList menggeser seluruh 1000 elemen, sementara LinkedList cukup menjahit satu node baru. Program berikut menghitung seluruh skenario itu plus model memori per elemen:

java
ModelAkses.java
/**
 * Perbandingan ArrayList vs LinkedList pada model kertas: setiap operasi
 * dihitung sebagai langkah penelusuran/penyalinan, memori dihitung dari
 * ukuran model per elemen. Seluruh angka deterministik atas n tetap.
 */
public class ModelAkses {

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

        // ---- 1. Biaya operasi dalam langkah ----
        System.out.println("== Biaya operasi (langkah) untuk n = " + n + " ==");
        System.out.printf("%-32s %10s %12s%n", "operasi", "ArrayList", "LinkedList");
        System.out.printf("%-32s %10d %12d%n", "get(indeks tengah)", 1, tengah);
        System.out.printf("%-32s %10d %12d%n", "add(0) - sisip di depan", n, 1);
        System.out.printf("%-32s %10d %12d%n", "iterasi seluruh elemen", n, n);
        System.out.printf("%-32s %10d %12d%n", "contains(nilai asing)", n, n);
        System.out.println();

        // ---- 2. Pertumbuhan ArrayList tanpa kapasitas awal ----
        int kapasitas = 0;   // 0 = array belum dialokasikan
        int realokasi = 0;
        long elemenTersalin = 0;
        int ukuran = 0;
        while (ukuran < n) {
            if (ukuran == kapasitas) {
                kapasitas = (kapasitas == 0) ? 10 : kapasitas + (kapasitas >> 1);
                elemenTersalin += ukuran; // seluruh isi lama dipindahkan
                realokasi++;
            }
            ukuran++;
        }
        System.out.println("== Pertumbuhan ArrayList (faktor 1,5x) ==");
        System.out.println("tanpa kapasitas awal : " + realokasi + " realokasi, "
            + elemenTersalin + " elemen tersalin, kapasitas akhir " + kapasitas);
        System.out.println("new ArrayList<>(n)   : 0 realokasi, 0 elemen tersalin");
        System.out.println();

        // ---- 3. Model memori per elemen (Integer) ----
        int kotakInteger = 16; // header objek + field int
        int slotArray = 4;     // slot referensi pada Object[]
        int nodeLinkedList = 24; // header + 3 referensi (item, next, prev)
        long memoriAl = (long) n * (kotakInteger + slotArray);
        long memoriLl = (long) n * (kotakInteger + nodeLinkedList);
        System.out.println("== Model memori untuk " + n + " elemen Integer ==");
        System.out.println("ArrayList : " + memoriAl + " byte (kotak 16 + slot 4)");
        System.out.println("LinkedList: " + memoriLl + " byte (kotak 16 + node 24)");
        System.out.println();

        // ---- 4. Kesimpulan model ----
        System.out.println("== Kesimpulan ==");
        System.out.println("Akses acak / iterasi : ArrayList menang telak");
        System.out.println("Sisip-hapus ujung    : seri (keduanya O(1) di ujung)");
        System.out.println("Sisip massal di tengah tanpa akses acak: satu-satunya");
        System.out.println("                      wilayah LinkedList layak dipertimbangkan");
    }
}

Output yang Dihasilkan:

text
== Biaya operasi (langkah) untuk n = 1000 ==
operasi                           ArrayList   LinkedList
get(indeks tengah)                        1          500
add(0) - sisip di depan                1000            1
iterasi seluruh elemen                 1000         1000
contains(nilai asing)                  1000         1000

== Pertumbuhan ArrayList (faktor 1,5x) ==
tanpa kapasitas awal : 13 realokasi, 2456 elemen tersalin, kapasitas akhir 1234
new ArrayList<>(n)   : 0 realokasi, 0 elemen tersalin

== Model memori untuk 1000 elemen Integer ==
ArrayList : 20000 byte (kotak 16 + slot 4)
LinkedList: 40000 byte (kotak 16 + node 24)

== Kesimpulan ==
Akses acak / iterasi : ArrayList menang telak
Sisip-hapus ujung    : seri (keduanya O(1) di ujung)
Sisip massal di tengah tanpa akses acak: satu-satunya
                      wilayah LinkedList layak dipertimbangkan

Mari kita telaah bagian-bagian kuncinya:

Baris 13-18 (tabel langkah): empat operasi dasar dihitung sebagai langkah murni. Angka 500 pada get versi LinkedList adalah kasus rata-rata — penelusuran selalu dimulai dari ujung yang lebih dekat, tetapi tetap setengah daftar.
Baris 22-33 (pertumbuhan kapasitas): perulangan meniru kebiasaan ArrayList yang sesungguhnya — kapasitas awal 10, tumbuh 1,5 kali lipat (kapasitas + (kapasitas >> 1)) setiap kali penuh, dan seluruh isi lama disalin ke array baru. Menambahkan 1000 elemen tanpa kapasitas awal berarti 13 realokasi dan 2.456 elemen tersalin.
Baris 41-48 (model memori): setiap elemen Integer kotak menyita 16 byte model; ArrayList menambahkan 4 byte slot referensi per elemen, LinkedList menambahkan 24 byte node berisi tiga referensi. Totalnya dua kali lipat: 20.000 lawan 40.000 byte — belum termasuk jejak memori node yang tercecer di heap, persis pola yang merugikan cache CPU.

Kapasitas Awal dan Pertumbuhan #

Bagian kedua output adalah argumen paling murah dari seluruh bab optimasi ini: new ArrayList<>(1000) menghapus seluruh 13 realokasi itu menjadi nol. Biayanya hanya satu angka yang biasanya sudah kita ketahui — ukuran hasil query, panjang input, jumlah baris laporan. Aturan praktisnya: setiap kali ukuran final bisa diperkirakan, berikan kapasitas awal; pertumbuhan otomatis tetap tersedia sebagai jaring pengaman bila estimasi meleset.

Perlu dicatat juga bahwa pola yang sama berlaku pada HashMap — kapasitas dan load factor mengatur kapan tabel di-rehash, dan HashMap tumbuh dua kali lipat, bukan 1,5 kali. Struktur lain punya pertumbuhan masing-masing; semuanya konstruksi berparameter yang bisa disetel di muka.

Memilih Struktur dari Pola Akses #

Pola akses dominan	Struktur tepat	Alasan struktural
Akses berindeks, iterasi	`ArrayList`	array rapat, satu langkah per akses
Keanggotaan (`contains`) sering	`HashSet`/`HashMap`	hash menggantikan penelusuran linear
Terurut + rentang (`headSet`, `subMap`)	`TreeSet`/`TreeMap`	pohon terurut, rentang O(log n)
Antrean dua ujung	`ArrayDeque`	array melingkar, tanpa node per elemen
FIFO/Ujian prioritas	`ArrayDeque`/`PriorityQueue`	operasi ujung O(1) / log n

Model kertas memberi kita intuisi berbasis angka; kebiasaan berikutnya yang sama seringnya kita pakai adalah stream. Chapter berikutnya membedah biaya pipeline stream dan kapan perulangan biasa tetap lebih tepat.

Referensi #

Berkas Sumber

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

java
/**
 * Perbandingan ArrayList vs LinkedList pada model kertas: setiap operasi
 * dihitung sebagai langkah penelusuran/penyalinan, memori dihitung dari
 * ukuran model per elemen. Seluruh angka deterministik atas n tetap.
 */
public class ModelAkses {

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

        // ---- 1. Biaya operasi dalam langkah ----
        System.out.println("== Biaya operasi (langkah) untuk n = " + n + " ==");
        System.out.printf("%-32s %10s %12s%n", "operasi", "ArrayList", "LinkedList");
        System.out.printf("%-32s %10d %12d%n", "get(indeks tengah)", 1, tengah);
        System.out.printf("%-32s %10d %12d%n", "add(0) - sisip di depan", n, 1);
        System.out.printf("%-32s %10d %12d%n", "iterasi seluruh elemen", n, n);
        System.out.printf("%-32s %10d %12d%n", "contains(nilai asing)", n, n);
        System.out.println();

        // ---- 2. Pertumbuhan ArrayList tanpa kapasitas awal ----
        int kapasitas = 0;   // 0 = array belum dialokasikan
        int realokasi = 0;
        long elemenTersalin = 0;
        int ukuran = 0;
        while (ukuran < n) {
            if (ukuran == kapasitas) {
                kapasitas = (kapasitas == 0) ? 10 : kapasitas + (kapasitas >> 1);
                elemenTersalin += ukuran; // seluruh isi lama dipindahkan
                realokasi++;
            }
            ukuran++;
        }
        System.out.println("== Pertumbuhan ArrayList (faktor 1,5x) ==");
        System.out.println("tanpa kapasitas awal : " + realokasi + " realokasi, "
            + elemenTersalin + " elemen tersalin, kapasitas akhir " + kapasitas);
        System.out.println("new ArrayList<>(n)   : 0 realokasi, 0 elemen tersalin");
        System.out.println();

        // ---- 3. Model memori per elemen (Integer) ----
        int kotakInteger = 16; // header objek + field int
        int slotArray = 4;     // slot referensi pada Object[]
        int nodeLinkedList = 24; // header + 3 referensi (item, next, prev)
        long memoriAl = (long) n * (kotakInteger + slotArray);
        long memoriLl = (long) n * (kotakInteger + nodeLinkedList);
        System.out.println("== Model memori untuk " + n + " elemen Integer ==");
        System.out.println("ArrayList : " + memoriAl + " byte (kotak 16 + slot 4)");
        System.out.println("LinkedList: " + memoriLl + " byte (kotak 16 + node 24)");
        System.out.println();

        // ---- 4. Kesimpulan model ----
        System.out.println("== Kesimpulan ==");
        System.out.println("Akses acak / iterasi : ArrayList menang telak");
        System.out.println("Sisip-hapus ujung    : seri (keduanya O(1) di ujung)");
        System.out.println("Sisip massal di tengah tanpa akses acak: satu-satunya");
        System.out.println("                      wilayah LinkedList layak dipertimbangkan");
    }
}