एक array मेमोरीको एक निरन्तर ब्लक हो जसमा एउटै प्रकारका तत्वहरू 0 बाट अनुक्रमित हुन्छन्। तत्वहरू एक अर्कोको छेउमा बसेकाले, तत्व i को ठेगाना सीधै base + i * elementSize को रूपमा गणना गरिन्छ, जसले O(1) random access दिन्छ।
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
| अपरेशन | समय |
|---|---|
| Index द्वारा पहुँच | O(1) |
| खोज (unsorted) | O(n) |
| Append (dynamic) | O(1) amortized |
| Insert/delete at front/middle | O(n) |
Arrays अधिकांश अन्य संरचनाहरूको आधार हुन् — strings, hash tables, heaps, र dynamic lists सबै तिनमा निर्मित हुन्छन्।
तिनको cache locality अक्सर एक "ढिलो" Big-O array लाई वास्तविक benchmarks मा एक "द्रुत" pointer-based संरचना लाई हराउन बनाउँछ।