Memilih Struktur Data

Setelah mempelajari beragam struktur data—array, linked list, stack, queue, hash table, BST, heap, graph—muncul pertanyaan: bagaimana memilih yang tepat untuk masalah tertentu? Tidak ada struktur data “terbaik” untuk semua skenario—setiap pilihan punya tradeoff antara waktu, memori, dan kompleksitas implementasi. Pada chapter ini kita akan menyusun decision matrix yang membandingkan struktur-struktur data berdasarkan kriteria operasi yang penting, lalu memetakan skenario umum ke pilihan struktur yang tepat.

Kriteria Memilih Struktur Data #

Sebelum memilih, identifikasi operasi mana yang paling sering dipakai. Struktur data optimal untuk satu operasi bisa jelek untuk operasi lain. Beberapa kunci pertanyaan:

Akses acak: apakah kita sering mengakses elemen ke-k?
Insert di mana: depan, belakang, atau tengah?
Delete di mana: depan, belakang, atau tengah?
Search: apakah kita perlu mencari berdasarkan nilai?
Memori: apakah memori terbatas?
Ukuran data: tetap atau dinamis?
Stabilitas: apakah urutan relatif elemen sama harus dipertahankan?

Jawaban atas pertanyaan-pertanyaan ini mempersempit pilihan. Sebagai contoh, bila akses acak adalah kebutuhan utama, array menang. Bila insert di depan sering dilakukan, linked list menang. Bila search cepat adalah prioritas, hash table atau BST adalah pilihan.

Perbandingan Operasi Lookup #

Kita akan membandingkan tiga struktur data: array, linked list, dan hash table. Implementasi sederhana untuk lookup string. Bandingkan kompleksitasnya.

c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    char *kunci;
    int nilai;
    struct node *next;
} node;

#define UKURAN_TABEL 32

static char *dup_str(const char *s) {
    size_t n = strlen(s) + 1;
    char *p = malloc(n);
    if (p != NULL) memcpy(p, s, n);
    return p;
}

static unsigned hash_str(const char *str) {
    unsigned h = 5381;
    int c;
    while ((c = (unsigned char)*str++) != 0) {
        h = ((h << 5) + h) + (unsigned)c;
    }
    return h;
}

/* Array lookup: linear search */
int cari_array(const char **arr, int n, const char *target) {
    for (int i = 0; i < n; i++) {
        if (strcmp(arr[i], target) == 0) return i;
    }
    return -1;
}

/* Linked list lookup */
int cari_list(node *kepala, const char *target) {
    int idx = 0;
    while (kepala != NULL) {
        if (strcmp(kepala->kunci, target) == 0) return idx;
        kepala = kepala->next;
        idx++;
    }
    return -1;
}

/* Hash table lookup */
typedef struct {
    node *bucket[UKURAN_TABEL];
} hash_table;

int ht_get(hash_table *ht, const char *kunci) {
    unsigned h = hash_str(kunci) % UKURAN_TABEL;
    node *cur = ht->bucket[h];
    while (cur != NULL) {
        if (strcmp(cur->kunci, kunci) == 0) return cur->nilai;
        cur = cur->next;
    }
    return -1;
}

void ht_set(hash_table *ht, const char *kunci, int nilai) {
    unsigned h = hash_str(kunci) % UKURAN_TABEL;
    node *n = malloc(sizeof(node));
    n->kunci = dup_str(kunci);
    n->nilai = nilai;
    n->next = ht->bucket[h];
    ht->bucket[h] = n;
}

void ht_hapus_semua(hash_table *ht) {
    for (int i = 0; i < UKURAN_TABEL; i++) {
        node *cur = ht->bucket[i];
        while (cur != NULL) {
            node *tmp = cur->next;
            free(cur->kunci);
            free(cur);
            cur = tmp;
        }
        ht->bucket[i] = NULL;
    }
}

void list_hapus_semua(node *kepala) {
    while (kepala != NULL) {
        node *tmp = kepala->next;
        free(kepala->kunci);
        free(kepala);
        kepala = tmp;
    }
}

int main(void) {
    const char *data_kunci[] = {"Budi", "Siti", "Andi", "Wati", "Rina"};
    int data_nilai[] = {100, 200, 300, 400, 500};
    int n = 5;

    const char **arr = malloc(sizeof(char *) * (size_t)n);
    node *list = NULL;
    hash_table ht;
    for (int i = 0; i < UKURAN_TABEL; i++) ht.bucket[i] = NULL;

    for (int i = 0; i < n; i++) {
        arr[i] = data_kunci[i];

        node *nnode = malloc(sizeof(node));
        nnode->kunci = dup_str(data_kunci[i]);
        nnode->nilai = data_nilai[i];
        nnode->next = list;
        list = nnode;

        ht_set(&ht, data_kunci[i], data_nilai[i]);
    }

    printf("Cari 'Wati':\n");
    int idx_a = cari_array(arr, n, "Wati");
    printf("  Array       : indeks %d (kompleksitas O(n))\n", idx_a);
    int idx_l = cari_list(list, "Wati");
    printf("  Linked list : indeks %d (kompleksitas O(n))\n", idx_l);
    int val_h = ht_get(&ht, "Wati");
    printf("  Hash table  : nilai %d (kompleksitas O(1) rata-rata)\n", val_h);

    free(arr);
    list_hapus_semua(list);
    ht_hapus_semua(&ht);

    return 0;
}

Output yang Dihasilkan:

text
Cari 'Wati':
  Array       : indeks 3 (kompleksitas O(n))
  Linked list : indeks 1 (kompleksitas O(n))
  Hash table  : nilai 400 (kompleksitas O(1) rata-rata)

Tiga struktur data menyimpan data yang sama, tetapi lookup memberi kompleksitas berbeda. Array dan linked list sama-sama O(n) karena harus traversal elemen satu per satu. Hash table O(1) rata-rata karena hash function langsung menentukan bucket.

Mari kita telaah baris-baris kode di atas:

Baris 33-39 (cari_array): linear search pada array of string. strcmp membandingkan setiap elemen. Kompleksitas O(n * m) di mana n = elemen, m = panjang string rata-rata.
Baris 42-51 (cari_list): traversal linked list dengan counter indeks. Kompleksitas O(n).
Baris 56-65 (ht_get): hash function djb2 menghasilkan indeks bucket, lalu traversal pendek chain (biasanya panjang 1-2 bila load factor rendah). Kompleksitas O(1) rata-rata, O(n) worst case bila hash function buruk.
Baris 67-75 (ht_set): insert depan chain bucket. Kompleksitas O(1).
Baris 102-110 (bangun 3 struktur): kode repetitif untuk konversi array statis ke tiga struktur data berbeda. Pada produksi, gunakan helper function agar tidak duplikasi.

Decision Matrix Skor #

Kita akan menyusun matrix skor untuk membantu keputusan. Setiap sel berisi skor 1-5 (5 terbaik) untuk kriteria operasi tertentu.

c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    const char *nama;
    int akses_acak;
    int insert_depan;
    int insert_belakang;
    int hapus;
    int memori;
    int search;
} struktur_data;

int skor_total(struktur_data *s) {
    return s->akses_acak + s->insert_depan + s->insert_belakang +
           s->hapus + s->memori + s->search;
}

void cetak_skor(struktur_data *s) {
    printf("  %-15s akses=%d insert_depan=%d insert_belakang=%d hapus=%d memori=%d search=%d -> total=%d\n",
           s->nama, s->akses_acak, s->insert_depan, s->insert_belakang,
           s->hapus, s->memori, s->search, skor_total(s));
}

int main(void) {
    struktur_data daftar[] = {
        {"Array",          5, 1, 5, 1, 5, 1},
        {"Linked List",    1, 5, 2, 4, 2, 2},
        {"Hash Table",     1, 4, 4, 3, 1, 5},
        {"BST",            1, 3, 3, 3, 2, 4},
        {"Heap",           1, 2, 2, 4, 4, 1},
        {"Circular Buffer",2, 1, 1, 1, 5, 1},
    };
    int n = sizeof(daftar) / sizeof(daftar[0]);

    printf("Decision matrix (skor 1-5, 5 terbaik):\n");
    for (int i = 0; i < n; i++) cetak_skor(&daftar[i]);

    printf("\nSkenario: butuh akses acak + search cepat:\n");
    for (int i = 0; i < n; i++) {
        int skor = daftar[i].akses_acak + daftar[i].search;
        printf("  %-15s skor_skenario=%d\n", daftar[i].nama, skor);
    }

    return 0;
}

Output yang Dihasilkan:

text
Decision matrix (skor 1-5, 5 terbaik):
  Array           akses=5 insert_depan=1 insert_belakang=5 hapus=1 memori=5 search=1 -> total=18
  Linked List     akses=1 insert_depan=5 insert_belakang=2 hapus=4 memori=2 search=2 -> total=16
  Hash Table      akses=1 insert_depan=4 insert_belakang=4 hapus=3 memori=1 search=5 -> total=18
  BST             akses=1 insert_depan=3 insert_belakang=3 hapus=3 memori=2 search=4 -> total=16
  Heap            akses=1 insert_depan=2 insert_belakang=2 hapus=4 memori=4 search=1 -> total=14
  Circular Buffer akses=2 insert_depan=1 insert_belakang=1 hapus=1 memori=5 search=1 -> total=11

Skenario: butuh akses acak + search cepat:
  Array           skor_skenario=6
  Linked List     skor_skenario=3
  Hash Table      skor_skenario=6
  BST             skor_skenario=5
  Heap            skor_skenario=2
  Circular Buffer skor_skenario=3

Total skor tinggi tidak otomatis berarti “pilihan terbaik”. Yang penting adalah skor untuk operasi yang sering dipakai. Pada skenario “akses acak + search cepat”, array dan hash table seri (skor 6), tetapi keduanya unggul pada aspek berbeda—array menang akses, hash table menang search. Pilihan akhir bergantung pada proporsi operasi sebenarnya.

Skenario Umum dan Rekomendasi #

Tabel berikut memetakan skenario umum ke struktur data yang direkomendasikan:

Skenario	Struktur Direkomendasikan	Alasan
Akses indeks acak sering	Array	`O(1)` akses indeks
Insert/hapus di depan sering	Linked list	`O(1)` insert/hapus depan
Undo/redo, evaluasi ekspresi	Stack	LIFO alami
Buffer streaming, antrian task	Queue / Circular Buffer	FIFO dengan throughput tinggi
Lookup key-value sering	Hash table	`O(1)` rata-rata lookup
Range query (kunci dalam rentang)	BST (atau sorted array)	`O(log n + k)` range query
Priority scheduling, Dijkstra	Heap / Priority Queue	`O(log n)` akses min/max
Hubungan antar objek (jaringan, peta)	Graph (adjacency list)	Iterasi tetangga efisien
Data terurut, search sering	Sorted array + binary search	`O(log n)` search, `O(1)` akses
Data terurut, insert/delete sering	BST (self-balancing)	`O(log n)` insert/delete/search
Koleksi elemen unik, cek keanggotaan	Hash set (hash table tanpa nilai)	`O(1)` rata-rata cek anggota

Aturan Praktis #

Berikut aturan praktis yang berguna saat memilih struktur data:

Mulai dari sederhana: bila ragu, mulai dengan array. Bila performa tidak cukup, baru upgrade ke struktur lebih kompleks.
Profiling dulu, optimisasi kemudian: jangan menebak bottleneck. Ukur dengan profiler, baru pilih struktur yang menyelesaikan masalah sebenarnya.
Pertimbangkan konstanta: O(n) dengan konstanta kecil (array cache-friendly) bisa lebih cepat dari O(log n) dengan konstanta besar (BST cache-unfriendly) pada data kecil.
Hindari prematur optimisasi: implementasi sederhana yang benar lebih baik dari implementasi cepat yang buggy. Struktur data kompleks seperti AVL tree rawan bug.
Pertimbangkan ekosistem: bila library standar atau pihak ketiga sudah menyediakan struktur yang dibutuhkan (misal glib GHashTable), gunakan itu alih-alih implementasi sendiri.

Penutup #

Pemilihan struktur data adalah keputusan desain yang penting. Tidak ada jawaban universal—pilihan terbaik bergantung pada pola akses data, ukuran dataset, dan batasan memori. Dengan memahami tradeoff tiap struktur, kita dapat membuat keputusan rasional alih-alih asumsi.

Pada bagian akhir course algoritma dan struktur data ini, kita sudah mempelajari: analisis kompleksitas (Big O), algoritma searching (linear, binary), algoritma sorting (bubble, selection, insertion, merge, quicksort), dan struktur data fundamental (linked list, stack, queue, circular buffer, hash table, BST, heap, graph). Pengetahuan ini adalah bekal untuk masalah komputasi yang lebih kompleks di dunia nyata.