एक सरणी मेमोरी का एक सन्निहित ब्लॉक है जिसमें एक ही प्रकार के तत्व होते हैं, जिन्हें 0 से अनुक्रमित किया जाता है। चूंकि तत्व एक दूसरे के बगल में हैं, तत्व i का पता base + i * elementSize के रूप में सीधे गणना की जाती है, जो 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
| संचालन | समय |
|---|---|
| इंडेक्स द्वारा पहुँच | O(1) |
| खोज (अनिर्धारित) | O(n) |
| परिशिष्ट (गतिशील) | O(1)摊销 |
| आगे/बीच में सम्मिलन/विलोपन | O(n) |
सरणियाँ अधिकांश अन्य संरचनाओं के तहत आधार हैं — स्ट्रिंग, hash tables, heaps और dynamic lists सभी उन पर निर्मित हैं।
उनकी cache स्थानीयता अक्सर एक "धीमी" Big-O सरणी को वास्तविक बेंचमार्क में एक "तेज़" पॉइंटर-आधारित संरचना को हराती है।