Array అనేది ఒకే రకమైన మూలకాలను కలిగి ఉన్న ఒక ఆసన్న మెమరీ బ్లాక్, 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) |
Arrays చాలా ఇతర నిర్మాణాల ఆధారం — strings, hash tables, heaps, మరియు dynamic lists అన్నీ వాటిపై నిర్మితమైనవి.
వాటి కాష్ స్థానికતা తరచుగా "నెమ్మదిగా" Big-O array ను వాస్తవ బెంచ్మార్క్లలో "వేగవంతమైన" పాయింటర్-ఆధారిత నిర్మాణాన్ని ఓడించడానికి చేస్తుంది.