public class AksesVsPenelusuran {

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    // Penghitung langkah nyata yang dilakukan tiap operasi.
    static long langkah;

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

        // Siapkan array dan linked list dengan isi identik: 0..999.
        int[] array = new int[n];
        Node kepala = new Node(0);
        Node ekor = kepala;
        for (int i = 1; i < n; i++) {
            array[i] = i;
            ekor.next = new Node(i);
            ekor = ekor.next;
        }

        System.out.println("n = " + n);
        System.out.println();
        System.out.println("=== Akses satu indeks (jumlah langkah) ===");
        System.out.println("indeks | array | linked list");
        for (int indeks : new int[] {0, 250, 500, 999}) {
            langkah = 0;
            int nilaiArray = aksesArray(array, indeks);
            long dariArray = langkah;

            langkah = 0;
            int nilaiList = aksesList(kepala, indeks);
            long dariList = langkah;

            System.out.printf("%6d | %5d | %12d  (nilai sama: %b)%n",
                    indeks, dariArray, dariList, nilaiArray == nilaiList);
        }

        System.out.println();
        System.out.println("=== Sisip satu nilai di posisi paling depan ===");
        langkah = 0;
        int[] arrayBaru = sisipDepanArray(array, 9999);
        long geserArray = langkah;

        langkah = 0;
        Node kepalaBaru = sisipDepanList(kepala, 9999);
        long tautanList = langkah;

        System.out.println("Array      : " + geserArray + " pergeseran elemen");
        System.out.println("Linked list: " + tautanList + " penugasan tautan");
        System.out.println("Nilai paling depan array      : " + arrayBaru[0]);
        System.out.println("Nilai paling depan linked list: " + kepalaBaru.data);
    }

    static int aksesArray(int[] a, int indeks) {
        langkah++;      // satu perhitungan alamat: alamat dasar + indeks
        return a[indeks];
    }

    static int aksesList(Node kepala, int indeks) {
        Node sekarang = kepala;
        langkah++;      // mengunjungi node kepala
        for (int i = 0; i < indeks; i++) {
            sekarang = sekarang.next;
            langkah++;  // satu lompatan mengikuti tautan
        }
        return sekarang.data;
    }

    static int[] sisipDepanArray(int[] a, int nilai) {
        int[] hasil = new int[a.length + 1];
        hasil[0] = nilai;
        for (int i = 0; i < a.length; i++) {
            langkah++;  // satu elemen bergeser satu posisi ke kanan
            hasil[i + 1] = a[i];
        }
        return hasil;
    }

    static Node sisipDepanList(Node kepala, int nilai) {
        Node baru = new Node(nilai);
        langkah++;      // satu penugasan tautan baru
        baru.next = kepala;
        return baru;
    }
}