10 Struktur Data yang Harus Diketahui Setiap Programmer

1. Array

Array adalah struktur data paling mendasar, yaitu kumpulan elemen yang disimpan dalam memori yang berdekatan, masing-masing dapat diakses langsung melalui indeks numeriknya. Karena elemen-elemen tersebut berada di sebelah satu sama lain dalam memori dan array mengetahui persis seberapa besar setiap elemen, mengambil item tertentu — seperti elemen kelima, elemen kelima ratus — membutuhkan waktu yang sama persis dan konstan terlepas dari ukuran total array, sebuah properti yang secara formal digambarkan sebagai akses O(1).

Akses waktu konstan itulah kekuatan utama array, dan itulah alasan mengapa array berada di bawah hampir setiap struktur data yang lebih kompleks dalam beberapa bentuk. Kelemahannya terlihat saat kita perlu memasukkan atau menghapus elemen dari mana saja selain dari ujung array. Karena elemen array disimpan berdekatan, memasukkan elemen baru di tengah membutuhkan pergeseran fisik setiap elemen berikutnya satu posisi untuk memberi ruang, yang membuat operasi tersebut menjadi O(n) — semakin banyak elemen yang kita miliki, semakin banyak pergeseran yang harus terjadi. Array secara tradisional juga memiliki ukuran tetap setelah dialokasikan, meskipun sebagian besar bahasa pemrograman modern menyediakan implementasi array dinamis — seperti list pada Python, Array pada JavaScript, ArrayList pada Java — yang secara otomatis mengubah ukurannya sendiri di balik layar sesuai kebutuhan, mengorbankan sedikit overhead demi kenyamanan karena tidak perlu mengetahui ukuran akhir koleksi kita di awal.

2. Linked List

Linked list mengambil pendekatan yang sangat berbeda untuk tujuan dasar yang sama — yaitu menyimpan koleksi elemen yang terurut — dengan sepenuhnya mengabaikan memori yang berdekatan. Sebaliknya, setiap elemen, yang disebut node, menyimpan nilainya sendiri bersama dengan referensi, atau pointer, ke node berikutnya dalam urutan tersebut. List itu sendiri hanya perlu melacak di mana node pertama berada; dari sana, kita dapat mencapai node lain dengan mengikuti rantai pointer, satu tautan pada satu waktu.

Perbedaan struktural ini membalikkan hampir semua kompromi yang dimiliki array. Menyisipkan atau menghapus node dari linked list, setelah kita memiliki referensi ke posisi yang tepat, benar-benar cepat — O(1) — karena kita hanya menghubungkan kembali beberapa pointer, tanpa perlu menggeser elemen lain. Biayanya adalah linked list kehilangan akses acak waktu konstan array sepenuhnya: untuk mencapai node kelima puluh, kita harus menelusuri empat puluh sembilan node pertama, satu tautan pada satu waktu, membuat operasi itu O(n). Linked list ganda memperluas konsep dasar dengan memberikan setiap node penunjuk ke node berikutnya dan node sebelumnya, sehingga memungkinkan penelusuran yang efisien di kedua arah dengan biaya sedikit memori tambahan per node. Dalam praktiknya, linked list muncul di mana pun penyisipan dan penghapusan yang sering lebih penting daripada akses acak, yaitu seperti implementasi dasar dari struktur antrian dan tumpukan tertentu, riwayat undo dalam aplikasi, dan mekanisme internal dari beberapa struktur data yang lebih canggih yang akan dibahas kemudian dalam panduan ini.

3. Stack

Stack adalah struktur data abstrak yang dibangun berdasarkan satu aturan sederhana, yaitu last in, first out, yang biasa disingkat LIFO. Kita hanya dapat menambahkan elemen ke bagian atas tumpukan, langkah yang disebut mendorong (pushing), dan kita hanya dapat menghapus elemen yang saat ini berada di atas, yang disebut mengeluarkan (popping) — tidak ada cara untuk mengakses bagian tengah tumpukan secara langsung, dan batasan itu justru menjadi intinya, bukan keterbatasan.

Model mental yang membuat stack intuitif adalah tumpukan piring fisik, yaitu kita menambahkan piring baru ke atas, dan kita mengambil piring dari atas, dan piring di bagian bawah tumpukan adalah piring terakhir yang dapat kita jangkau. Pola persis ini muncul terus-menerus dalam software nyata. Stack panggilan fungsi, yaitu mekanisme yang digunakan setiap bahasa pemrograman untuk melacak fungsi mana yang memanggil fungsi mana, adalah stack literal — setiap panggilan fungsi didorong ke atas, dan ketika kembali, panggilan tersebut dikeluarkan kembali, melanjutkan tepat di tempat fungsi pemanggil berhenti. Riwayat tombol kembali browser, fungsi undo di editor teks, dan algoritma di balik pengecekan apakah sekumpulan tanda kurung dalam sebuah ekspresi seimbang dengan benar, semuanya bergantung langsung pada perilaku stack, karena dalam setiap kasus ini, item yang paling baru ditambahkan adalah item yang benar-benar perlu ditangani terlebih dahulu.

4. Queue

Queue membalikkan aturan stack sepenuhnya, yaitu first in, first out, atau FIFO. Elemen baru ditambahkan di bagian belakang antrian, dan elemen dihapus dari bagian depan — persis seperti antrean fisik orang yang menunggu di kasir, di mana orang yang tiba pertama adalah orang yang dilayani pertama, dan pendatang baru bergabung di belakang daripada memotong ke depan.

Pengurutan ini membuat antrian sangat cocok untuk situasi apa pun di mana keadilan atau urutan kronologis yang ketat penting. Sistem penjadwalan tugas, manajemen pekerjaan cetak, dan antrian pesan dalam sistem terdistribusi semuanya bergantung pada perilaku antrian secara khusus karena mereka perlu memproses permintaan sesuai urutan kedatangannya, bukan dalam urutan lain. Queue memainkan peran algoritmik mendasar, yaitu pencarian lebar pertama (breadth-first search), salah satu dari dua strategi fundamental untuk menjelajahi struktur pohon atau grafik, bergantung pada antrian untuk melacak simpul mana yang akan dikunjungi selanjutnya, khususnya karena perlu menjelajahi semua simpul pada jarak saat ini dari titik awal sebelum bergerak lebih jauh — konsekuensi langsung dari urutan first-in-first-out yang secara alami diterapkan oleh queue. Variasi seperti antrian dua ujung, atau deque, memungkinkan penyisipan dan penghapusan yang efisien dari kedua ujung secara bersamaan, yang ternyata berguna untuk berbagai algoritma yang membutuhkan fleksibilitas tambahan tersebut.

5. Tabel Hash

Tabel hash, juga disebut peta hash atau kamus tergantung pada bahasa pemrograman, memecahkan salah satu masalah paling umum dalam pemrograman, yaitu diberikan sebuah kunci, temukan nilai yang terkait dengannya, secepat mungkin. Hal ini dilakukan melalui fungsi hash, yang mengambil kunci — seperti string, angka, nilai apa pun yang dapat di-hash — dan mengubahnya menjadi angka yang menentukan di mana nilai kunci tersebut harus berada dalam penyimpanan yang mendasarinya. Ketika kita mencari kunci tersebut nanti, fungsi hash yang sama akan menghitung ulang lokasi yang sama secara langsung, sehingga memungkinkan kita untuk langsung menuju ke tempat yang tepat daripada mencari melalui data kita satu elemen demi satu.

Hal ini memberikan tabel hash sifat yang luar biasa, yaitu seperti pencarian, penyisipan, dan penghapusan rata-rata O(1), terlepas dari berapa banyak elemen yang sebenarnya terdapat dalam tabel hash. Ini adalah kategori kinerja yang benar-benar berbeda dari pencarian melalui array atau list, di mana waktu yang dibutuhkan meningkat secara langsung dengan ukuran koleksi. Komplikasi yang harus ditangani oleh tabel hash adalah tabrakan — yaitu dua kunci berbeda yang kebetulan menghasilkan hash ke lokasi penyimpanan yang sama — yang biasanya diselesaikan melalui teknik seperti chaining, di mana setiap slot penyimpanan menyimpan daftar kecil semua pasangan kunci-nilai yang menghasilkan hash di sana, atau open addressing, yang mencari slot yang tersedia berikutnya sesuai dengan aturan yang ditentukan. Tabel hash benar-benar ada di mana-mana dalam software nyata, seperti lapisan caching, pengindeksan database, menghitung frekuensi item dalam koleksi, dan memeriksa apakah suatu nilai telah dilihat sebelumnya adalah semua contoh penggunaan tabel hash klasik, dan sulit untuk menemukan software yang tidak sepele yang tidak bergantung pada struktur data ini di suatu tempat dalam implementasinya.

6. Tree

Tree mengatur data secara hierarkis, bukan linier, yaitu satu simpul akar terhubung ke simpul anak, yang masing-masing dapat memiliki anak sendiri, bercabang ke luar seperti pohon keluarga atau bagan organisasi. Simpul tanpa anak disebut daun, dan aturan spesifik yang mengatur bagaimana simpul saling berhubungan mendefinisikan banyak variasi pohon khusus yang digunakan di seluruh ilmu komputer.

Pohon pencarian biner, salah satu varian yang paling umum dan instruktif, memberlakukan aturan pengurutan spesifik, yaitu untuk setiap simpul tertentu, setiap nilai di subpohon kirinya lebih kecil, dan setiap nilai di subpohon kanannya lebih besar. Pengurutan inilah yang membuat pohon pencarian biner benar-benar ampuh — mencari, memasukkan, atau menghapus nilai membutuhkan waktu O(log n) pada pohon yang seimbang, karena setiap perbandingan pada simpul tertentu menghilangkan sekitar setengah dari pohon yang tersisa dari pertimbangan, logika dasar yang sama di balik pencarian biner pada array yang diurutkan. Peringatan pentingnya adalah bahwa efisiensi ini sepenuhnya bergantung pada pohon yang tetap seimbang; Pohon pencarian biner yang dibangun dari data yang sudah diurutkan, tanpa penyeimbangan ulang, dapat menurun menjadi sesuatu yang berperilaku seperti daftar tertaut biasa, dengan waktu pencarian kembali ke O(n). Inilah alasan mengapa varian pohon penyeimbang otomatis — pohon AVL, pohon merah-hitam — ada, yaitu mereka secara otomatis menyusun ulang diri mereka sendiri selama penyisipan dan penghapusan untuk menjamin bahwa kinerja O(log n) tetap berlaku terlepas dari urutan data yang masuk. Secara lebih luas, pohon mendukung struktur direktori sistem file, struktur DOM yang menjadi dasar setiap halaman web, dan sistem pengindeksan database yang perlu menjaga agar sejumlah besar data dapat dicari dan diurutkan secara bersamaan.

7. Heap

Heap adalah struktur berbasis pohon khusus yang dibangun berdasarkan satu jaminan spesifik, yaitu simpul akar selalu menyimpan nilai terkecil di seluruh struktur (min-heap) atau nilai terbesar (max-heap), dan properti ini berlaku secara rekursif di setiap level, bukan hanya di puncak. Tidak seperti pohon pencarian biner, heap tidak menjanjikan urutan relatif simpul saudara atau di seluruh cabang terpisah — seluruh tujuannya adalah untuk menjawab satu pertanyaan spesifik secara efisien, "apa elemen terkecil (atau terbesar) saat ini," bukan mendukung pencarian umum di seluruh nilai sembarang.

Fokus yang sempit inilah yang membuat heap sangat efisien dalam satu hal yang menjadi tujuan pembuatannya, yaitu mengambil elemen minimum atau maksimum adalah O(1), karena selalu berada tepat di akar, sementara memasukkan elemen baru atau menghapus akar membutuhkan O(log n), karena struktur hanya perlu memulihkan properti heap-nya di sepanjang satu jalur daripada menyeimbangkan kembali seluruh struktur. Kombinasi ini menjadikan heap sebagai implementasi standar dan khusus di balik antrian prioritas, yaitu struktur data di mana elemen perlu diproses bukan berdasarkan urutan kedatangannya, tetapi berdasarkan urutan prioritas yang ditetapkan. Penjadwal tugas yang perlu selalu menjalankan pekerjaan dengan prioritas tertinggi berikutnya, dan algoritma Dijkstra untuk menemukan jalur terpendek melalui grafik berbobot, keduanya bergantung langsung pada kemampuan heap untuk mengambil elemen minimum saat ini secara efisien, berulang kali, seiring berjalannya algoritma.

8. Graph

Graph adalah struktur data yang paling umum dan fleksibel, terdiri dari simpul, yang disebut verteks, yang dihubungkan oleh hubungan, yang disebut sisi, tanpa hierarki inheren atau urutan yang diperlukan seperti yang diberlakukan oleh tree. Tree, pada kenyataannya, secara teknis hanyalah jenis grafik spesifik yang dibatasi — yang tidak memiliki siklus dan hanya memiliki satu jalur antara dua simpul. Graph sepenuhnya menghilangkan batasan tersebut, memungkinkan jaringan koneksi yang sangat kompleks: sebuah simpul dapat terhubung ke sejumlah simpul lain, sisi dapat membawa arah (hubungan satu arah) atau tidak membawa arah (hubungan timbal balik), dan sisi secara opsional dapat membawa bobot yang mewakili beberapa biaya atau jarak yang terkait dengan koneksi tertentu tersebut.

Fleksibilitas ini menjadikan graph sebagai representasi alami untuk berbagai sistem dunia nyata yang pada dasarnya tentang hubungan daripada hierarki yang ketat: jaringan sosial, di mana orang adalah verteks dan persahabatan atau pengikut adalah sisi; jaringan jalan dan aplikasi pemetaan, di mana persimpangan adalah verteks dan jalan adalah sisi berbobot yang mewakili jarak atau waktu tempuh; grafik ketergantungan yang digunakan oleh pengelola paket untuk menentukan urutan instalasi library software; dan struktur tautan dari web itu sendiri, yang pada intinya adalah grafik berarah yang sangat besar. Dua strategi dasar untuk menjelajahi graph, yaitu breadth-first search, yang menggunakan antrian dan menjelajahi level demi level ke luar, dan depth-first search, yang menggunakan tumpukan (atau rekursi, yang bergantung pada mekanisme tumpukan panggilan yang sama) dan menjelajahi sejauh mungkin di sepanjang satu jalur sebelum melakukan penelusuran balik (backtracking) — membentuk dasar bagi sebagian besar algoritma grafik yang lebih canggih yang digunakan untuk menemukan jalur terpendek, mendeteksi siklus, dan menentukan konektivitas di seluruh jaringan.

9. Trie

Trie, terkadang diucapkan "try" secara khusus untuk membedakannya dari "tree," adalah struktur pohon khusus yang dibangun untuk satu jenis data tertentu, yaitu string, dan khususnya awalan yang sama. Alih-alih menyimpan setiap string lengkap sebagai satu unit tunggal, trie memecah string karakter demi karakter, dengan setiap node mewakili satu karakter, dan jalur dari akar ke bawah melalui pohon mewakili awalan dan kata-kata lengkap yang disimpan di dalamnya. Kata-kata yang memiliki awalan yang sama — misalnya, "cat," "car," dan "card" — memiliki jalur awal yang sama melalui trie sebelum bercabang di titik di mana karakter mereka berbeda.

Struktur ini membuat trie sangat efisien untuk jenis operasi yang jauh lebih sulit ditangani oleh tabel hash atau daftar terurut, yaitu menemukan setiap kata yang dimulai dengan awalan tertentu. Mencari sebuah kata, atau memeriksa apakah ada kata dalam trie yang diawali dengan awalan tertentu, hanya membutuhkan waktu yang sebanding dengan panjang string yang dicari, sepenuhnya independen dari jumlah total kata yang terdapat dalam trie — profil kinerja yang benar-benar berbeda dan seringkali lebih unggul dibandingkan dengan memindai daftar string dan memeriksa awalan masing-masing secara individual. Inilah mengapa trie berada di balik sistem pelengkapan otomatis, pemeriksa ejaan, dan tabel perutean IP, di mana operasi spesifik dan berulang "temukan semua yang diawali dengan ini" perlu ditangani seefisien mungkin, dalam skala besar, di seluruh kosakata atau ruang alamat yang sangat besar.

10. Set

Set adalah koleksi yang memberlakukan tepat satu aturan, yaitu setiap elemen di dalamnya harus unik, tanpa duplikat yang diperbolehkan dalam keadaan apa pun. Sebagian besar implementasi praktis set sebenarnya dibangun langsung di atas tabel hash di balik layar, itulah sebabnya set biasanya mewarisi kinerja O(1) rata-rata yang sama dan berharga untuk memeriksa apakah nilai tertentu sudah ada, menambahkan nilai baru, atau menghapus nilai yang sudah ada.

Selain penegakan keunikan sederhana, set mendukung serangkaian operasi matematika yang secara langsung sesuai dengan kebutuhan pemrograman umum, yaitu seperti union (menggabungkan dua set menjadi satu, mempertahankan setiap elemen yang berbeda dari keduanya), intersection (hanya menemukan elemen yang muncul di kedua himpunan), dan difference (menemukan elemen yang ada di satu set tetapi tidak di set lainnya). Operasi-operasi ini terus-menerus muncul dalam kode nyata — menghilangkan duplikasi daftar nilai yang diambil dari berbagai sumber, secara efisien memeriksa apakah dua koleksi pengguna, tag, atau izin tumpang tindih, atau menemukan item mana yang ada dalam satu dataset tetapi hilang dari dataset lain. Set seringkali kurang dimanfaatkan dibandingkan dengan seberapa sering masalah spesifik yang mereka selesaikan — "apakah koleksi ini berisi duplikat, dan dapatkah saya memeriksa keanggotaannya secara efisien" — benar-benar muncul dalam tugas pemrograman sehari-hari.

Memilih Struktur yang Tepat untuk Pekerjaan

Melihat kesepuluh struktur data ini, pelajaran paling jelas adalah bahwa tidak ada satu pun yang secara abstrak lebih baik daripada yang lain — masing-masing mewakili serangkaian kompromi yang berbeda dan disengaja, dioptimalkan untuk pola akses dan modifikasi tertentu. Array dan tabel hash sama-sama menawarkan pencarian cepat, tetapi untuk alasan yang sepenuhnya berbeda dan di bawah batasan yang sepenuhnya berbeda, yaitu array mengharuskan kita untuk sudah mengetahui posisi numerik yang kita inginkan, sementara tabel hash memungkinkan kita untuk mencari sesuatu berdasarkan kunci yang bermakna dengan mengorbankan urutan yang terjamin. Stack dan queue sama-sama membatasi cara kita menambahkan dan menghapus elemen, dan pembatasan itulah yang membuat masing-masing menjadi pilihan yang tepat dan alami untuk kelas masalah tertentu — LIFO atau FIFO — yang sesuai dengan aturan pengurutannya.

Keterampilan praktis yang layak dibangun bukanlah menghafal karakteristik kinerja setiap struktur data secara terpisah, meskipun itu tentu saja merupakan dasar yang berguna. Yang penting adalah mengembangkan naluri untuk bertanya, untuk masalah tertentu, seperti apa pola akses dan modifikasi yang sebenarnya — apakah kita memerlukan pencarian cepat berdasarkan posisi, atau berdasarkan kunci sembarang? Apakah kita perlu berulang kali mengambil nilai minimum atau maksimum saat ini? Apakah kita perlu mengeksplorasi hubungan antar item yang tidak sesuai dengan hierarki yang ketat? — dan biarkan jawaban jujur ​​itu mengarahkan kita ke struktur yang benar-benar dibangun untuk pola tersebut, daripada menggunakan struktur mana pun yang paling familiar atau paling mudah diakses saat itu.

Jadi, struktur data adalah kosakata yang mendasari hampir semua rekayasa software, dan sepuluh struktur data yang dibahas di sini — array, linked list, stack, queue, hash table, tree, heap, graph, trie, dan set — mencakup sebagian besar pola organisasi yang muncul dalam kode produksi nyata.