Belajar C Language - Data Structures & Algorithms Dasar

#Pendahuluan

Setelah menguasai pointer dan alokasi dinamis di episode 7, kalian kini siap membangun struktur data — blok penyusun aplikasi nyata. Episode 9 membahas linked list, stack, dan queue, lalu sorting dan searching sederhana, dan bagaimana menganalisis kompleksitasnya.

Struktur data yang dibahas di episode ini bukan sekadar latihan akademik. Linked list menjadi dasar implementasi tabel hash, stack dipakai untuk menjalankan fungsi rekursif di dalam CPU, dan queue mengatur antrian permintaan di server.

Algoritma sorting dan searching yang kalian pelajari akan menjadi pembanding untuk memahami mengapa struktur data dan algoritma yang lebih canggih dibutuhkan di sistem produksi.

#Linked List

#Node dan Pointer Berantai

Linked list adalah rangkaian node, di mana setiap node menyimpan data dan pointer ke node berikutnya. Berbeda dengan array, elemen tidak bersebelahan di memori, sehingga penyisipan dan penghapusan di tengah lebih murah:

cat > list.c <<'EOF'
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void sisip_depan(struct Node **head, int nilai) {
    struct Node *baru = malloc(sizeof(struct Node));
    if (baru == NULL) {
        return;
    }
    baru->data = nilai;
    baru->next = *head;
    *head = baru;
}
 
void cetak(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next) {
        printf("%d -> ", p->data);
    }
    printf("NULL\n");
}
 
int main(void) {
    struct Node *head = NULL;
    sisip_depan(&head, 3);
    sisip_depan(&head, 2);
    sisip_depan(&head, 1);
    cetak(head);
    return 0;
}
EOF
gcc -Wall -Wextra list.c -o list && ./list

Fungsi sisip_depan(&head, 3) menerima alamat dari pointer kepala karena head sendiri harus bisa diubah. Akses anggota lewat -> adalah shorthand untuk dereference lalu akses: p->data setara dengan (*p).data. Jangan lupa melepaskan setiap node dengan free setelah tidak dipakai.

#Kompleksitas Linked List

Akses elemen ke-n memerlukan penelusuran dari awal, sehingga kompleksitasnya O(n). Namun penyisipan di depan hanya butuh waktu tetap O(1). Trade-off inilah yang membedakan linked list dari array dan menentukan kapan memakai yang mana.

#Stack dan Queue

#Stack: LIFO

Stack bekerja dengan prinsip last in, first out: elemen terakhir yang masuk adalah yang pertama keluar. Operasi utamanya adalah push untuk menambah dan pop untuk mengambil:

#include <stdio.h>
 
#define KAPASITAS 8
 
int tumpukan[KAPASITAS];
int atas = 0;
 
void push(int nilai) {
    if (atas < KAPASITAS) {
        tumpukan[atas++] = nilai;
    }
}
 
int pop(void) {
    if (atas > 0) {
        return tumpukan[--atas];
    }
    return -1;
}

Implementasi di atas memakai array dengan indeks atas sebagai penanda posisi. Memeriksa kapasitas sebelum push dan kekosongan sebelum pop mencegah akses di luar batas.

#Queue: FIFO

Queue bekerja dengan prinsip first in, first out, seperti antrian di loket. Elemen ditambahkan di belakang dan diambil dari depan. Implementasi array memakai dua penanda, depan dan belakang, yang berputar saat mencapai ujung — teknik yang disebut circular buffer. Queue adalah struktur utama untuk buffer antrian di sistem jaringan dan kernel.

#Sorting Dasar

#Bubble Sort

Bubble sort membandingkan pasangan elemen berdekatan dan menukarnya jika urutan salah, berulang hingga tidak ada tukar lagi. Sederhana dan mudah dipahami, tetapi lambat untuk data besar:

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

Kompleksitas bubble sort adalah O(n^2) pada kasus terburuk. Perhatikan bahwa array dikirim ke fungsi sebagai pointer, sehingga perubahan di dalam fungsi terlihat dari luar — memanfaatkan perilaku array dari episode 6.

#Insertion Sort dan Selection Sort

Insertion sort membangun hasil terurut elemen per elemen, cocok untuk data yang hampir terurut. Selection sort mencari elemen terkecil dan menempatkannya di posisi yang benar setiap iterasi. Keduanya O(n^2) pada kasus terburuk, tetapi insertion sort unggul praktis untuk array kecil.

#Searching

#Linear Search

Linear search memeriksa elemen satu per satu dari awal:

int linear_search(int a[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

Linear search sederhana dan tidak butuh data terurut, tetapi kompleksitasnya O(n). Untuk data besar, ini terlalu lambat.

#Binary Search

Binary search memangkas area pencarian setengah setiap langkah, tetapi syaratnya array sudah terurut. Bandingkan target dengan elemen tengah, lalu persempit ke kiri atau kanan:

int binary_search(int a[], int n, int target) {
    int kiri = 0, kanan = n - 1;
    while (kiri <= kanan) {
        int tengah = kiri + (kanan - kiri) / 2;
        if (a[tengah] == target) {
            return tengah;
        }
        if (a[tengah] < target) {
            kiri = tengah + 1;
        } else {
            kanan = tengah - 1;
        }
    }
    return -1;
}

Rumus tengah = kiri + (kanan - kiri) / 2 menghindari overflow dibanding (kiri + kanan) / 2. Binary search berjalan dalam O(log n), membuatnya efisien bahkan untuk jutaan elemen.

#Penutup

Inti yang harus dibawa pulang:

• Linked list memakai node yang terhubung pointer dan hemat sisipan di tengah.
• Stack adalah LIFO, queue adalah FIFO, keduanya bisa dibangun dengan array.
• Bubble, insertion, dan selection sort memiliki kompleksitas O(n^2).
• Linear search O(n), binary search O(log n) dengan syarat data terurut.
• Akses struct lewat pointer memakai operator panah.
• Jangan optimasi sebelum memahami kompleksitas dan kebutuhan nyata.

Di episode 10 selanjutnya kita akan membahas preprocessor dan build systems — direktif #include, #define, #ifdef, dan #pragma, macro function dan konstanta yang aman, Makefile dasar dengan rules dan targets, hingga pendahuluan CMake untuk project cross-platform.