Struktur data dasar
List, map, set, stack, dan queue: apa keunggulan masing-masing, bentuknya di Python, JavaScript, PHP, dan Go, dan kenapa memilih yang tepat bisa membuat kode puluhan ribu kali lebih cepat.
Sejauh ini di seri ini kita membahas nilai tunggal: sebuah angka, sebuah string, sebuah boolean. Program nyata bekerja dengan kumpulan: daftar pesanan, harga per produk, kumpulan tag di sebuah artikel. Struktur data adalah cara menyusun nilai-nilai itu supaya hal-hal yang perlu kita lakukan dengannya jadi mudah dan cepat.
Tidak perlu banyak. Lima ini sudah mencakup sebagian besar kode sehari-hari: list, map, set, stack, dan queue. Bagian ini membahas keunggulan masing-masing, dan bentuknya di Python, JavaScript, PHP, dan Go.
List (array): data yang berurutan
List menyimpan item secara berurutan dan bisa diambil berdasarkan posisinya.
prices = [12, 5, 30]
prices.append(8)
print(prices, prices[0], prices[-1], len(prices))
# [12, 5, 30, 8] 12 8 4
Pakai list saat urutan itu penting atau saat kita akan menelusuri semua item. Mengambil item berdasarkan posisi itu cepat. Mencari item berdasarkan nilainya tidak, karena komputer harus mengecek item satu per satu (dibahas di bawah).
Semua bahasa punya: list di Python, Array di JavaScript, slice di Go, dan array di PHP.
Map (dictionary): cari berdasarkan kunci
Map menyimpan pasangan kunci → nilai, sehingga nilai bisa ditemukan lewat kuncinya tanpa mencari.
stock = {"book": 3, "pen": 10}
stock["mug"] = 2
print(stock["pen"]) # 10
print(stock.get("lamp")) # None
print(stock.get("lamp", 0)) # 0
print(list(stock)) # ['book', 'pen', 'mug']
Tutorial Python menjelaskan bahwa “dictionaries are indexed by keys, which can be any immutable type” (diindeks dengan kunci yang tidak bisa diubah), dan list(d) “returns a list of all the keys used in the dictionary, in insertion order”, sesuai urutan dimasukkan. Meminta kunci yang tidak ada dengan stock["lamp"] memunculkan KeyError; .get() memberi kita pilihan nilai cadangan.
Pakai map setiap kali Anda mendapati diri mencari di list “item yang id-nya X”. Untuk itulah map ada.
Di JavaScript, pakai Map. MDN: “The Map object holds key-value pairs and remembers the original insertion order of the keys.” Objek biasa juga bisa dipakai sebagai map, tapi membawa kunci warisan. MDN mencatat bahwa “A Map does not contain any keys by default. It only contains what is explicitly put into it”:
const stock = new Map([["book", 3], ["pen", 10]]);
stock.set("mug", 2);
console.log(stock.get("pen"), stock.get("lamp"), stock.has("lamp"));
// 10 undefined false
const obj = {};
console.log("toString" in obj, new Map().has("toString"));
// true false
Di Go, map sudah bawaan bahasa. Ada dua detail penting. Pertama, kunci yang tidak ada tidak membuat error: “If the requested key doesn’t exist, we get the value type’s zero value”, yang didapat adalah nilai nol dari tipenya. Untuk membedakan “tidak ada” dengan “nol”, pakai bentuk dua nilai, di mana ok “is true if the key exists in the map, and false if not”:
stock := map[string]int{"book": 3, "pen": 10}
fmt.Println(stock["chair"]) // 0
n, ok := stock["chair"]
fmt.Println(n, ok) // 0 false
Kedua, urutan tidak dijaga. Kata blog Go: “the iteration order is not specified and is not guaranteed to be the same from one iteration to the next.” Dua loop atas map yang sama, dalam satu kali jalan:
book pen mug lamp cup
lamp cup book pen mug
Kalau butuh urutan yang stabil di Go, urutkan kuncinya dulu.
PHP: satu array untuk semuanya
PHP tidak memisahkan list dan map. Manualnya menyebut langsung: “An array in PHP is actually an ordered map.” Array di PHP sebenarnya adalah map yang berurutan. “List” hanyalah map yang kuncinya kebetulan 0, 1, 2, …
$prices = [12, 5, 30];
$prices[] = 8;
$stock = ["book" => 3, "pen" => 10];
$stock["mug"] = 2;
echo json_encode($prices), " ", json_encode($stock);
// [12,5,30,8] {"book":3,"pen":10,"mug":2}
Praktis, tapi ada beberapa kejutan. Kunci yang terlihat seperti bilangan bulat dikonversi: “Strings containing valid decimal ints, unless the number is preceded by a + sign, will be cast to the int type. E.g. the key “8” will actually be stored under 8.” Kunci string "8" disimpan sebagai angka 8. Jadi kunci-kunci ini bertabrakan:
$mixed = ["8" => "a", "08" => "b", 8 => "c"];
var_dump($mixed);
// [8] => "c", ["08"] => "b" ← "8" dan 8 adalah kunci yang sama
Lalu, menghapus item bisa meninggalkan celah di kunci, yang membuat “list” berubah jadi map saat di-encode ke JSON:
$tags = array_unique(["go", "php", "go", "python"]);
echo json_encode($tags); // {"0":"go","1":"php","3":"python"}
echo json_encode(array_values($tags)); // ["go","php","python"]
Baris kedua itu layak diingat kalau Anda membuat API dengan PHP: API yang kadang mengembalikan array dan kadang objek adalah sumber bug yang umum di sisi client.
Set: nilai unik, cek keberadaan dengan cepat
“A set is an unordered collection with no duplicate elements”: set adalah kumpulan tanpa urutan dan tanpa duplikat. Pakai saat yang penting adalah ada atau tidaknya sesuatu, bukan di mana atau berapa kali.
tags = {"go", "php", "go", "python"}
print(sorted(tags), "php" in tags)
# ['go', 'php', 'python'] True
a = {"go", "php"}
b = {"php", "js"}
print(sorted(a & b), sorted(a | b), sorted(a - b))
# ['php'] ['go', 'js', 'php'] ['go']
Set juga langsung memberi irisan (&), gabungan (|), dan selisih (-), yang menggantikan banyak loop bersarang.
Di JavaScript, nilai dalam Set “may only occur once; it is unique in the set’s collection”:
const tags = new Set(["go", "php", "go", "python"]);
console.log(tags.size, tags.has("php")); // 3 true
Go tidak punya tipe set; cara yang umum adalah map dengan nilai bool (atau kosong): map[string]bool. Padanan terdekat di PHP adalah array_unique, atau memakai nilainya sebagai kunci array.
Kenapa pilihannya penting: mencari di list vs set
Mengecek apakah sebuah nilai ada di list berarti melihat item satu per satu. Mengecek di set (atau kunci map) hampir langsung sampai ke jawabannya. Bedanya membesar seiring ukuran data. Di mesin yang dipakai untuk menulis catatan ini, mengecek satu angka 100 kali di kumpulan berisi sejuta angka:
big_list = list(range(1_000_000))
big_set = set(big_list)
# 999_999 in big_list ×100 → 0.5022 s
# 999_999 in big_set ×100 → 0.000011 s
Sekitar 46.000 kali lebih cepat, cukup dengan mengganti satu baris. Angka pastinya tergantung mesin, tapi jaraknya tidak. Inilah perbaikan performa yang paling sering di kode sehari-hari: ganti “mencari di list di dalam loop” dengan “cek di set atau map”. Bagian 10 menjelaskan alasannya dengan notasi Big-O.
Stack dan queue: urutan pemrosesan
Kadang yang penting adalah item mana yang keluar berikutnya.
Stack itu terakhir masuk, pertama keluar, seperti tumpukan piring. Tutorial Python: “The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (“last-in, first-out”).” Bayangkan tombol back di browser, atau undo:
stack = []
stack.append("page1"); stack.append("page2"); stack.append("page3")
print(stack.pop(), stack) # page3 ['page1', 'page2']
Queue itu pertama masuk, pertama keluar, seperti antrean di loket. List bisa dipakai, “however, lists are not efficient for this purpose”, karena mengambil dari depan berarti menggeser semua item lainnya. “To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends”:
from collections import deque
queue = deque(["order1", "order2"])
queue.append("order3")
print(queue.popleft(), list(queue)) # order1 ['order2', 'order3']
Antrean job, antrean pesan, antrean cetak, dan “proses pesanan sesuai urutan datang” semuanya memakai struktur ini.
Catatan soal tuple dan data yang tetap
Python juga punya tuple: mirip list, tapi tidak bisa diubah setelah dibuat.
point = (3, 4)
point[0] = 5
# TypeError: 'tuple' object does not support item assignment
Cocok untuk kelompok kecil nilai yang tetap, seperti koordinat atau pasangan (result, error). Di Go dan PHP, padanannya biasanya struct atau class kecil dengan field bernama, yang sering lebih jelas daripada mengingat arti posisi 0 dan 1.
Memilih dengan cepat
| Butuh untuk… | Pakai |
|---|---|
| Menyimpan item berurutan, menelusuri semuanya | List / array |
| Mencari berdasarkan id, nama, atau kode | Map / dictionary |
| Mengecek “ada atau tidak?”, membuang duplikat | Set |
| Undo, back, pemrosesan bersarang | Stack |
| Memproses sesuai urutan datang | Queue |
Kenapa ini penting sehari-hari
- Performa. Kebanyakan loop lambat di kode bisnis adalah “untuk setiap item, cari di list lain”. Map atau set biasanya memperbaikinya.
- Kebenaran. Map di Go dan array PHP yang punya celah tidak berperilaku seperti list berurutan. Kalau urutan output atau bentuk JSON penting, buat eksplisit.
- Kunci yang tidak ada. Python memunculkan error, JavaScript dan PHP memberi
undefined/null, dan Go memberi nilai nol. Ketahui mana yang sedang dihadapi sebelum menganggap0berarti “tidak ditemukan”. - Kode yang mudah dibaca.
if tag in allowed_tagsdengan set menyatakan maksudnya dengan tepat.
Coba sendiri
- Jalankan perbandingan waktu list vs set di mesin Anda sendiri, lalu coba dengan 10.000 dan 10 juta item.
- Di PHP, buat array,
unset()satu item di tengah, lalujson_encode. Perbaiki denganarray_values. - Di Go, loop map yang sama tiga kali lalu cetak kuncinya. Lalu urutkan kuncinya dan loop lagi.
- Cari tempat di kode Anda yang mencari di list di dalam loop, lalu tulis ulang dengan map atau set.
Ringkasan
- List menjaga urutan; map mencari berdasarkan kunci; set menyimpan nilai unik dan cepat menjawab “ada atau tidak?”.
- Stack terakhir masuk pertama keluar; queue pertama masuk pertama keluar. Di Python, pakai
dequeuntuk queue. MapdanSetdi JavaScript lebih bersih daripada memakai objek biasa. Go punya map tapi tidak punya set, dan urutan map tidak dijamin.- Array PHP adalah map berurutan; kunci string berisi angka berubah jadi integer, dan celah bisa mengubah list jadi objek JSON.
- Memilih set atau map daripada mencari di list bisa puluhan ribu kali lebih cepat untuk data besar.
Referensi
- Data Structures, tutorial Python.
- Map dan Set, MDN.
- Arrays, PHP Manual.
- Andrew Gerrand, Go maps in action, The Go Blog, Februari 2013.