<\/span><\/h2>\nInti:<\/strong> deretan elemen yang diakses lewat indeks. Implementasi modern biasanya \u201cdynamic array\u201d (bisa bertambah otomatis).<\/p>\n\n- Kapan dipakai:<\/strong> akses acak super cepat (O(1))\u2014misalnya daftar produk di keranjang, cache kecil, buffer UI.<\/li>\n
- Kelebihan:<\/strong> sederhana, locality of reference bagus (ramah CPU cache), iterasi cepat.<\/li>\n
- Kekurangan:<\/strong> sisip\/hapus di tengah mahal (O(n)); saat penuh perlu realokasi.<\/li>\n<\/ul>\n
# Python list = dynamic array\r\narr = [10, 20, 30]\r\narr.append(40) # amortized O(1)\r\nx = arr[2] # O(1) -> 30\r\narr.insert(1, 15) # O(n)<\/code><\/pre>\n<\/span>2. Linked List (Singly\/Doubly)<\/span><\/h2>\nInti:<\/strong> elemen saling terhubung via pointer. Singly<\/em> (satu arah), double<\/em> (dua arah), circular<\/em> bila ekor menunjuk kepala.<\/p>\n\n- Kapan dipakai:<\/strong> banyak operasi sisip\/hapus di awal\/akhir (O(1)).<\/li>\n
- Kelebihan:<\/strong> tidak perlu realokasi besar; node bisa disebar di memori.<\/li>\n
- Kekurangan:<\/strong> akses acak lambat (O(n)); overhead pointer.<\/li>\n<\/ul>\n
class Node:\r\n def __init__(self, val, nxt=None):\r\n self.val, self.next = val, nxt\r\n\r\n# tambah di depan O(1)\r\nhead = Node(3, Node(2, Node(1)))<\/code><\/pre>\n<\/span>3. Stack<\/span><\/h2>\nInti:<\/strong> LIFO (last in, first out). Push\/pop di ujung yang sama.<\/p>\n\n- Kapan dipakai:<\/strong> undo\/redo, parsing ekspresi, DFS, backtracking.<\/li>\n
- Operasi:<\/strong> push O(1), pop O(1), top O(1).<\/li>\n<\/ul>\n
stack = []\r\nstack.append('A') # push\r\nstack.append('B')\r\ntop = stack.pop() # 'B'<\/code><\/pre>\n<\/span>4. Queue, Deque, Priority Queue<\/span><\/h2>\nQueue:<\/strong> FIFO. Deque:<\/strong> bisa tambah\/hapus di kedua ujung. Priority Queue (Heap):<\/strong> elemen prioritas tertinggi\/terendah keluar dulu.<\/p>\n\n- Kapan dipakai:<\/strong> antrian job, BFS, scheduler, rate limiter.<\/li>\n<\/ul>\n
from collections import deque\r\nq = deque()\r\nq.append('A'); q.append('B')\r\nq.popleft() # 'A' (O(1))\r\n\r\nimport heapq\r\npq = []\r\nheapq.heappush(pq, (1, \"urgent\"))\r\nheapq.heappush(pq, (5, \"normal\"))\r\nheapq.heappop(pq) # (1, \"urgent\")<\/code><\/pre>\n<\/span>5. Hash Table (Map\/Dict\/Set)<\/span><\/h2>\nInti:<\/strong> kunci \u2192 nilai dengan hashing. Rata-rata operasi O(1).<\/p>\n\n- Kapan dipakai:<\/strong> lookup cepat (userId \u2192 profil), frequency count, indexing kecil.<\/li>\n
- Kelebihan:<\/strong> sangat cepat untuk akses kunci langsung.<\/li>\n
- Kekurangan:<\/strong> butuh fungsi hash bagus; ada kemungkinan collision.<\/li>\n<\/ul>\n
# dict & set di Python = hash table\r\nprice = {\"apel\": 10000, \"jeruk\": 12000}\r\nprice[\"apel\"] # 10000 (O(1) average)\r\nseen = set([1,2,3])<\/code><\/pre>\n<\/span>6. Tree & Binary Search Tree (BST)<\/span><\/h2>\nInti:<\/strong> struktur hierarki. BST:<\/strong> kiri < root < kanan, memudahkan pencarian.<\/p>\n\n- Kapan dipakai:<\/strong> indeks terurut, fitur autocomplete sederhana, set terurut.<\/li>\n
- Kelebihan:<\/strong> pencarian\/insert\/hapus O(log n) jika seimbang.<\/li>\n
- Kekurangan:<\/strong> bisa ter-degenerate (jadi linked list) jika tak di-balance.<\/li>\n<\/ul>\n
Versi \u201cself-balancing<\/em>\u201d seperti AVL\/Red-Black menjaga O(log n) stabil.<\/p>\n<\/span>7. Heap (Min-Heap\/Max-Heap)<\/span><\/h2>\nInti:<\/strong> pohon biner lengkap yang menjaga elemen ekstrem di root (min atau max).<\/p>\n\n- Kapan dipakai:<\/strong> top-k, scheduling, Dijkstra, median running.<\/li>\n
- Operasi:<\/strong> push\/pop O(log n); peek O(1).<\/li>\n<\/ul>\n
import heapq\r\nscores = [34, 90, 12, 77, 56]\r\ntop3 = heapq.nlargest(3, scores) # [90, 77, 56]<\/code><\/pre>\n<\/span>8. Trie (Prefix Tree)<\/span><\/h2>\nInti:<\/strong> pohon karakter untuk menyimpan kumpulan string; tiap edge mewakili huruf.<\/p>\n\n- Kapan dipakai:<\/strong> autocomplete, spell-check, pencarian prefix.<\/li>\n
- Kelebihan:<\/strong> cek prefix O(L) (L = panjang kata), independen dari jumlah kata.<\/li>\n
- Kekurangan:<\/strong> boros memori bila data jarang berbagi prefix.<\/li>\n<\/ul>\n
class TrieNode:\r\n def __init__(self):\r\n self.child = {}\r\n self.end = False\r\n\r\nroot = TrieNode()\r\n# sisip 'cat'\r\nnode = root\r\nfor ch in \"cat\":\r\n node = node.child.setdefault(ch, TrieNode())\r\nnode.end = True<\/code><\/pre>\n<\/span>9. Graph (Adjacency List\/Matrix)<\/span><\/h2>\nInti:<\/strong> node (vertex) + edge (bisa berbobot\/berarah). Representasi umum adjacency list<\/em> (hemat) atau matrix<\/em> (akses O(1) untuk cek edge).<\/p>\n\n- Kapan dipakai:<\/strong> peta jalan, jaringan sosial, dependency, rekomendasi.<\/li>\n
- Algoritma populer:<\/strong> BFS\/DFS, Dijkstra, Floyd\u2013Warshall, Topological sort.<\/li>\n<\/ul>\n
# adjacency list\r\nG = {\r\n 'A': [('B',5), ('C',1)],\r\n 'B': [('C',2)],\r\n 'C': [('B',1)]\r\n}<\/code><\/pre>\n<\/span>10. Disjoint Set \/ Union-Find<\/span><\/h2>\nInti:<\/strong> mempartisi elemen ke dalam himpunan terpisah, mendukung find<\/em> & union<\/em> sangat cepat (hampir O(1)).<\/p>\n\n- Kapan dipakai:<\/strong> deteksi siklus, Kruskal (MST), konektivitas komponen.<\/li>\n<\/ul>\n
# rumus umum: path compression + union by rank\r\nparent = list(range(10))\r\nrank = [0]*10\r\n\r\ndef find(x):\r\n if parent[x] != x:\r\n parent[x] = find(parent[x])\r\n return parent[x]\r\n\r\ndef union(a,b):\r\n ra, rb = find(a), find(b)\r\n if ra == rb: return\r\n if rank[ra] < rank[rb]:\r\n parent[ra] = rb\r\n elif rank[ra] > rank[rb]:\r\n parent[rb] = ra\r\n else:\r\n parent[rb] = ra\r\n rank[ra] += 1<\/code><\/pre>\n<\/span>11. Segment Tree & Fenwick Tree (BIT)<\/span><\/h2>\nInti:<\/strong> struktur untuk range query\/update cepat pada array (mis. sum\/min\/max).<\/p>\n\n- Segment Tree:<\/strong> update & query O(log n), fleksibel (bisa min\/max\/gcd).<\/li>\n
- Fenwick\/BIT:<\/strong> implementasi lebih sederhana untuk sum\/prefix sum O(log n).<\/li>\n<\/ul>\n
# Fenwick Tree sederhana (1-indexed)\r\nclass BIT:\r\n def __init__(self, n):\r\n self.fw = [0]*(n+1)\r\n def add(self, i, v):\r\n while i < len(self.fw):\r\n self.fw[i] += v\r\n i += i & -i\r\n def sum(self, i):\r\n s = 0\r\n while i > 0:\r\n s += self.fw[i]\r\n i -= i & -i\r\n return s<\/code><\/pre>\n<\/span>12. B-Tree \/ B+Tree<\/span><\/h2>\nInti:<\/strong> pohon multi-cabang, tinggi rendah, cocok untuk storage disk\/SSD. Banyak dipakai sebagai indeks database dan file system.<\/p>\n\n- Kapan dipakai:<\/strong> indeks on-disk dengan blok besar; minim page fault.<\/li>\n
- Bedanya:<\/strong> B+Tree simpan data hanya di daun; node internal hanya pointer\/kunci\u2014bagus buat range scan.<\/li>\n<\/ul>\n
<\/span>13. Skip List<\/span><\/h2>\nInti:<\/strong> linked list bertingkat dengan \u201cjalur cepat\u201d. Operasi probabilistik O(log n).<\/p>\n\n- Kapan dipakai:<\/strong> alternatif balanced tree yang lebih mudah diimplementasi.<\/li>\n
- Catatan:<\/strong> dipakai di beberapa database dan sistem cache.<\/li>\n<\/ul>\n
<\/span>14. Bloom Filter<\/span><\/h2>\nInti:<\/strong> probabilistic set: cek keanggotaan \u201cmungkin ada\u201d atau \u201cpasti tidak ada\u201d. Sangat hemat memori.<\/p>\n\n- Kapan dipakai:<\/strong> filter awal sebelum query mahal (mis. cache, anti-spam, rekomendasi).<\/li>\n
- Kelebihan:<\/strong> footprint kecil, kecepatan tinggi.<\/li>\n
- Kekurangan:<\/strong> false positive mungkin; tidak ada delete tanpa trik.<\/li>\n<\/ul>\n
<\/span>15. LRU Cache (HashMap + Doubly Linked List)<\/span><\/h2>\nInti:<\/strong> cache yang membuang item paling lama tidak dipakai. Kombinasi hash map<\/em> (O(1) akses) + doubly linked list<\/em> (O(1) pindah\/hapus).<\/p>\n\n- Kapan dipakai:<\/strong> caching hasil query API, gambar, atau perhitungan berat.<\/li>\n<\/ul>\n
# sketsa LRU: gunakan OrderedDict untuk ringkas\r\nfrom collections import OrderedDict\r\n\r\nclass LRU:\r\n def __init__(self, cap):\r\n self.cap = cap\r\n self.od = OrderedDict()\r\n def get(self, k):\r\n if k not in self.od: return None\r\n self.od.move_to_end(k) # most recent\r\n return self.od[k]\r\n def put(self, k, v):\r\n if k in self.od:\r\n self.od.move_to_end(k)\r\n self.od[k] = v\r\n if len(self.od) > self.cap:\r\n self.od.popitem(last=False) # remove LRU<\/code><\/pre>\n<\/span>Ringkasan Kompleksitas (garis besar)