/**
 * 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");
    }
}