Fondasi · Pelajaran 1 dari 10
Kenapa struktur data penting
8 menit baca · BelajarCode
Struktur data adalah cara menyusun data di memori supaya operasi tertentu efisien. Tidak ada struktur yang unggul untuk semua operasi. Memilih struktur data berarti menentukan operasi mana yang paling sering dipakai, lalu membuatnya cepat.
Tipe data abstrak
Tipe data abstrak (ADT) mendefinisikan apa yang bisa dilakukan, tanpa menyebut bagaimana caranya. Contohnya ADT antrean: tambah di belakang, ambil dari depan. ADT itu bisa diwujudkan dengan array atau linked list. Pemakai antrean tidak perlu tahu wujudnya, cukup operasinya.
| Struktur | Akses indeks ke-i | Cari nilai | Tambah | Hapus |
|---|---|---|---|---|
| Array dinamis | O(1) | O(n) | O(1) di akhir, O(n) di tengah | O(n) |
| Linked list | O(n) | O(n) | O(1) di depan | O(1) jika simpulnya diketahui |
| Stack dan queue | Tidak dipakai | Tidak dipakai | O(1) | O(1) |
| Hash table | Tidak dipakai | O(1) | O(1) | O(1) |
| Binary search tree seimbang | Tidak dipakai | O(log n) | O(log n) | O(log n) |
| Heap | Tidak dipakai | O(n) | O(log n) | O(log n) untuk minimum |
Bedanya terasa di data besar
1import time23n = 100_0004daftar = list(range(n))5himpunan = set(daftar)6dicari = [n - 1, n - 2, n - 3] * 10078mulai = time.perf_counter()9for x in dicari:10 _ = x in daftar11waktu_list = time.perf_counter() - mulai1213mulai = time.perf_counter()14for x in dicari:15 _ = x in himpunan16waktu_set = time.perf_counter() - mulai1718print(f"Mencari di list: {waktu_list:.4f} detik")19print(f"Mencari di set : {waktu_set:.6f} detik")20print(f"set kira-kira {waktu_list / waktu_set:.0f} kali lebih cepat")Mencari di list: 0.2875 detik Mencari di set : 0.000031 detik set kira-kira 9274 kali lebih cepat
Mencari di list memeriksa satu per satu (O(n)), sedangkan set memakai hash table (O(1) rata-rata). Untuk 300 pencarian di antara 100.000 data, bedanya ribuan kali lipat.
Cek pemahaman
Sebuah aplikasi kamus sering mencari arti kata dan jarang menambah kata baru. Struktur mana yang paling cocok untuk pencarian?
Latihan
Pilih strukturnya
Tentukan struktur data yang paling cocok untuk setiap kebutuhan dan jelaskan alasannya:
- Fitur undo di editor teks.
- Antrean cetak dokumen di printer kantor.
- Mengecek apakah sebuah username sudah dipakai.
- Mengambil pasien dengan kondisi paling darurat di IGD.
Pembahasan
- Stack. Aksi terakhir dibatalkan lebih dulu (LIFO).
- Queue. Dokumen yang dikirim lebih dulu dicetak lebih dulu (FIFO).
- Hash table atau set. Pemeriksaan keanggotaan O(1) rata-rata.
- Heap (priority queue). Mengambil elemen dengan prioritas tertinggi dalam O(log n).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.