एक 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
| ऑपरेशन | वेळ |
|---|---|
| इंडेक्सद्वारे प्रवेश | O(1) |
| शोध (unsorted) | O(n) |
| जोडणी (dynamic) | O(1) amortized |
| समाविष्ट/हटवणी पुढे/मध्यभागी | O(n) |
Arrays हे बहुतांश इतर संरचनांचा आधार आहेत — strings, hash tables, heaps, आणि dynamic lists सर्व त्यांच्यावर बिल्ड होतात.
त्यांचे cache locality अनेकदा एक "slowdown" Big-O array ला एक "faster" pointer-based structure मध्ये वास्तविक बेंचमार्क्समध्ये हरवून देते.