Memilih Struktur Data

Section ini telah membawa kita jauh: dari Big-O, dynamic array, linked list, stack dan queue, sampai hash table, tree, heap, graph, dan keluarga algoritma pencarian, sorting, backtracking, greedy, divide and conquer, dan dynamic programming. Pengetahuan itu baru bernilai penuh ketika bisa memutuskan. Pertanyaan yang benar jarang berbunyi “struktur mana yang paling cepat”, melainkan “struktur mana yang paling cocok untuk pola akses data kita”. Chapter penutup ini menjalankan satu eksperimen nyata pada empat struktur, menyusun tabel keputusan lengkap dengan padanan STL, lalu merangkum seluruh perjalanan dan menunjuk arah section berikutnya.

Satu Beban Kerja, Empat Struktur #

Eksperimennya sederhana dan jujur: 4096 elemen, 32 pencarian (16 target yang ada, 16 yang tidak), diulang pada empat struktur berbeda. Agar hasilnya deterministik, pengacakan memakai LCG (linear congruential generator) dengan seed tetap — bukan rand() yang bisa berubah antar mesin:

// Demo pemilihan struktur data: satu beban kerja pencarian, empat struktur.
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

struct Node {
    int data;
    Node* kiri;
    Node* kanan;
};

// Insert BST iteratif: tanpa rekursi, aman untuk input terurut yang panjang.
void insertBst(Node*& akar, int nilai) {
    Node* baru = new Node{nilai, nullptr, nullptr};
    if (akar == nullptr) {
        akar = baru;
        return;
    }
    Node* kini = akar;
    while (true) {
        if (nilai < kini->data) {
            if (kini->kiri == nullptr) { kini->kiri = baru; return; }
            kini = kini->kiri;
        } else if (nilai > kini->data) {
            if (kini->kanan == nullptr) { kini->kanan = baru; return; }
            kini = kini->kanan;
        } else {
            delete baru;  // duplikat diabaikan
            return;
        }
    }
}

// Search BST iteratif: setiap langkah membuang satu cabang.
bool cariBst(Node* akar, int target, long long& langkah) {
    Node* kini = akar;
    langkah = 0;
    while (kini != nullptr) {
        ++langkah;
        if (target == kini->data) return true;
        kini = (target < kini->data) ? kini->kiri : kini->kanan;
    }
    return false;
}

void hapusBst(Node* node) {  // post-order: anak dulu, baru node
    if (node == nullptr) return;
    hapusBst(node->kiri);
    hapusBst(node->kanan);
    delete node;
}

// Linear search pada vector tak terurut, dengan penghitung perbandingan.
bool cariLinear(const std::vector<int>& data, int target, long long& langkah) {
    langkah = 0;
    for (int nilai : data) {
        ++langkah;
        if (nilai == target) return true;
    }
    return false;
}

// Binary search pada vector terurut.
bool cariBiner(const std::vector<int>& data, int target, long long& langkah) {
    int lo = 0, hi = static_cast<int>(data.size()) - 1;
    langkah = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        ++langkah;
        if (data[mid] == target) return true;
        if (data[mid] < target) lo = mid + 1;
        else                    hi = mid - 1;
    }
    return false;
}

int main() {
    const int N = 4096;
    // Buat deret 0..4095 lalu acak secara deterministik (LCG seed tetap).
    std::vector<int> acak;
    acak.reserve(N);
    for (int i = 0; i < N; ++i) acak.push_back(i);
    unsigned long long benih = 12345;
    for (int i = N - 1; i > 0; --i) {
        benih = benih * 6364136223846793005ULL + 1442695040888963407ULL;
        int j = static_cast<int>((benih >> 33) % static_cast<unsigned long long>(i + 1));
        std::swap(acak[i], acak[j]);
    }

    // Beban kerja: 32 pencarian (16 target ada, 16 target tidak ada).
    std::vector<int> target;
    for (int k = 0; k < 16; ++k) target.push_back(256 * k + 3);
    for (int k = 0; k < 16; ++k) target.push_back(5000 + 256 * k);

    // Struktur 1 dan 2: vector tak terurut vs vector terurut.
    std::vector<int> terurut = acak;
    std::sort(terurut.begin(), terurut.end());
    long long totalLinear = 0, totalBiner = 0, langkah = 0;
    for (int t : target) {
        cariLinear(acak, t, langkah);    totalLinear += langkah;
        cariBiner(terurut, t, langkah);  totalBiner += langkah;
    }

    // Struktur 3: BST dari input acak (cenderung seimbang).
    Node* akarAcak = nullptr;
    for (int nilai : acak) insertBst(akarAcak, nilai);
    long long totalBstAcak = 0;
    for (int t : target) {
        cariBst(akarAcak, t, langkah);
        totalBstAcak += langkah;
    }

    // Struktur 4: BST dari input terurut (degenerate: rantai satu arah).
    Node* akarRantai = nullptr;
    for (int nilai : terurut) insertBst(akarRantai, nilai);
    long long totalBstRantai = 0;
    for (int t : target) {
        cariBst(akarRantai, t, langkah);
        totalBstRantai += langkah;
    }

    std::cout << "Beban kerja: " << target.size()
              << " pencarian pada " << N << " elemen\n";
    std::cout << "vector tak terurut (linear search) : "
              << totalLinear << " perbandingan\n";
    std::cout << "vector terurut      (binary search): "
              << totalBiner << " perbandingan\n";
    std::cout << "BST dari input acak                : "
              << totalBstAcak << " perbandingan\n";
    std::cout << "BST dari input terurut (degenerate): "
              << totalBstRantai << " perbandingan\n";

    hapusBst(akarAcak);
    hapusBst(akarRantai);
    return 0;
}

Output yang Dihasilkan:

Beban kerja: 32 pencarian pada 4096 elemen
vector tak terurut (linear search) : 104445 perbandingan
vector terurut      (binary search): 368 perbandingan
BST dari input acak                : 412 perbandingan
BST dari input terurut (degenerate): 96320 perbandingan

Bedah baris penting:

1. Baris 84-89: Fisher-Yates shuffle dengan LCG seed tetap — urutan acak yang sama persis di setiap eksekusi, syarat angka pembanding yang adil.
2. Baris 93-94: daftar target sengaja mencampur yang ada (indeks 256k+3) dan yang tidak ada (5000 ke atas) — skenario “tidak ditemukan” adalah yang paling mahal dan tidak boleh dilewatkan.
3. Baris 99-102: struktur pertama dan kedua diuji pada data yang sama: vector tak terurut untuk linear search, dan salinannya yang diurutkan untuk binary search.
4. Baris 106-111: BST ketiga dibangun dari urutan acak; insert dan carinya iteratif dengan penghitung langkah.
5. Baris 115-120: BST keempat menerima input yang sama tetapi dalam urutan terurut — memicu skenario degenerate dari chapter Binary Search Tree.
6. Baris 134-135: hapusBst membersihkan kedua tree secara post-order; struktur manual tetap menuntut kebersihan memori.

Baca angkanya dengan teliti, karena keempatnya mengajarkan hal yang berbeda. Binary search butuh 368 perbandingan lawan 104.445 untuk linear search — selisih ratusan kali hanya dari satu keputusan (mengurutkan data sekali). BST dari input acak sekelas dengan binary search (412) — tree yang cenderung seimbang memang berkinerja seperti yang dijanjikan teorinya. Dan BST dari input terurut mencapai 96.320 — hampir selambat linear search, meskipun “struktur yang sama” dengan BST acak. Struktur yang sama bisa hebat atau buruk tergantung pola data yang masuk; itu inti dari seluruh section ini.

Tabel Keputusan: Kebutuhan, Struktur, dan Padanan STL #

Tabel berikut merangkum seluruh section menjadi satu halaman rujukan. Kolom pertama adalah kebutuhan yang Anda rasakan, bukan nama struktur — karena keputusan selalu mulai dari masalah:

Dua baris terakhir tabel patut mendapat sorotan ekstra. Pilihan “vector terurut + binary search” sering terlupakan padahal sangat praktis: bila data jarang berubah tetapi sering dicari, mengurutkan sekali lalu memakai std::lower_bound mengalahkan std::map untuk data berukuran sedang, berkat memori yang rapat dan ramah cache. Dan untuk graph, STL tidak menyediakan class khusus — std::vector<std::vector<int>> untuk adjacency list adalah konvensi yang dipakai hampir semua kode C++.

Pertimbangan Pola Akses #

Tabel di atas memberi kandidat; pola akses yang menentukan pemenangnya. Pertanyaan-pertanyaan berikut adalah daftar periksa yang bisa dibawa ke masalah apa pun:

• Dominan baca atau dominan tulis? Data yang jarang berubah cocok untuk struktur yang “mengatur dulu, cepat selamanya” (vector terurut, BST). Data yang berhembus-hembus per detik lebih cocok untuk struktur yang murah saat menulis (vector dengan push_back, hash table).
• Berapa ukurannya? Pada ratusan elemen, cache CPU membuat vector sederhana hampir selalu menang; kecanggihan O(log n) baru terasa pada ribuan ke atas.
• Bagaimana urutan kedatangan data? Input terurut menghukum BST biasa (degenerate) tetapi tidak mengganggu hash table sama sekali.
• Apakah urutan iterasi penting? Bila perlu menelusuri data terurut, std::unordered_map menuntut langkah tambahan menyimpan urutan; std::map memberinya gratis.
• Ada duplikat? set menolaknya, multiset/multimap menerima — keputusan kecil yang menghindari perbaikan menyakitkan di kemudian hari.
• Berapa sering pencarian terjadi? Pencarian sekali pada 100 elemen tidak butuh struktur apa pun; linear search saja selesai lebih cepat daripada waktu yang habis untuk membangun indeks.

Rangkuman Section dan Langkah Berikutnya #

Perjalanan 20 chapter section ini bisa dirangkum dalam satu alur: Big-O dan kompleksitas memberi bahasa untuk mengukur; array, linked list, stack, dan queue membentuk fondasi linear; hash table, tree, BST, dan heap menyerang masalah pencarian dan prioritas; graph memodelkan hubungan yang tak berhierarki; lalu keluarga algoritma — linear dan binary search, sorting, backtracking, greedy, divide and conquer, dynamic programming, Dijkstra — mengubah struktur data menjadi jawaban. Setiap chapter menulis implementasinya sendiri, dan kebiasaan itu bukan latihan kosong: memahami cara kerja dari dalam membuat Anda tahu kapan library cukup dan kapan tidak.

Algoritma yang benar di atas kertas masih bisa salah di kode nyata: indeks keluar batas, pointer menggantung, cache invalid menyebabkan hasil aneh di komputer tertentu. Itulah wilayah section berikutnya — Debugging dan Code Quality — yang mengajarkan compiler warnings, sanitizers, dan unit testing supaya kode yang kita bangun dengan struktur data yang tepat juga terbukti benar, bukan sekadar terlihat benar.

Rujukan resmi: Containers library , Algorithms library , dan std::map .