Dasar-dasar array

Array adalah kumpulan elemen yang disimpan berurutan pada satu blok memori, dan tata letak sederhana itulah yang menentukan cepat atau lambatnya setiap operasinya. Topik ini membedah akibat tata letak tersebut: pengindeksan berbiaya $O(1)$, pencarian nilai berbiaya $O(n)$, serta penyisipan dan penghapusan di tengah yang memicu pergeseran elemen. Setiap klaim biaya diuji dengan penghitung operasi pada array berisi 1.000 elemen, lalu diperiksa ulang pada array int[] milik Java. Setelah selesai membaca, biaya tiap operasi array dapat dinilai bukan dari kesan, melainkan dari mekanisme memorinya.

Memori berdampingan#

Ciri utama array adalah memorinya yang contiguous, yakni seluruh elemen menempati blok memori yang benar-benar berurutan tanpa celah. Jika elemen pertama berada di alamat 1000 dan satu elemen int berukuran 4 byte, elemen berikutnya pasti berada di 1004, lalu 1008, dan seterusnya. Karena posisi setiap elemen dapat dihitung dengan rumus $\text{alamat}(i) = \text{alamat awal} + i \times s$, dengan $s$ ukuran satu elemen dalam byte, komputer tidak perlu menelusuri array untuk membaca satu titik tertentu. Satu perhitungan aritmetika langsung menunjuk alamatnya.

Susunan berdampingan inilah yang membedakan array dari struktur data berantai seperti linked list, yang menyimpan setiap elemen beserta alamat elemen sesudahnya sehingga boleh tersebar di mana saja. Pada array, tidak ada alamat yang perlu diikuti, cukup satu rumus. Diagram berikut menggambarkan lima elemen int yang berdampingan beserta indeks dan alamatnya, dengan sel indeks 2 disorot sebagai contoh perhitungan alamat.

Penomoran indeks dimulai dari 0, sehingga elemen kelima berada pada indeks 4 dan alamat 1016. Konvensi ini terasa janggal di awal, tetapi konsisten dipakai Python, Java, dan hampir semua bahasa pemrograman. Konsekuensi yang sering luput: tidak ada celah antarelemen berarti juga tidak ada ruang untuk menyisipkan nilai baru tanpa menggeser elemen yang sudah ada, dan ukuran blok tidak bertambah sendiri.

Akses indeks dan pencarian linear#

Membaca satu elemen lewat indeks, misalnya data[876], hanya membutuhkan satu perhitungan alamat, sehingga biayanya $O(1)$ berapa pun panjang arraynya. Mencari posisi sebuah nilai adalah cerita yang berbeda karena array tidak menyimpan peta dari nilai ke alamat. Satu-satunya cara yang aman pada array acak adalah memeriksa elemen satu per satu dari indeks 0, yang disebut pencarian linear (linear search). Biayanya $O(n)$, karena elemen target berpotensi berada di posisi mana pun dan tidak ada yang boleh dilewati.

Demo berikut menghitung berapa banyak elemen yang benar-benar diperiksa pencarian linear pada array 1.000 elemen, lalu membandingkannya dengan satu akses indeks ke posisi yang sama.

"""Membandingkan biaya akses indeks dan pencarian linear pada array 1.000 elemen."""

data = list(range(1000))   # array 1.000 elemen berisi 0, 1, 2, ..., 999

# akses indeks: satu perhitungan alamat, tanpa memeriksa elemen lain
x = data[876]
print("akses data[876]                :", x)

# pencarian linear: elemen diperiksa satu per satu dari indeks 0
target = 876
pemeriksaan = 0
for i in range(len(data)):
    pemeriksaan += 1
    if data[i] == target:
        break

print("pencarian linear memeriksa     :", pemeriksaan, "elemen")
print("elemen yang dilewati pencarian :", pemeriksaan - 1)

akses data[876]                : 876
pencarian linear memeriksa     : 877 elemen
elemen yang dilewati pencarian : 876

Selisihnya mencolok: akses indeks selesai tanpa memeriksa elemen lain, sedangkan pencarian harus melewati 876 elemen sebelum menemukan targetnya. Angka 877 bukan kebetulan, karena target berada di indeks 876 sehingga seluruh elemen di depannya ikut diperiksa. Pada target yang tidak ada, seluruh 1.000 elemen diperiksa dan penghitung berhenti di sana. Akses $O(1)$ lewat indeks inilah yang menjadikan array bahan baku utama banyak struktur data lain, termasuk tabel hash pada modul hashing.

Penyisipan dan penghapusan di tengah#

Berdampingan berarti tidak ada celah, sehingga menyisipkan satu nilai di tengah memaksa semua elemen setelahnya bergeser satu tempat untuk membuka ruang. Penghapusan bekerja sebaliknya, elemen setelah posisi yang dikosongkan digeser mundur untuk menutup celah itu. Kedua operasi memindahkan hingga $O(n)$ elemen ketika posisinya paling awal, dan baru menjadi murah ketika terjadi di ujung array yang masih kosong.

Simulasi berikut menyisipkan 99 di indeks 2 dari array lima elemen. Satu slot kosong disediakan di ujung terlebih dahulu supaya ukuran array tidak berubah, sehingga pergeserannya terlihat jelas.

# menyisipkan 99 di indeks 2: elemen setelahnya digeser satu tempat
nilai = [10, 20, 30, 40, 50]
geser = 0

nilai.append(0)               # sediakan satu slot kosong di ujung
i = len(nilai) - 1
while i > 2:                  # geser dari belakang agar tidak menimpa
    nilai[i] = nilai[i - 1]
    geser += 1
    i -= 1
nilai[2] = 99

print("array akhir       :", nilai)
print("jumlah pergeseran :", geser)

array akhir       : [10, 20, 99, 30, 40, 50]
jumlah pergeseran : 3

Menyisipkan di indeks 2 dari array lima elemen hanya menggeser tiga elemen, tetapi angka itu tumbuh seiring panjang array dan kedekatan posisi sisipan dengan awal array. Pada array berisi satu juta elemen, penyisipan di indeks 0 menggeser satu juta nilai. Pola pergeseran ini pula yang membuat operasi insert dan remove pada list Python berbiaya $O(n)$ ketika terjadi di tengah.

Biaya pengubahan ukuran#

Panjang array pada Java ditetapkan saat dibuat dan tidak bisa ditambah setelahnya. Ketika array penuh, satu-satunya jalan adalah mengalokasikan array baru yang lebih besar, menyalin seluruh isi lama, lalu meninggalkan array lama untuk dibersihkan. Penyalinan itu berbiaya $O(n)$, dan selama prosesnya berlangsung dua array menempati memori sekaligus. Biaya ini muncul setiap kali kapasitas terlampaui, bukan sekali seumur hidup array.

Python menyembunyikan urusan tersebut lewat list yang menambah slot secara otomatis. Di balik layar, list Python sebenarnya adalah dynamic array, yaitu array yang mengatur ulang kapasitasnya sendiri ketika ruang habis. Kerja menyalin tidak lenyap, hanya dipindahkan ke belakang layar dan dijadwalkan dengan pola tertentu agar tidak terlalu sering. Pola pertumbuhan itu dibedah lebih rinci pada topik array dinamis di modul ini, lengkap dengan hitungan total salinannya.

Array pada Java#

Java menyediakan array sebagai tipe bahasa yang paling polos, ditulis int[] untuk deretan bilangan bulat. Ukurannya terkunci sejak dibuat, atribut length menyimpan panjangnya, dan elemennya diakses lewat indeks dengan kurung siku. Array int[] menyimpan angka secara langsung pada blok memorinya tanpa pembungkus objek, sehingga sangat ringkas untuk data numerik murni. Program kecil berikut mencoba pembacaan, penulisan lewat indeks, dan pembacaan length.

public class DemoArray {
    public static void main(String[] args) {
        int[] nilai = {70, 85, 90, 60, 75};
        System.out.println("panjang array : " + nilai.length);
        System.out.println("nilai[2]      : " + nilai[2]);
        nilai[2] = 95;
        System.out.println("nilai[2] baru : " + nilai[2]);
    }
}

panjang array : 5
nilai[2]      : 90
nilai[2] baru : 95

Baris nilai[2] = 95 menulis langsung ke alamat elemen ketiga, dan nilai.length dibaca tanpa tanda kurung karena memang bukan metode. Program di atas dijalankan dengan java DemoArray.java, yang sejak Java 11 bisa mengeksekusi satu berkas sumber tanpa tahap kompilasi manual. Perhatikan bahwa elemen kelima berada di nilai[4], dan nilai[5] sudah berada di luar blok milik array.

Kesalahan umum#

1. Mengira indeks terakhir sama dengan panjang array. Pada array lima elemen, nilai[5] sudah di luar batas meskipun panjangnya memang 5. Indeks yang sah berhenti di 4, dan perulangan range(len(data)) pada Python aman karena berhenti sebelum batas itu.
2. Menilai array cepat untuk semua jenis pencarian. Kecepatan $O(1)$ hanya berlaku saat indeks sudah diketahui. Mencari sebuah nilai tetap berbiaya $O(n)$ tanpa bantuan struktur tambahan, secepat apa pun aksesnya setelah posisi ditemukan.
3. Menilai operasi dari panjang kodenya. Pemanggilan nilai.insert(0, x) pada list Python hanya satu baris, tetapi menggeser seluruh elemen di belakangnya. Panjang kode tidak berkaitan dengan biayanya, mekanismenya yang menentukan.
4. Membuang ukuran array statis lalu kewalahan. Array int[] yang sudah penuh tidak bisa menampung apa pun lagi, dan solusinya berupa salinan ke array baru yang berbiaya $O(n)$. Rencanakan kapasitas atau pindah ke struktur yang tumbuh otomatis.

Ringkasan#

• Memori berdampingan membuat alamat setiap elemen dapat dihitung dari indeksnya, sehingga akses indeks berbiaya $O(1)$.
• Pencarian nilai memeriksa hingga $O(n)$ elemen karena array tidak menyimpan peta dari nilai ke alamat.
• Penyisipan dan penghapusan di tengah menggeser hingga $O(n)$ elemen, sedangkan pengubahan ukuran menyalin seluruh isi ke array baru.
• Array int[] pada Java berperilaku persis seperti gambaran di atas, lengkap dengan penjaga batas indeks dan atribut length.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi tipe sequence bawaan Python yang dipakai untuk mendemonstrasikan pengindeksan dan penyisipan.
• Dynamic array — Wikipedia — gambaran hubungan array statis, array dinamis, dan biaya penyalinannya.
• Algorithms, 4th Edition — Princeton University — materi algoritma Princeton yang menempatkan array sebagai bahan dasar struktur data lainnya.
• VisuAlgo — visualisasi interaktif array dan operasi-operasinya.