Bagaimana Anda memilih struktur data yang tepat untuk suatu masalah?

Question

Accepted Answer

Pilih struktur yang **operasi paling sering digunakan paling murah** untuk pola akses Anda. Mulai dengan mendaftar operasi yang akan Anda lakukan, perkirakan frekuensinya, lalu cocokkan dengan kekuatan struktur.

## Daftar periksa keputusan

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Sesuaikan operasi dengan kompleksitas

| Kebutuhan | Struktur terbaik | Biaya op utama |
|---|---|---|
| Akses acak menurut indeks | dynamic array | O(1) |
| Pencarian menurut kunci | hash map | O(1) avg |
| Diurutkan + kueri rentang | balanced BST | O(log n) |
| Min/max berulang kali | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Pencarian awalan | trie | O(L) |

## Contoh penalaran

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Mengapa ini penting

Memilih dengan baik sering kali merupakan perbedaan antara solusi O(n) dan O(n²) — pengungkit terbesar pada kinerja.

Pewawancara menguji persis penalaran ini: mereka ingin melihat Anda memetakan persyaratan ke biaya operasi, bukan menghafal struktur.

Kebutuhan	Struktur terbaik	Biaya op utama
Akses acak menurut indeks	dynamic array	O(1)
Pencarian menurut kunci	hash map	O(1) avg
Diurutkan + kueri rentang	balanced BST	O(log n)
Min/max berulang kali	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Pencarian awalan	trie	O(L)