VMware ESXi and vSphere Cluster Management

Struktur Data dan Algoritma (DSA): Panduan Dasar hingga Lanjutan

Pelajari struktur data dan algoritma dari dasar hingga lanjutan: kompleksitas, array, linked list, tree, graf, sorting, searching, greedy, dan dynamic programming.

Struktur Data dan Algoritma atau Data Structures and Algorithms (DSA) adalah fondasi untuk menulis program yang benar, efisien, dan mudah dikembangkan. Struktur data menentukan bagaimana data diatur, sedangkan algoritma menentukan langkah untuk memproses data tersebut.

Panduan ini ditujukan bagi pemula yang telah memahami dasar pemrograman, mahasiswa, peserta bootcamp, serta pengembang yang mempersiapkan wawancara teknis. Prasyaratnya meliputi variabel, tipe data, percabangan, perulangan, fungsi, array atau list, string, reference atau pointer, serta matematika dasar seperti logaritma dan kombinatorika sederhana.

1. Pengantar Struktur Data dan Algoritma

Apa itu struktur data?

Struktur data adalah cara mengatur dan menyimpan data agar operasi tertentu dapat dilakukan secara efektif. Array menyimpan elemen dalam urutan indeks, hash table memetakan key ke value, dan tree menyimpan hubungan hierarkis.

Algoritma adalah rangkaian langkah sistematis dan terbatas untuk menyelesaikan masalah. Algoritma yang baik menghasilkan jawaban benar, berhenti pada kondisi yang tepat, dan menggunakan sumber daya secara wajar.

ADT, tipe data primitif, dan implementasi

• Tipe data primitif adalah tipe dasar yang disediakan bahasa, seperti integer, floating-point, boolean, dan karakter.
• Abstract Data Type (ADT) adalah spesifikasi perilaku dan operasi tanpa menentukan cara implementasinya. Stack, misalnya, memiliki operasi push dan pop dengan prinsip LIFO.
• Implementasi struktur data adalah cara konkret mewujudkan ADT, misalnya stack menggunakan array dinamis atau linked list.

Pemilihan struktur data memengaruhi desain algoritma dan performa. Pencarian keanggotaan berulang dapat lebih sesuai menggunakan set daripada array. Namun, struktur yang lebih cepat tidak selalu lebih baik: keterbacaan, kemudahan pemeliharaan, ukuran input, dan biaya memori juga harus dipertimbangkan.

2. Analisis Kompleksitas

Kompleksitas waktu mengukur pertumbuhan jumlah operasi terhadap ukuran input n. Kompleksitas ruang mengukur pertumbuhan memori tambahan yang dibutuhkan. Analisis ini biasanya mengabaikan konstanta dan bagian yang pertumbuhannya lebih kecil.

Big O, Big Theta, dan Big Omega

• Big O menyatakan batas atas pertumbuhan, sering digunakan untuk membahas batas terburuk.
• Big Theta menyatakan pertumbuhan yang ketat atau seorde.
• Big Omega menyatakan batas bawah pertumbuhan.

Kasus terbaik terjadi pada input yang paling menguntungkan, kasus terburuk pada input paling merugikan, sedangkan kasus rata-rata memerlukan asumsi distribusi input.

Cara menghitung kompleksitas

• Loop tunggal yang berjalan n kali biasanya O(n).
• Dua loop berurutan dijumlahkan, misalnya O(n) + O(n) tetap O(n).
• Loop bersarang biasanya dikalikan. Loop luar dan dalam yang masing-masing berjalan n kali menghasilkan O(n²).
• Loop yang membagi ukuran masalah menjadi dua pada setiap langkah, seperti n = n / 2, menghasilkan O(log n).
• Rekursi perlu dianalisis berdasarkan jumlah pemanggilan dan pekerjaan pada setiap pemanggilan. Rekursi yang bercabang dua tanpa penyimpanan hasil dapat mencapai O(2^n).

Operasi struktur data bergantung pada implementasi dan kondisi. Akses array umumnya O(1), pencarian array O(n), pencarian rata-rata hash table O(1), dan traversal tree O(n). Pada BST yang seimbang, pencarian rata-rata atau terburuk yang terjamin dapat O(log n), tetapi BST yang miring dapat menjadi O(n).

Memori tambahan dapat ditukar dengan waktu. Memoization menyimpan hasil submasalah agar tidak dihitung ulang, tetapi membutuhkan ruang ekstra. Sebaliknya, solusi in-place dapat menghemat memori dengan kemungkinan kode lebih rumit.

3. Array, String, dan Matriks

Array menyimpan elemen pada posisi berindeks. Traversal membaca elemen satu per satu, pembaruan mengubah nilai pada indeks, sedangkan penyisipan atau penghapusan di tengah biasanya memerlukan pergeseran.

Array statis memiliki ukuran tetap. Array dinamis dapat membesar ketika kapasitas penuh, biasanya dengan mengalokasikan ruang baru dan menyalin elemen. Karena sebagian besar penambahan tidak memerlukan penyalinan, append pada array dinamis sering dianalisis sebagai O(1) amortisasi.

String dan matriks

String adalah urutan karakter. Perhatikan encoding seperti UTF-8 karena satu karakter visual dapat terdiri dari beberapa unit kode. Beberapa bahasa memperlakukan string sebagai immutable, sehingga penggabungan berulang dapat membuat banyak objek baru.

Matriks adalah array dua dimensi. Traversal baris demi baris menggunakan dua indeks, sedangkan traversal diagonal perlu aturan indeks seperti row == column. Pada grid, selalu periksa batas baris dan kolom sebelum mengakses tetangga.

Pola penting pada array

• Two pointers: dua indeks bergerak dari kiri dan kanan atau searah untuk menghindari loop bersarang.
• Sliding window: mempertahankan interval berjalan untuk mencari subarray atau substring yang memenuhi syarat.
• Prefix sum: menyimpan jumlah kumulatif agar query jumlah rentang dapat dijawab cepat; setelah preprocessing O(n), query biasanya O(1).
• Difference array: menyimpan perubahan pada batas interval sehingga banyak operasi range update dapat diproses secara efisien.

Contoh mencari nilai terbesar dan frekuensinya:

terbesar = -infinity
frekuensi = {}
untuk setiap x dalam data:
    jika x > terbesar:
        terbesar = x
    frekuensi[x] = frekuensi.get(x, 0) + 1

Traversal tersebut membutuhkan O(n) waktu dan O(k) ruang, dengan k sebagai jumlah nilai berbeda.

4. Linked List

Linked list tersusun dari node. Node menyimpan data dan reference atau pointer ke node lain. Head menunjuk node pertama, sedangkan tail biasanya menunjuk node terakhir.

• Singly linked list memiliki pointer ke node berikutnya.
• Doubly linked list memiliki pointer berikutnya dan sebelumnya, sehingga traversal dua arah lebih mudah.
• Circular linked list menghubungkan node terakhir kembali ke node pertama.

Traversal linked list dimulai dari head dan mengikuti reference hingga null atau kembali ke head pada bentuk circular. Menyisipkan di awal dapat O(1). Menyisipkan di akhir O(1) jika tail tersedia, tetapi menemukan posisi tertentu tetap O(n). Linked list unggul untuk perubahan lokal tanpa menggeser elemen, tetapi buruk untuk akses acak dan menggunakan memori tambahan untuk pointer.

Manipulasi dan deteksi siklus

Membalik linked list dilakukan dengan tiga reference: previous, current, dan next. Simpan node berikutnya sebelum mengubah pointer agar sisa list tidak hilang.

Teknik fast-slow pointers menggunakan pointer lambat yang maju satu langkah dan pointer cepat yang maju dua langkah. Jika keduanya bertemu, list memiliki siklus. Teknik ini memakai O(1) ruang tambahan.

5. Stack, Queue, Deque, dan Priority Queue

Stack mengikuti LIFO, yaitu elemen terakhir masuk menjadi elemen pertama keluar. Operasinya adalah push, pop, dan peek atau top. Stack dapat digunakan untuk validasi tanda kurung, undo/redo, evaluasi ekspresi, dan DFS.

Queue mengikuti FIFO, yaitu elemen pertama masuk menjadi elemen pertama keluar. Operasinya adalah enqueue, dequeue, front, dan rear. Queue digunakan dalam penjadwalan dan BFS.

Deque atau double-ended queue mendukung penambahan dan penghapusan dari kedua ujung. Circular queue memakai kembali slot array yang telah kosong dengan indeks melingkar. Priority queue selalu mengeluarkan elemen dengan prioritas tertinggi atau terendah, biasanya menggunakan heap.

Pilih implementasi array ketika akses lokal dan cache-friendly penting. Gunakan linked list jika penyisipan atau penghapusan di node yang sudah diketahui lebih dominan dan overhead reference dapat diterima.

6. Hash Table dan Set

Hash table menyimpan pasangan key-value. Hash function mengubah key menjadi angka yang menentukan bucket. Operasi utamanya adalah lookup, insert, update, dan delete.

Collision terjadi ketika beberapa key menuju bucket yang sama. Chaining menyimpan beberapa entri dalam bucket, sedangkan open addressing mencari slot lain menggunakan strategi seperti probing.

Load factor adalah rasio jumlah elemen terhadap kapasitas tabel. Jika terlalu tinggi, collision meningkat dan tabel biasanya melakukan resizing: kapasitas diperbesar dan entri di-hash ulang. Dengan hash function dan kapasitas yang baik, operasi rata-rata adalah O(1), meskipun kasus terburuk dapat lebih lambat.

Dictionary atau map menyimpan key yang dipetakan ke value. Set hanya menyimpan keanggotaan nilai tanpa value terpisah. Keduanya berguna untuk pencarian cepat, frequency counting, dan deduplikasi.

7. Tree, Binary Search Tree, dan Heap

Dalam tree, root adalah node teratas. Parent memiliki child, node pada tingkat yang sama disebut sibling, dan node tanpa child disebut leaf. Depth adalah jarak node dari root, height adalah jarak terpanjang menuju leaf, dan subtree adalah tree yang berakar pada node tertentu.

Binary tree memiliki paling banyak dua child per node. Pada Binary Search Tree (BST), nilai di subtree kiri lebih kecil dan nilai di subtree kanan lebih besar menurut aturan pembanding. Inorder traversal BST menghasilkan data terurut.

Traversal tree

• Preorder: node, kiri, kanan; berguna untuk menyalin struktur.
• Inorder: kiri, node, kanan; menghasilkan urutan terurut pada BST.
• Postorder: kiri, kanan, node; berguna untuk menghapus subtree.
• Level order: berdasarkan tingkat menggunakan queue.

Pencarian, penyisipan, dan penghapusan BST mengikuti perbandingan dari root. Jika tree seimbang, operasinya O(log n). Jika semua node condong ke satu sisi, tree menyerupai linked list dan menjadi O(n). AVL tree menjaga perbedaan tinggi subtree dengan ketat, sedangkan red-black tree memakai aturan warna untuk menjaga keseimbangan secara lebih longgar. Keduanya menjaga operasi logaritmik.

Heap adalah complete binary tree. Pada min-heap, parent tidak lebih besar daripada child; pada max-heap, parent tidak lebih kecil daripada child. Heap cocok untuk mengambil elemen prioritas, tetapi tidak mendukung pencarian arbitrary secara cepat.

8. Heap dan Priority Queue secara Praktis

Heap biasanya direpresentasikan dalam array. Dengan indeks berbasis nol, child kiri node i berada di 2i + 1, child kanan di 2i + 2, dan parent di (i - 1) // 2.

• Heapify up memperbaiki heap setelah insertion, dengan kompleksitas O(log n).
• Heapify down memperbaiki heap setelah extraction, dengan kompleksitas O(log n).
• Melihat elemen teratas adalah O(1).
• Build heap dari array dapat dilakukan dalam O(n), bukan O(n log n).

Priority queue berguna untuk penjadwalan, mencari top-k elemen, menghitung median aliran data dengan dua heap, serta mendukung Dijkstra dan algoritma graf lainnya.

9. Trie dan Struktur Data Khusus

Trie atau prefix tree menyimpan karakter pada jalur dari root. Trie cocok untuk autocomplete, pencarian kata, dan query berdasarkan prefiks. Waktu operasi dipengaruhi panjang kata, bukan langsung jumlah kata.

Fenwick tree atau Binary Indexed Tree mendukung pembaruan satu posisi dan query prefix sum secara O(log n) dengan ruang O(n). Segment tree mendukung range query dan update dengan O(log n), serta dapat dikembangkan untuk operasi seperti minimum, maksimum, atau jumlah.

Union-find atau Disjoint Set Union (DSU) mengelola kelompok elemen yang saling terhubung. Operasi find dan union menjadi sangat cepat secara amortisasi dengan path compression dan union by rank atau size. DSU sering dipakai untuk connected components dan Kruskal.

Pilih struktur khusus berdasarkan pola query dan update. Jika hanya perlu prefix sum statis, prefix sum biasa lebih sederhana. Jika data sering diperbarui, Fenwick tree atau segment tree lebih sesuai. Jika masalahnya menggabungkan komponen, gunakan DSU.

10. Graf

Graf terdiri dari vertex atau node dan edge yang menghubungkan pasangan node. Istilah penting lainnya adalah derajat, bobot, jalur, siklus, dan komponen terhubung. Graf dapat berarah atau tak berarah, berbobot atau tidak berbobot.

Adjacency list menyimpan daftar tetangga setiap node dan hemat ruang untuk graf sparse. Adjacency matrix menyimpan tabel koneksi dan menyediakan pemeriksaan edge O(1), tetapi membutuhkan O(V²) ruang.

BFS dan DFS

Breadth-First Search (BFS) mengunjungi graf per tingkat menggunakan queue. Pada graf tak berbobot, BFS menemukan jalur terpendek berdasarkan jumlah edge. Depth-First Search (DFS) menjelajah sedalam mungkin menggunakan recursion atau stack eksplisit. Keduanya umumnya memiliki kompleksitas O(V + E) dengan adjacency list.

BFS dan DFS dapat digunakan untuk connected components, deteksi siklus, serta pengujian bipartite graph dengan pewarnaan dua kelompok. Untuk graf berarah, DFS juga membantu menemukan back edge sebagai indikasi siklus.

Topological sort dan jalur terpendek

Topological sort mengurutkan vertex pada Directed Acyclic Graph (DAG) sehingga setiap prasyarat muncul sebelum dependennya. Algoritma dapat memakai indegree dan queue atau DFS. Contohnya adalah menentukan urutan mata kuliah berdasarkan prasyarat.

Minimum spanning tree menghubungkan seluruh vertex tanpa siklus dengan total bobot minimum. Kruskal mengurutkan edge dan menggunakan DSU, sedangkan Prim memperluas tree dari vertex awal menggunakan priority queue.

11. Algoritma Pencarian

Linear search memeriksa elemen satu per satu dan memiliki kompleksitas O(n). Binary search membagi ruang pencarian menjadi dua sehingga membutuhkan data terurut atau kondisi yang monoton.

Variasi binary search meliputi lower bound, yaitu posisi pertama dengan nilai minimal tertentu, dan upper bound, yaitu posisi pertama dengan nilai lebih besar dari target. Binary search juga dapat mencari jawaban pada ruang nilai jika predikatnya monoton, misalnya kapasitas minimum yang membuat jadwal dapat selesai.

Pada array terrotasi, tentukan bagian kiri atau kanan yang masih terurut, lalu periksa apakah target berada dalam rentang bagian tersebut. Untuk nilai dengan batas tertentu, tetapkan invariant yang jelas: bagian mana yang mungkin masih berisi jawaban.

12. Algoritma Pengurutan

Stabilitas berarti elemen dengan key sama mempertahankan urutan awal. Ini penting saat sorting bertingkat. In-place berarti algoritma menggunakan ruang tambahan kecil di luar input. Quicksort, merge sort, dan heap sort memiliki trade-off berbeda antara stabilitas, memori, dan jaminan worst case.

13. Rekursi dan Backtracking

Fungsi rekursif memanggil dirinya sendiri. Setiap rekursi harus memiliki base case yang menghentikan pemanggilan dan recursive case yang mendekatkan input ke base case.

f(n):
    jika n adalah base case:
        kembalikan nilai dasar
    kembalikan gabungkan(f(submasalah), n)

Setiap pemanggilan disimpan pada call stack. Base case yang salah atau kedalaman terlalu besar dapat menyebabkan stack overflow. Solusi rekursif dapat diubah menjadi iteratif dengan loop atau stack eksplisit.

Backtracking membangun kandidat secara bertahap, memeriksa apakah kandidat masih valid, lalu membatalkan pilihan ketika perlu. Teknik ini cocok untuk kombinasi, permutasi, subset, maze, dan constraint problems. Pruning membuang cabang yang sudah pasti tidak menghasilkan solusi sehingga ruang pencarian lebih kecil.

14. Divide and Conquer, Greedy, dan Dynamic Programming

Divide and conquer memecah masalah menjadi bagian lebih kecil, menyelesaikannya, lalu menggabungkan hasil. Greedy memilih opsi terbaik saat ini. Greedy hanya valid jika dapat dibuktikan bahwa pilihan lokal tidak merusak solusi optimal.

Dynamic programming (DP) digunakan ketika submasalah yang sama muncul berulang dan solusi optimal tersusun dari solusi optimal submasalah. Memoization menyimpan hasil saat rekursi berjalan, sedangkan tabulation mengisi tabel dari kasus dasar menuju state akhir.

1. Definisikan state, yaitu informasi minimum yang mewakili submasalah.
2. Tentukan transition, yaitu hubungan state dengan state sebelumnya.
3. Tentukan base case.
4. Tentukan urutan perhitungan untuk tabulation.
5. Evaluasi optimasi memori, misalnya menyimpan hanya baris atau state sebelumnya.

Contoh jumlah cara mencapai anak tangga dapat memakai dp[i] = dp[i - 1] + dp[i - 2]. Masalah knapsack sederhana dapat memakai state berdasarkan indeks item dan kapasitas tersisa.

15. Strategi Pemecahan Masalah DSA

1. Baca batasan input dan format output. Nilai n kecil mungkin mengizinkan brute force, sedangkan n besar membutuhkan pola lebih efisien.
2. Buat brute force sebagai baseline untuk memahami masalah dan menguji solusi yang dioptimalkan.
3. Cari pola: frequency counting, two pointers, sliding window, prefix sum, monotonic stack, binary search, traversal graf, atau DP.
4. Tulis invariant atau alasan informal mengapa setiap langkah mempertahankan kebenaran solusi.
5. Uji edge case: input kosong, satu elemen, duplikasi, nilai ekstrem, data sudah terurut, semua nilai sama, dan input besar.
6. Hitung kompleksitas waktu dan ruang akhir, lalu bandingkan dengan batas yang tersedia.

16. Implementasi, Pengujian, dan Praktik Kode

Tulis pseudocode sebelum implementasi. Pseudocode membantu memisahkan ide algoritma dari sintaks bahasa. Setelah itu, gunakan struktur data dari standard library jika sudah memenuhi kebutuhan; implementasi manual sebaiknya dilakukan untuk belajar atau ketika kebutuhan khusus memang menuntutnya.

• Gunakan nama variabel yang menjelaskan makna, bukan hanya a atau x.
• Pecah solusi menjadi fungsi atau modul kecil dengan tanggung jawab jelas.
• Dokumentasikan asumsi seperti data terurut, bobot non-negatif, indeks berbasis nol, atau batas kapasitas.
• Bandingkan solusi berdasarkan kebenaran, kompleksitas, penggunaan memori, dan keterbacaan.

Checklist pengujian dan debugging

• Uji kasus normal, kosong, satu elemen, duplikasi, nilai ekstrem, dan input besar.
• Periksa kesalahan indeks, null reference, overflow integer, kondisi batas, dan mutasi data yang tidak disengaja.
• Untuk binary search, pastikan input terurut, pembaruan batas benar, dan gunakan rumus tengah seperti left + (right - left) // 2 untuk menghindari overflow.
• Untuk rekursi, pastikan base case tercapai dan parameter berubah menuju base case. Gunakan solusi iteratif atau stack eksplisit jika kedalaman besar.
• Untuk BFS atau DFS, gunakan struktur visited, tandai node pada waktu yang tepat, dan periksa arah serta seluruh adjacency.
• Untuk Dijkstra, pastikan tidak ada bobot negatif, abaikan entri priority queue yang sudah kedaluwarsa, dan inisialisasi jarak dengan benar. Gunakan Bellman-Ford untuk bobot negatif.
• Jika hash table lambat, periksa collision, load factor, resizing, dan konsistensi representasi key.
• Jika DP melebihi batas waktu atau memori, cari state yang berulang, gunakan memoization atau tabulation, dan kompres dimensi jika hanya state sebelumnya yang diperlukan.

17. Contoh Konsep yang Sering Muncul

Validasi tanda kurung

Gunakan stack. Saat menemukan tanda buka, lakukan push. Saat menemukan tanda tutup, periksa apakah top adalah pasangan yang sesuai lalu lakukan pop. Ekspresi valid jika stack kosong setelah semua karakter diproses.

Subarray terpanjang dengan batas jumlah

Untuk bilangan non-negatif, sliding window dapat memperluas right dan menggeser left ketika jumlah melebihi batas. Setiap pointer bergerak paling banyak n kali sehingga kompleksitasnya O(n). Untuk bilangan negatif, asumsi ini tidak berlaku secara umum dan teknik lain mungkin diperlukan.

Posisi pertama dan terakhir target

Jalankan binary search dua kali: lower bound mencari posisi pertama yang nilainya setidaknya target, sedangkan upper bound mencari posisi pertama yang lebih besar dari target. Rentang kemunculan target kemudian adalah dari lower bound hingga satu posisi sebelum upper bound.

Rute minimum dan prasyarat

Gunakan Dijkstra untuk peta dengan bobot jalan non-negatif dan priority queue untuk memilih jarak terkecil. Gunakan topological sort untuk urutan mata kuliah pada DAG. Jika prasyarat membentuk siklus, tidak ada urutan valid yang menyelesaikan semuanya.

18. Ringkasan Belajar

Mulailah dari array, string, kompleksitas, stack, queue, hash map, sorting, dan binary search. Lanjutkan ke linked list, tree, heap, graf, rekursi, backtracking, greedy, dan DP. Pada setiap topik, pahami operasi, invariant, kompleksitas, implementasi, serta edge case.

DSA bukan sekadar menghafal algoritma. Tujuan utamanya adalah mengenali bentuk masalah, memilih representasi data yang sesuai, membuktikan solusi secara masuk akal, mengukur biaya waktu dan memori, lalu menulis kode yang benar serta dapat dipelihara. Pelajari topik terkait seperti struktur data dan algoritma lainnya sambil berlatih dengan variasi input yang berbeda.