Struktur data itu fondasi cara kita menyimpan dan mengambil data. Pilihan yang tepat bikin aplikasi terasa cepat, hemat memori, dan enak di-maintain. Di bawah ini kami bedah contoh struktur data lengkap—apa fungsinya, kapan dipakai, plus contoh kode singkat—agar WiseSob bisa langsung praktik.
1. Array (Dynamic Array)
Inti: deretan elemen yang diakses lewat indeks. Implementasi modern biasanya “dynamic array” (bisa bertambah otomatis).
- Kapan dipakai: akses acak super cepat (O(1))—misalnya daftar produk di keranjang, cache kecil, buffer UI.
- Kelebihan: sederhana, locality of reference bagus (ramah CPU cache), iterasi cepat.
- Kekurangan: sisip/hapus di tengah mahal (O(n)); saat penuh perlu realokasi.
# Python list = dynamic array
arr = [10, 20, 30]
arr.append(40) # amortized O(1)
x = arr[2] # O(1) -> 30
arr.insert(1, 15) # O(n)2. Linked List (Singly/Doubly)
Inti: elemen saling terhubung via pointer. Singly (satu arah), double (dua arah), circular bila ekor menunjuk kepala.
- Kapan dipakai: banyak operasi sisip/hapus di awal/akhir (O(1)).
- Kelebihan: tidak perlu realokasi besar; node bisa disebar di memori.
- Kekurangan: akses acak lambat (O(n)); overhead pointer.
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
# tambah di depan O(1)
head = Node(3, Node(2, Node(1)))3. Stack
Inti: LIFO (last in, first out). Push/pop di ujung yang sama.
- Kapan dipakai: undo/redo, parsing ekspresi, DFS, backtracking.
- Operasi: push O(1), pop O(1), top O(1).
stack = []
stack.append('A') # push
stack.append('B')
top = stack.pop() # 'B'4. Queue, Deque, Priority Queue
Queue: FIFO. Deque: bisa tambah/hapus di kedua ujung. Priority Queue (Heap): elemen prioritas tertinggi/terendah keluar dulu.
- Kapan dipakai: antrian job, BFS, scheduler, rate limiter.
from collections import deque
q = deque()
q.append('A'); q.append('B')
q.popleft() # 'A' (O(1))
import heapq
pq = []
heapq.heappush(pq, (1, "urgent"))
heapq.heappush(pq, (5, "normal"))
heapq.heappop(pq) # (1, "urgent")5. Hash Table (Map/Dict/Set)
Inti: kunci → nilai dengan hashing. Rata-rata operasi O(1).
- Kapan dipakai: lookup cepat (userId → profil), frequency count, indexing kecil.
- Kelebihan: sangat cepat untuk akses kunci langsung.
- Kekurangan: butuh fungsi hash bagus; ada kemungkinan collision.
# dict & set di Python = hash table
price = {"apel": 10000, "jeruk": 12000}
price["apel"] # 10000 (O(1) average)
seen = set([1,2,3])6. Tree & Binary Search Tree (BST)
Inti: struktur hierarki. BST: kiri < root < kanan, memudahkan pencarian.
- Kapan dipakai: indeks terurut, fitur autocomplete sederhana, set terurut.
- Kelebihan: pencarian/insert/hapus O(log n) jika seimbang.
- Kekurangan: bisa ter-degenerate (jadi linked list) jika tak di-balance.
Versi “self-balancing” seperti AVL/Red-Black menjaga O(log n) stabil.
7. Heap (Min-Heap/Max-Heap)
Inti: pohon biner lengkap yang menjaga elemen ekstrem di root (min atau max).
- Kapan dipakai: top-k, scheduling, Dijkstra, median running.
- Operasi: push/pop O(log n); peek O(1).
import heapq
scores = [34, 90, 12, 77, 56]
top3 = heapq.nlargest(3, scores) # [90, 77, 56]8. Trie (Prefix Tree)
Inti: pohon karakter untuk menyimpan kumpulan string; tiap edge mewakili huruf.
- Kapan dipakai: autocomplete, spell-check, pencarian prefix.
- Kelebihan: cek prefix O(L) (L = panjang kata), independen dari jumlah kata.
- Kekurangan: boros memori bila data jarang berbagi prefix.
class TrieNode:
def __init__(self):
self.child = {}
self.end = False
root = TrieNode()
# sisip 'cat'
node = root
for ch in "cat":
node = node.child.setdefault(ch, TrieNode())
node.end = True9. Graph (Adjacency List/Matrix)
Inti: node (vertex) + edge (bisa berbobot/berarah). Representasi umum adjacency list (hemat) atau matrix (akses O(1) untuk cek edge).
- Kapan dipakai: peta jalan, jaringan sosial, dependency, rekomendasi.
- Algoritma populer: BFS/DFS, Dijkstra, Floyd–Warshall, Topological sort.
# adjacency list
G = {
'A': [('B',5), ('C',1)],
'B': [('C',2)],
'C': [('B',1)]
}10. Disjoint Set / Union-Find
Inti: mempartisi elemen ke dalam himpunan terpisah, mendukung find & union sangat cepat (hampir O(1)).
- Kapan dipakai: deteksi siklus, Kruskal (MST), konektivitas komponen.
# rumus umum: path compression + union by rank
parent = list(range(10))
rank = [0]*10
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a,b):
ra, rb = find(a), find(b)
if ra == rb: return
if rank[ra] < rank[rb]:
parent[ra] = rb
elif rank[ra] > rank[rb]:
parent[rb] = ra
else:
parent[rb] = ra
rank[ra] += 111. Segment Tree & Fenwick Tree (BIT)
Inti: struktur untuk range query/update cepat pada array (mis. sum/min/max).
- Segment Tree: update & query O(log n), fleksibel (bisa min/max/gcd).
- Fenwick/BIT: implementasi lebih sederhana untuk sum/prefix sum O(log n).
# Fenwick Tree sederhana (1-indexed)
class BIT:
def __init__(self, n):
self.fw = [0]*(n+1)
def add(self, i, v):
while i < len(self.fw):
self.fw[i] += v
i += i & -i
def sum(self, i):
s = 0
while i > 0:
s += self.fw[i]
i -= i & -i
return s12. B-Tree / B+Tree
Inti: pohon multi-cabang, tinggi rendah, cocok untuk storage disk/SSD. Banyak dipakai sebagai indeks database dan file system.
- Kapan dipakai: indeks on-disk dengan blok besar; minim page fault.
- Bedanya: B+Tree simpan data hanya di daun; node internal hanya pointer/kunci—bagus buat range scan.
13. Skip List
Inti: linked list bertingkat dengan “jalur cepat”. Operasi probabilistik O(log n).
- Kapan dipakai: alternatif balanced tree yang lebih mudah diimplementasi.
- Catatan: dipakai di beberapa database dan sistem cache.
14. Bloom Filter
Inti: probabilistic set: cek keanggotaan “mungkin ada” atau “pasti tidak ada”. Sangat hemat memori.
- Kapan dipakai: filter awal sebelum query mahal (mis. cache, anti-spam, rekomendasi).
- Kelebihan: footprint kecil, kecepatan tinggi.
- Kekurangan: false positive mungkin; tidak ada delete tanpa trik.
15. LRU Cache (HashMap + Doubly Linked List)
Inti: cache yang membuang item paling lama tidak dipakai. Kombinasi hash map (O(1) akses) + doubly linked list (O(1) pindah/hapus).
- Kapan dipakai: caching hasil query API, gambar, atau perhitungan berat.
# sketsa LRU: gunakan OrderedDict untuk ringkas
from collections import OrderedDict
class LRU:
def __init__(self, cap):
self.cap = cap
self.od = OrderedDict()
def get(self, k):
if k not in self.od: return None
self.od.move_to_end(k) # most recent
return self.od[k]
def put(self, k, v):
if k in self.od:
self.od.move_to_end(k)
self.od[k] = v
if len(self.od) > self.cap:
self.od.popitem(last=False) # remove LRURingkasan Kompleksitas (garis besar)
| Struktur | Akses | Sisip/Hapus | Catatan |
|---|---|---|---|
| Array | O(1) indeks | O(n) tengah | append amortized O(1) |
| Linked List | O(n) | O(1) di ujung | pointer overhead |
| Stack/Queue | — | O(1) | LIFO/FIFO |
| Hash Table | O(1)* | O(1)* | *rata-rata, bergantung hash |
| BST seimbang | O(log n) | O(log n) | AVL/RB tree |
| Heap | — | O(log n) | peek O(1) |
| Trie | O(L) | O(L) | L = panjang kata |
| Union-Find | ~O(1) | ~O(1) | path compression |
Panduan Memilih: kapan pakai yang mana
- Butuh akses acak cepat: Array atau Hash Table.
- Butuh sisip/hapus sering di ujung: Linked List, Deque.
- Butuh urutan prioritas: Heap (priority queue).
- Butuh data terurut + range query: Balanced BST, B-Tree/B+Tree, Segment Tree/Fenwick.
- Butuh prefix search: Trie.
- Butuh jaringan/relasi: Graph.
- Butuh filter cepat hemat memori: Bloom Filter.
- Butuh cache yang pintar: LRU (kombinasi hashmap + doubly linked list).
Contoh nyata: dari masalah ke struktur
- Autocomplete produk: Trie untuk prefix, Hash Table untuk metadata produk, Heap untuk ranking terlaris.
- Rekomendasi teman: Graph untuk relasi, BFS/DFS untuk jelajah, plus Hash Table untuk visited.
- Harga dinamis realtime: Heap untuk top-k harga, Fenwick/Segment Tree untuk perhitungan agregat cepat per kategori.
- Feed berita: Queue untuk pipeline event, LRU cache untuk konten yang sering tampil.
Anti-pattern yang sering bikin performa jeblok
- Memaksa satu struktur untuk semua situasi: misal selalu pakai array padahal perlu lookup kunci → pakai Hash Table.
- Over-optimasi prematur: bikin struktur rumit padahal bottleneck ada di I/O jaringan.
- Salah representasi graf: pakai adjacency matrix untuk graf jarang (sparse) → boros memori; pakai adjacency list.
- Lupa edge case: pointer null di linked list, atau collision handling di hash table.
Tips implementasi biar rapi dan aman
- Tulis operasi dasar eksplisit: buat fungsi
push/pop/peekdsb., jangan campur aduk di tempat lain. - Tes unit untuk kasus sudut: list kosong, satu elemen, duplikat kunci, overflow kapasitas.
- Pikirkan memori: node kecil tapi banyak tetap mahal; gunakan struktur ringkas bila datanya sederhana.
- Profil sebelum optimasi: pakai profiler untuk memastikan perubahan memang mempercepat.
Belajar lebih dalam dari dokumentasi resmi
Kalau ingin memahami detail perilaku list/dict/set di Python (yang jadi representasi beberapa struktur di atas), dokumentasi resminya enak dibaca: docs.python.org – Data Structures. Cocok buat memastikan asumsi kompleksitas dan corner case.
Kesimpulan
Memilih struktur data itu soal kecocokan masalah: ada yang unggul di akses acak, ada yang jago urutan prioritas, ada yang spesialis prefix atau relasi. Dengan memahami karakter tiap struktur—beserta trade-off waktu dan memori—kami dan WiseSob bisa menulis kode yang lebih efisien, gampang dirawat, dan tetap ngebut saat skala tumbuh.
