Array, aynı türden öğeleri içeren bitişik bir bellek bloğudur ve 0 dan indekslenir. Öğeler birbirine yan yana olduğu için, i öğesinin adresi doğrudan base + i * elementSize olarak hesaplanır ve O(1) rastgele erişim sağlar.
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
| İşlem | Zaman |
|---|---|
| İndekse göre erişim | O(1) |
| Arama (sırasız) | O(n) |
| Ekleme (dinamik) | O(1) amortized |
| Başa/ortaya ekleme/silme | O(n) |
Arrayler çoğu diğer veri yapısının temelini oluştururlar — stringler, hash tablolar, heaplar ve dinamik listeler hepsi bunların üzerinde inşa edilir.
Onların cache lokali sıklıkla "daha yavaş" Big-O bir array'i gerçek karşılaştırmalarda "daha hızlı" işaretçi tabanlı bir yapıyı yenmesini sağlar.