Apa iku array lan apa complexities saka operasine?

Question

IT Interview Practice · Accepted Answer

**Array** iku blok memory kontigo sing ngandhut elemen saka jenis sing padha, diindeks wiwit `0`. Amarga elemen-elemen dumunung jejer-jejeran, alamat saka elemen `i` dihitung langsung minangka `base + i * elementSize`, menehi **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)
```

## Conto

```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:** mabur indexing, cache-friendly (data iku kontigo), low memory overhead.
- **Weaknesses:** ngemasi/ngilang ing tengah iku O(n); fixed-size arrays mbutuh copying kanggo tuwuh.

## Mengapa iki penting

Array iku fondasi ing ngisor-e struktur paling - strings, hash tables, heaps, lan dynamic lists kabeh bangun sawerining dheweke.

Cache locality dheweke asring naggawe array "alon" ngalahake struktur "cepet" berbasis-pointer ing real benchmarks.

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

Memory layout

Conto

Complexity

Trade-offs

Mengapa iki penting

Pitakon sing gegandhengan