Kategori Struktur Data

Setiap struktur data yang akan kita pelajari pada Course ini dapat dikelompokkan ke dalam beberapa kategori berdasarkan bentuk, ukuran, dan jenis elemen yang disimpan. Pemahaman terhadap kategori ini membantu kita memilih struktur yang tepat dengan cepat ketika menghadapi masalah baru. Pada Chapter ini kita akan memetakan struktur data ke dalam tiga sumbu pengelompokan: linier vs non-linier, statis vs dinamis, dan homogen vs heterogen. Kita juga akan melihat contoh konkret penerapan dua kategori melalui kode C++ yang dapat dijalankan.

Pengelompokan Berdasarkan Bentuk #

Bentuk struktur data menentukan cara kita menjelajah dan memanipulasi elemen. Pengelompokan utama berdasarkan bentuk adalah linier dan non-linier.

Struktur Data Linier #

Struktur data linier menyusun elemen secara berurutan: setiap elemen (kecuali ujung) memiliki tepat satu elemen penerus dan satu elemen pendahulu. Penjelajahan dilakukan dalam satu arah, baik dari depan ke belakang maupun sebaliknya.

Contoh struktur data linier:

• array dan std::vector — blok memori berurutan.
• linked list — simpul terhubung lewat pointer.
• stack — tumpukan dengan akses LIFO.
• queue — antrean dengan akses FIFO.

Struktur Data Non-Linier #

Struktur data non-linier menyusun elemen secara hierarkis atau bercabang. Satu elemen dapat terhubung ke beberapa elemen penerus, sehingga penjelajahan tidak lagi linier.

Contoh struktur data non-linier:

• tree — hierarki simpul dengan satu root.
• graph — kumpulan simpul dengan koneksi sembarang.
• heap — pohon biner dengan properti heap.

Pengelompokan Berdasarkan Ukuran #

Ukuran struktur data dapat tetap (statis) atau berubah-ubah (dinamis) selama eksekusi program.

Struktur Data Statis #

Struktur statis dialokasikan dengan ukuran tetap pada saat kompilasi atau pada saat konstruksi. Kelebihannya adalah efisiensi memori dan akses cepat karena lokasi elemen dapat dihitung langsung. Kekurangannya, struktur statis tidak bisa tumbuh ketika data bertambah melebihi kapasitas awal.

Contoh: std::array<T, N> pada C++, array C-style T arr[N].

Struktur Data Dinamis #

Struktur dinamis dapat berubah ukuran saat runtime sesuai kebutuhan. Struktur ini mengalokasikan memori tambahan ketika elemen baru disisipkan dan membebaskan memori ketika elemen dihapus.

Contoh: std::vector, std::list, std::map, std::unordered_map, linked list.

Pengelompokan Berdasarkan Homogenitas #

Homogenitas menunjukkan apakah semua elemen struktur memiliki tipe yang sama.

• Homogen: semua elemen bertipe sama. Contoh: std::vector<int>, std::array<double, 10>.
• Heterogen: elemen boleh memiliki tipe berbeda. Contoh: std::tuple<int, std::string, double>, std::variant<int, std::string>, atau struct yang berisi beberapa field bertipe berbeda.

Mayoritas struktur data yang kita pelajari pada DSA bersifat homogen karena fokusnya pada algoritma yang memproses sekumpulan nilai dengan tipe sama.

Tabel Ringkasan Kategori #

Tabel berikut memetakan struktur data yang akan kita pelajari pada Course ini ke dalam tiga sumbu kategori.

Contoh Kode: Linier vs Non-Linier #

Sekarang kita akan melihat bagaimana dua kategori struktur data berbeda dapat merepresentasikan kumpulan nilai yang sama. Kita akan menyimpan tujuh bilangan ke dalam std::vector (linier) dan ke dalam binary search tree (BST, non-linier), lalu menampilkan isi keduanya. Perhatikan bahwa penjelajahan BST secara in-order menghasilkan elemen terurut, sebuah sifat khas struktur non-linier yang tidak dimiliki array mentah.

Mekanisme Kerja #

Pada std::vector, elemen disimpan berdampingan di memori. Iterasi dengan range-based for loop membaca elemen satu per satu sesuai urutan penyimpanan. Pada BST, setiap nilai disimpan pada simpul terpisah. Penyisipan menempatkan nilai lebih kecil di subpohon kiri dan nilai lebih besar di subpohon kanan. In-order traversal (kiri → akar → kanan) menghasilkan elemen terurut menaik.

Kode Program #

#include <iostream>
#include <vector>
#include <memory>

// Simpul pohon biner sederhana
struct Node {
    int nilai;
    std::unique_ptr<Node> kiri;
    std::unique_ptr<Node> kanan;

    explicit Node(int v) : nilai(v) {}
};

// Sisip nilai ke BST (binary search tree)
void sisip(Node* akar, int nilai) {
    if (nilai < akar->nilai) {
        if (akar->kiri) {
            sisip(akar->kiri.get(), nilai);
        } else {
            akar->kiri = std::make_unique<Node>(nilai);
        }
    } else if (nilai > akar->nilai) {
        if (akar->kanan) {
            sisip(akar->kanan.get(), nilai);
        } else {
            akar->kanan = std::make_unique<Node>(nilai);
        }
    }
    // jika sama, abaikan (no duplicates)
}

// In-order traversal: kiri, akar, kanan
void inorder(const Node* node) {
    if (!node) return;
    inorder(node->kiri.get());
    std::cout << node->nilai << " ";
    inorder(node->kanan.get());
}

int main() {
    // Struktur data linier: std::vector
    std::vector<int> dataLinier = {50, 30, 70, 20, 40, 60, 80};
    std::cout << "Array (linier): ";
    for (int v : dataLinier) std::cout << v << " ";
    std::cout << "\n";

    // Struktur data non-linier: pohon biner pencarian
    auto akar = std::make_unique<Node>(dataLinier[0]);
    for (size_t i = 1; i < dataLinier.size(); ++i) {
        sisip(akar.get(), dataLinier[i]);
    }

    std::cout << "BST inorder (non-linier): ";
    inorder(akar.get());
    std::cout << "\n";

    return 0;
}

Output yang Dihasilkan:

Array (linier): 50 30 70 20 40 60 80 
BST inorder (non-linier): 20 30 40 50 60 70 80 

Bedah Kode Baris-per-Baris #

Mari kita telaah bagian-bagian penting dari program di atas:

1. Baris 6 (struct Node): mendefinisikan simpul BST. Setiap simpul menyimpan nilai serta dua std::unique_ptr<Node> untuk anak kiri dan kanan. unique_ptr mengelola memori otomatis lewat RAII.
2. Baris 11 (explicit Node(int v)): constructor ditandai explicit agar tidak terjadi konversi implisit dari int ke Node.
3. Baris 16 (void sisip(Node* akar, int nilai)): fungsi rekursif penyisipan BST. Menerima raw pointer akar karena pemilikan memori tetap dipegang oleh unique_ptr di pemanggil.
4. Baris 17 (if (nilai < akar->nilai)): bandingkan nilai baru dengan nilai simpul saat ini. BST invariant: subpohon kiri berisi nilai lebih kecil, subpohon kanan berisi nilai lebih besar.
5. Baris 19 (sisip(akar->kiri.get(), nilai)): rekursi ke subpohon kiri bila sudah ada; jika belum, buat simpul baru pada baris 21.
6. Baris 31 (void inorder(const Node* node)): in-order traversal yang mengunjungi kiri dulu, lalu akar, lalu kanan. Pada BST, urutan ini menghasilkan elemen terurut menaik.
7. Baris 39 (std::vector<int> dataLinier = {...}): inisialisasi std::vector dengan tujuh elemen tak terurut. Struktur linier tidak memiliki invariant terurutan.
8. Baris 47 (auto akar = std::make_unique<Node>(...)): membuat root BST secara dinamis. auto memudahkan penulisan tanpa menyebut tipe panjang std::unique_ptr<Node>.

Implikasi Pemilihan Kategori #

Pemilihan kategori struktur data memengaruhi algoritma yang bisa dipakai dan kompleksitas yang dihasilkan. Sebagai contoh, mencari nilai pada array linier tak terurut memerlukan O(n) operasi (linear search). Pada BST, pencarian memerlukan O(log n) operasi pada kasus seimbang, atau O(n) pada kasus degenerate (pohon miring).

Beberapa pertimbangan praktis ketika memilih kategori:

• Linier vs non-linier: pilih non-linier jika dibutuhkan hierarki atau pencarian cepat.
• Statis vs dinamis: pilih statis jika ukuran diketahui di awal dan konstan untuk efisiensi maksimal.
• Homogen vs heterogen: gunakan std::variant atau std::tuple ketika tipe elemen bervariasi.

Ringkasan #

Pada Chapter ini kita telah mengelompokkan struktur data ke dalam tiga sumbu:

• Bentuk: linier (array, list, stack, queue) vs non-linier (tree, graph, heap).
• Ukuran: statis (array C, std::array) vs dinamis (std::vector, linked list, tree).
• Homogenitas: homogen (mayoritas struktur DSA) vs heterogen (tuple, variant, struct).

Pemilihan kategori yang tepat menjadi langkah pertama sebelum memilih struktur data spesifik. Pada Chapter berikutnya kita akan melihat kategori algoritma berdasarkan paradigma pemecahan masalah.