Setelah Proyek 5 memakai array statis untuk menampung baris CSV, kini kita naik kelas: membangun struktur data dinamis yang tumbuh sesuai kebutuhan. Pada proyek ini kita mengimplementasikan empat struktur data fundamental dari nol — singly linked list, stack, queue, dan hash table — semuanya dengan alokasi memori manual via malloc/free. Proyek ini melatih keterampilan pointer, manajemen memori, dan pengujian struktur data yang menjadi pondasi untuk algoritma tingkat lanjut.

Setiap struktur data kita tempatkan pada pasangan header (.h) dan implementasi (.c) sendiri, dengan API yang konsisten: fungsi _init, _push/_enqueue, _pop/_dequeue, dan _destroy. Program utama main.c mendemonstrasikan pemakaian keempat struktur, sementara tests.c memverifikasi perilaku dengan rangkaian test yang dapat dijalankan lewat make test.

Tampilan Program Akhir #

Sesi pemakaian berikut menunjukkan hasil akhir proyek saat dijalankan dengan make run:

text 
$ make run
=== Demo Struktur Data ===

1) Singly Linked List
Insert belakang: 10, 20
Insert depan: 5
Insert belakang: 30
Hasil: 5 -> 10 -> 20 -> 30 -> NULL
Panjang list: 4

2) Stack (LIFO)
Push: 10, 20, 30
Pop semua: 30 20 10

3) Queue (FIFO)
Enqueue: 100, 200, 300
Dequeue semua: 100 200 300

4) Hash Table
Put: Budi=25, Siti=30, Andi=28
Get Siti -> 30
Get Budi -> 25
Get Dewi -> (tidak ditemukan)
Distribusi bucket:
  bucket[0..7]: 0 0 1 0 0 1 0 1

5) Memory test
Buffer size 3 -> resize ke 5
Data: 0 10 20 30 40
Setelah destroy: data=NULL, size=0

=== Selesai ===

$ make test
[LULUS] pop dari stack kosong -> -1
[LULUS] size setelah 2 push = 2
[LULUS] pop pertama = 20 (LIFO)
[LULUS] pop kedua = 10 (LIFO)
[LULUS] pop dari stack kosong kembali -> -1
...

Ringkasan: 5 lulus, 0 gagal

Output membuktikan keempat struktur data bekerja sesuai kontrak: linked list menyimpan urutan insert, stack membalik urutan (LIFO), queue menjaga urutan (FIFO), dan hash table mencari key dalam O(1) rata-rata.

Tujuan Pembelajaran #

Setelah menyelesaikan proyek ini, kita mampu:

  • mengimplementasikan singly linked list dengan insert depan dan belakang,
  • membangun stack berbasis linked list dengan operasi push/pop,
  • membangun queue berbasis linked list dengan operasi enqueue/dequeue,
  • mengimplementasikan hash table dengan chaining untuk collision resolution,
  • mengelola siklus hidup memori: malloc, realloc, free tanpa leak,
  • menulis unit test untuk struktur data dengan edge case boundary.

Prasyarat #

Proyek ini memakai materi bab sebelumnya:

  • Pointer dan Array — dereference, -> operator, pointer arithmetic,
  • Memory Management — malloc, free, realloc, dangling pointer,
  • Struct dan Enum — Node, Stack, Queue, HashTable,
  • Fungsi dan Header Files — pemisahan .h/.c,
  • String — strcmp, strncpy untuk hash table key.

Tahapan Pengerjaan #

Proyek dikerjakan dalam enam bagian berurutan. Setiap bagian menghasilkan modul yang dapat diuji sendiri:

  1. Bagian 1: Singly Linked List — linked_list.h/.c dengan list_insert_depan, list_insert_belakang, list_tampilkan, dan list_hapus_semua.
  2. Bagian 2: Stack — stack.h/.c dengan operasi LIFO dan stack_is_empty.
  3. Bagian 3: Queue — queue.h/.c dengan operasi FIFO dan penanganan tail.
  4. Bagian 4: Hash Table — hash_table.h/.c dengan chaining dan fungsi hash FNV-1a.
  5. Bagian 5: Memory Management — pola init/destroy, realloc untuk resize, dan pemeriksaan leak.
  6. Bagian 6: Unit Testing — tests.c dengan edge case: pop dari stack kosong, dequeue dari queue kosong, get key yang tidak ada.

Mulailah dari Bagian 1 dan ikuti urutannya karena setiap bagian membangun fondasi pointer dan alokasi yang dipakai bagian berikutnya. Berkas sumber lengkap tersedia pada bagian bawah halaman masing-masing part.

# Bagian 1: Singly Linked List

Implementasikan linked list dengan insert, delete, traverse.

Buka → # Bagian 2: Stack

Implementasikan stack dengan push, pop, peek.

Buka → # Bagian 3: Queue

Implementasikan queue FIFO dengan enqueue dan dequeue.

Buka → # Bagian 4: Hash Table

Implementasikan hash table dengan chaining.

Buka → # Bagian 5: Memory Management

Pastikan setiap struktur membebaskan semua node.

Buka → # Bagian 6: Unit Testing

Tulis test untuk setiap struktur data.

Buka → # Buka →

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

hash_table.c

Unduh berkas
c 
/* hash_table.c -- simple hash table with chaining. */
#define _POSIX_C_SOURCE 200809L /* for strdup */
#include "hash_table.h"

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

/* djb2 hash function by Daniel J. Bernstein. */
static unsigned long hash_djb2(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*str++)) {
        h = ((h << 5) + h) + c; /* h * 33 + c */
    }
    return h;
}

int ht_init(HashTable *ht, size_t capacity) {
    if (!ht || capacity == 0) return -1;
    ht->buckets = calloc(capacity, sizeof(HTNode *));
    if (!ht->buckets) return -1;
    ht->capacity = capacity;
    ht->size = 0;
    return 0;
}

void ht_destroy(HashTable *ht) {
    if (!ht) return;
    for (size_t i = 0; i < ht->capacity; i++) {
        HTNode *cur = ht->buckets[i];
        while (cur) {
            HTNode *next = cur->next;
            free(cur->key);
            free(cur);
            cur = next;
        }
    }
    free(ht->buckets);
    ht->buckets = NULL;
    ht->capacity = 0;
    ht->size = 0;
}

int ht_put(HashTable *ht, const char *key, int value) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    /* Update if key exists. */
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            return 0;
        }
        cur = cur->next;
    }
    /* Insert new node at head. */
    HTNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->key = strdup(key);
    if (!node->key) {
        free(node);
        return -1;
    }
    node->value = value;
    node->next = ht->buckets[h];
    ht->buckets[h] = node;
    ht->size++;
    return 0;
}

int ht_get(const HashTable *ht, const char *key, int *out) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (out) *out = cur->value;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

int ht_remove(HashTable *ht, const char *key) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    HTNode *prev = NULL;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next;
            else      ht->buckets[h] = cur->next;
            free(cur->key);
            free(cur);
            ht->size--;
            return 0;
        }
        prev = cur;
        cur = cur->next;
    }
    return -1;
}

size_t ht_size(const HashTable *ht) {
    return ht ? ht->size : 0;
}

linked_list.c

Unduh berkas
c 
/* linked_list.c -- singly linked list implementation. */
#include "linked_list.h"

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

void ll_init(LinkedList *list) {
    if (!list) return;
    list->head = NULL;
    list->size = 0;
}

void ll_destroy(LinkedList *list) {
    if (!list) return;
    LLNode *cur = list->head;
    while (cur) {
        LLNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

int ll_push_front(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = list->head;
    list->head = node;
    list->size++;
    return 0;
}

int ll_push_back(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = NULL;
    if (!list->head) {
        list->head = node;
    } else {
        LLNode *cur = list->head;
        while (cur->next) cur = cur->next;
        cur->next = node;
    }
    list->size++;
    return 0;
}

int ll_pop_front(LinkedList *list, int *out) {
    if (!list || !list->head) return -1;
    LLNode *node = list->head;
    if (out) *out = node->data;
    list->head = node->next;
    free(node);
    list->size--;
    return 0;
}

int ll_get(const LinkedList *list, size_t index, int *out) {
    if (!list || !out || index >= list->size) return -1;
    LLNode *cur = list->head;
    for (size_t i = 0; i < index; i++) cur = cur->next;
    *out = cur->data;
    return 0;
}

int ll_remove(LinkedList *list, size_t index) {
    if (!list || index >= list->size) return -1;
    LLNode *to_free;
    if (index == 0) {
        to_free = list->head;
        list->head = to_free->next;
    } else {
        LLNode *prev = list->head;
        for (size_t i = 0; i < index - 1; i++) prev = prev->next;
        to_free = prev->next;
        prev->next = to_free->next;
    }
    free(to_free);
    list->size--;
    return 0;
}

int ll_find(const LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *cur = list->head;
    int index = 0;
    while (cur) {
        if (cur->data == value) return index;
        cur = cur->next;
        index++;
    }
    return -1;
}

size_t ll_size(const LinkedList *list) {
    return list ? list->size : 0;
}

void ll_print(const LinkedList *list) {
    if (!list) return;
    printf("[");
    LLNode *cur = list->head;
    while (cur) {
        printf("%d", cur->data);
        if (cur->next) printf(", ");
        cur = cur->next;
    }
    printf("]\n");
}

main.c

Unduh berkas
c 
/* main.c -- demo of all four data structures. */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

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

static void demo_linked_list(void) {
    printf("--- Linked List ---\n");
    LinkedList list;
    ll_init(&list);

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_back(&list, 30);
    ll_push_front(&list, 5);
    printf("After pushes: ");
    ll_print(&list);
    printf("Size: %zu\n", ll_size(&list));
    printf("Find 20: index %d\n", ll_find(&list, 20));

    int v;
    ll_pop_front(&list, &v);
    printf("After pop_front (%d): ", v);
    ll_print(&list);

    ll_destroy(&list);
    printf("\n");
}

static void demo_stack(void) {
    printf("--- Stack ---\n");
    Stack s;
    if (stack_init(&s, 4) != 0) {
        printf("stack_init failed\n");
        return;
    }

    stack_push(&s, 1);
    stack_push(&s, 2);
    stack_push(&s, 3);
    printf("Size: %zu\n", stack_size(&s));

    int v;
    while (!stack_is_empty(&s)) {
        stack_pop(&s, &v);
        printf("Popped: %d\n", v);
    }

    stack_destroy(&s);
    printf("\n");
}

static void demo_queue(void) {
    printf("--- Queue ---\n");
    Queue q;
    if (queue_init(&q, 4) != 0) {
        printf("queue_init failed\n");
        return;
    }

    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);
    printf("Size: %zu\n", queue_size(&q));

    int v;
    while (!queue_is_empty(&q)) {
        queue_dequeue(&q, &v);
        printf("Dequeued: %d\n", v);
    }

    queue_destroy(&q);
    printf("\n");
}

static void demo_hash_table(void) {
    printf("--- Hash Table ---\n");
    HashTable ht;
    if (ht_init(&ht, 8) != 0) {
        printf("ht_init failed\n");
        return;
    }

    ht_put(&ht, "satu", 1);
    ht_put(&ht, "dua", 2);
    ht_put(&ht, "tiga", 3);
    printf("Size: %zu\n", ht_size(&ht));

    int v;
    if (ht_get(&ht, "dua", &v) == 0) printf("get(dua) = %d\n", v);
    if (ht_get(&ht, "empat", &v) != 0) printf("get(empat) not found\n");

    ht_remove(&ht, "dua");
    printf("After remove dua, size: %zu\n", ht_size(&ht));

    ht_destroy(&ht);
    printf("\n");
}

int main(void) {
    printf("== Struktur Data Demo ==\n\n");
    demo_linked_list();
    demo_stack();
    demo_queue();
    demo_hash_table();
    printf("== Selesai ==\n");
    return 0;
}

queue.c

Unduh berkas
c 
/* queue.c -- FIFO queue (circular buffer). */
#include "queue.h"

#include <stdlib.h>

int queue_init(Queue *q, size_t capacity) {
    if (!q || capacity == 0) return -1;
    q->data = malloc(capacity * sizeof(int));
    if (!q->data) return -1;
    q->capacity = capacity;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    return 0;
}

void queue_destroy(Queue *q) {
    if (!q) return;
    free(q->data);
    q->data = NULL;
    q->capacity = 0;
    q->head = q->tail = q->size = 0;
}

int queue_enqueue(Queue *q, int value) {
    if (!q || q->size >= q->capacity) return -1;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
    return 0;
}

int queue_dequeue(Queue *q, int *out) {
    if (!q || q->size == 0) return -1;
    if (out) *out = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return 0;
}

int queue_is_empty(const Queue *q) {
    return !q || q->size == 0;
}

size_t queue_size(const Queue *q) {
    return q ? q->size : 0;
}

stack.c

Unduh berkas
c 
/* stack.c -- LIFO stack (dynamic array). */
#include "stack.h"

#include <stdlib.h>

int stack_init(Stack *s, size_t capacity) {
    if (!s || capacity == 0) return -1;
    s->data = malloc(capacity * sizeof(int));
    if (!s->data) return -1;
    s->capacity = capacity;
    s->size = 0;
    return 0;
}

void stack_destroy(Stack *s) {
    if (!s) return;
    free(s->data);
    s->data = NULL;
    s->capacity = 0;
    s->size = 0;
}

int stack_push(Stack *s, int value) {
    if (!s) return -1;
    if (s->size >= s->capacity) {
        size_t new_cap = s->capacity * 2;
        int *p = realloc(s->data, new_cap * sizeof(int));
        if (!p) return -1;
        s->data = p;
        s->capacity = new_cap;
    }
    s->data[s->size++] = value;
    return 0;
}

int stack_pop(Stack *s, int *out) {
    if (!s || stack_is_empty(s)) return -1;
    if (out) *out = s->data[--s->size];
    return 0;
}

int stack_peek(const Stack *s, int *out) {
    if (!s || stack_is_empty(s) || !out) return -1;
    *out = s->data[s->size - 1];
    return 0;
}

int stack_is_empty(const Stack *s) {
    return !s || s->size == 0;
}

size_t stack_size(const Stack *s) {
    return s ? s->size : 0;
}

tests.c

Unduh berkas
c 
/* tests.c -- unit tests for all four data structures.
 *
 * Compile with:
 *   gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined \
 *       tests.c linked_list.c stack.c queue.c hash_table.c -o test_runner
 */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

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

static int tests_passed = 0;
static int tests_failed = 0;

#define ASSERT(cond, msg) do { \
    if (cond) { tests_passed++; } \
    else { tests_failed++; printf("FAIL: %s (line %d)\n", msg, __LINE__); } \
} while (0)

static void test_linked_list(void) {
    LinkedList list;
    ll_init(&list);
    ASSERT(ll_size(&list) == 0, "ll empty size");

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_front(&list, 5);
    ASSERT(ll_size(&list) == 3, "ll size after push");

    int v;
    ASSERT(ll_get(&list, 0, &v) == 0 && v == 5, "ll get(0) == 5");
    ASSERT(ll_get(&list, 2, &v) == 0 && v == 20, "ll get(2) == 20");

    ASSERT(ll_find(&list, 10) == 1, "ll find(10) == 1");
    ASSERT(ll_find(&list, 99) == -1, "ll find(99) not found");

    ASSERT(ll_pop_front(&list, &v) == 0 && v == 5, "ll pop_front == 5");
    ASSERT(ll_size(&list) == 2, "ll size after pop");

    ll_remove(&list, 0);
    ASSERT(ll_size(&list) == 1, "ll size after remove");

    ll_destroy(&list);
    ASSERT(ll_size(&list) == 0, "ll size after destroy");
}

static void test_stack(void) {
    Stack s;
    ASSERT(stack_init(&s, 2) == 0, "stack_init ok");
    ASSERT(stack_is_empty(&s), "stack empty initially");

    ASSERT(stack_push(&s, 100) == 0, "stack_push 100");
    ASSERT(stack_push(&s, 200) == 0, "stack_push 200");
    /* Force a grow. */
    ASSERT(stack_push(&s, 300) == 0, "stack_push 300 (grow)");

    ASSERT(stack_size(&s) == 3, "stack size 3");

    int v;
    ASSERT(stack_peek(&s, &v) == 0 && v == 300, "stack_peek == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 300, "stack_pop == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 200, "stack_pop == 200");
    ASSERT(stack_pop(&s, &v) == 0 && v == 100, "stack_pop == 100");
    ASSERT(stack_is_empty(&s), "stack empty at end");
    ASSERT(stack_pop(&s, &v) == -1, "stack_pop on empty returns -1");

    stack_destroy(&s);
}

static void test_queue(void) {
    Queue q;
    ASSERT(queue_init(&q, 4) == 0, "queue_init ok");
    ASSERT(queue_is_empty(&q), "queue empty initially");

    for (int i = 1; i <= 4; i++) {
        ASSERT(queue_enqueue(&q, i * 10) == 0, "queue_enqueue");
    }
    ASSERT(queue_size(&q) == 4, "queue full size");

    int v;
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 10, "queue_dequeue 10");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 20, "queue_dequeue 20");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 30, "queue_dequeue 30");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 40, "queue_dequeue 40");
    ASSERT(queue_is_empty(&q), "queue empty after drain");
    ASSERT(queue_dequeue(&q, &v) == -1, "queue_dequeue on empty");

    queue_destroy(&q);
}

static void test_hash_table(void) {
    HashTable ht;
    ASSERT(ht_init(&ht, 4) == 0, "ht_init ok");
    ASSERT(ht_size(&ht) == 0, "ht empty");

    ASSERT(ht_put(&ht, "alpha", 1) == 0, "ht_put alpha");
    ASSERT(ht_put(&ht, "beta", 2) == 0, "ht_put beta");
    ASSERT(ht_put(&ht, "gamma", 3) == 0, "ht_put gamma");
    ASSERT(ht_size(&ht) == 3, "ht size 3");

    int v;
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 2, "ht_get beta");
    ASSERT(ht_get(&ht, "missing", &v) == -1, "ht_get missing");

    /* Update existing key. */
    ASSERT(ht_put(&ht, "beta", 22) == 0, "ht_put beta update");
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 22, "ht_get beta updated");
    ASSERT(ht_size(&ht) == 3, "ht size unchanged after update");

    ASSERT(ht_remove(&ht, "alpha") == 0, "ht_remove alpha");
    ASSERT(ht_get(&ht, "alpha", &v) == -1, "ht_get alpha gone");
    ASSERT(ht_size(&ht) == 2, "ht size 2 after remove");

    ht_destroy(&ht);
}

int main(void) {
    test_linked_list();
    test_stack();
    test_queue();
    test_hash_table();

    printf("\n=== Test Results ===\n");
    printf("Passed: %d\n", tests_passed);
    printf("Failed: %d\n", tests_failed);
    if (tests_failed == 0) {
        printf("Lulus : %d\n", tests_passed);
        return 0;
    }
    return 1;
}