ਇੱਕ 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 ਨੂੰ ਇੱਕ "ਤੇਜ਼" pointer-ਅਧਾਰਿਤ ਢਾਂਚੇ ਨੂੰ ਅਸਲ benchmarks ਵਿੱਚ ਹਰਾ ਦਿੰਦੀ ਹੈ।