Belajar Data Structure - Decision Matrix: Memilih Struktur Data yang Tepat
Memilih struktur data yang tepat membutuhkan framework, bukan tebakan. Di episode ini kalian memahami pertanyaan kunci: access pattern, insert/delete frequency, memory constraint, serta mempraktikkan 5 coding problems dengan identifikasi DS optimal dan justifikasi trade-off.
#Pendahuluan
Setelah di episode 23 kita menutup Fase 5 dengan suffix array dan suffix tree, pada episode ini kita memasuki Fase 6: Pemilihan, Optimasi & Produksi dengan membahas decision matrix — framework untuk memilih struktur data yang tepat berdasarkan pertanyaan kunci, bukan tebakan atau kebiasaan.
Sejauh ini kita telah mempelajari 15+ struktur data. Pertanyaannya sekarang: kapan harus menggunakan mana? Jawabannya bukan "tergantung" — ada framework yang bisa kalian ikuti secara konsisten.
#Framework: Pertanyaan Kunci
#1. Access Pattern?
Pertanyaan paling penting: bagaimana data kalian diakses?
| Pattern | DS Optimal | Contoh |
|---|---|---|
| Random access by index | Array | Lookup table, buffer |
| Key-value lookup | Hash Map | Dictionary, cache |
| Ordered iteration | BST, TreeMap | Leaderboard, range query |
| Min/Max priority | Heap | Task scheduling, top-K |
| Prefix matching | Trie | Autocomplete |
| Shortest path | Graph + Dijkstra | Navigation |
#2. Insert/Delete Frequency?
| Frekuensi | DS Optimal | Alasan |
|---|---|---|
| Insert di head sering | Linked List | O(1) insert head |
| Insert/delete di tengah | BST, Hash Map | O(log n) atau O(1) |
| Insert/delete di ujung | Deque, Stack | O(1) di kedua ujung |
| Batch insert | Array | Cache-friendly, bulk load |
#3. Memory Constraint?
| Constraint | DS Optimal | Trade-off |
|---|---|---|
| Hemat memori | Array, Bloom Filter | Kurang fleksibel |
| Bisa boros memori | Linked List, Hash Map | Lebih fleksibel |
| Disk-based | B-Tree, LSM-Tree | Minimalkan disk I/O |
#4. Concurrent Access?
| Skenario | DS Optimal | Keterangan |
|---|---|---|
| Read-heavy | ConcurrentHashMap | Optimasi read |
| Write-heavy | Lock-free queue | Minimalisasi lock |
| Read-write balanced | Concurrent skip list | Balance |
#Matriks Perbandingan
| DS | Access | Insert | Delete | Search | Ordered | Memory |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Tergantung | Efisien |
| Linked List | O(n) | O(1) head | O(1) head | O(n) | Tidak | Boros |
| Hash Map | N/A | O(1) avg | O(1) avg | O(1) avg | Tidak | Menengah |
| BST | N/A | O(log n) | O(log n) | O(log n) | Ya | Efisien |
| Heap | O(1) min | O(log n) | O(log n) | O(n) | Partial | Efisien |
| Trie | N/A | O(m) | O(m) | O(m) | Ya | Boros |
| B-Tree | N/A | O(log n) | O(log n) | O(log n) | Ya | Efisien |
#Praktik: 5 Coding Problems
#Problem 1: Two Sum
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# DS optimal: Hash Map — O(n) lookup, O(n) spaceJustifikasi: Hash Map memungkinkan O(1) lookup untuk complement, menjadikan solusi O(n).
#Problem 2: Top K Frequent Elements
from collections import Counter
import heapq
def top_k_frequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
# DS optimal: Heap — O(n log k) untuk top KJustifikasi: Min-heap berukuran k menjaga elemen terbesar secara efisien.
#Problem 3: Merge Intervals
def merge_intervals(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# DS optimal: Array + Sorting — O(n log n) time, O(n) space#Problem 4: LRU Cache
# DS optimal: Doubly Linked List + Hash Map — O(1) get/put
# Sudah dibahas di episode 22#Problem 5: Word Break
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
return root
def word_break(s, word_dict):
trie = build_trie(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
if dp[i]:
node = trie
for j in range(i, n):
if s[j] not in node.children:
break
node = node.children[s[j]]
if node.is_end:
dp[j + 1] = True
return dp[n]
# DS optimal: Trie — prefix sharing untuk dictionary lookupTip
Jangan menghafal matriks ini. Sebaliknya, latih pertanyaan kunci: "Bagaimana data diakses?" → "Seberapa sering insert/delete?" → "Berapa banyak memory?" → "Apakah perlu ordered?" Dengan pertanyaan ini, kalian akan secara natural memilih DS yang tepat.
#Penutup
Inti yang harus dibawa pulang:
- Framework: access pattern → insert/delete frequency → memory → ordering.
- Two Sum → Hash Map. Top K → Heap. Merge Intervals → Array + Sorting.
- LRU Cache → Doubly Linked List + Hash Map. Word Break → Trie.
- Jangan menghafal — latih pertanyaan kunci untuk membuat keputusan.
Di episode 25 selanjutnya kita akan membahas memory layout, cache, dan space-time tradeoff — bagaimana cara data tersimpan di memori mempengaruhi performa, cache locality, prefetching, dan perbandingan array-of-struct vs struct-of-array. Ini akan mengubah cara kalian berpikir tentang "efisien"!