Suatu array ialah blok memori bersebelahan yang menyimpan elemen daripada jenis yang sama, diindeks bermula dari 0. Oleh sebabkan elemen terletak bersebelahan antara satu sama lain, alamat elemen i dikira secara terus sebagai base + i * elementSize, memberikan capaian rawak O(1).
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Operasi | Masa |
|---|---|
| Capaian mengikut indeks | O(1) |
| Carian (tidak diisih) | O(n) |
| Tambah di hujung (dinamik) | O(1) ter-amortize |
| Sisip/padam di hadapan/tengah | O(n) |
Array ialah asas di sebalik kebanyakan struktur lain — string, hash table, heap, dan senarai dinamik semuanya dibina di atasnya.
Lokaliti cache mereka selalunya menyebabkan array dengan Big-O yang "lebih perlahan" mengatasi struktur berasaskan penunjuk yang "lebih pantas" dalam penanda aras sebenar.