array کیا ہے اور اس کے operations کی complexities کیا ہیں؟

Question

Accepted Answer

ایک **array** memory کا ایک continuous block ہے جو ایک جیسی قسم کے elements کو رکھتا ہے، جو `0` سے indexed ہوتے ہیں۔ چونکہ elements ایک دوسرے کے ساتھ ملے ہوئے ہوتے ہیں، element `i` کا address براہ راست `base + i * elementSize` کے طور پر compute ہوتا ہے، جو **O(1) random access** دیتا ہے۔

## Memory layout

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (4-byte ints)
```

## Example

```python
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
```

## Complexity

| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Append (dynamic) | O(1) amortized |
| Insert/delete at front/middle | O(n) |

## Trade-offs

- **Strengths:** تیزی سے indexing، cache-friendly (data contiguous ہے)، کم memory overhead۔
- **Weaknesses:** درمیان میں inserting/removing O(n) ہے؛ fixed-size arrays کو بڑھانے کے لیے copying کی ضرورت ہے۔

## اہمیت

Arrays اکثر دوسری structures کی بنیاد ہیں — strings، hash tables، heaps، اور dynamic lists سب ان پر بنے ہیں۔

ان کا cache locality اکثر ایک "سست" Big-O array کو "تیزتر" pointer-based structure کو حقیقی benchmarks میں ہرا دیتا ہے۔

Operation	Time
Access by index	O(1)
Search (unsorted)	O(n)
Append (dynamic)	O(1) amortized
Insert/delete at front/middle	O(n)