Linked list adalah struktur data dinamis pertama yang kita bangun. Berbeda dari array yang ukurannya tetap, linked list tumbuh dan menyusut sesuai kebutuhan dengan mengalokasikan node baru di heap. Pada bagian ini kita membuat linked_list.h yang mendefinisikan tipe Node, lalu linked_list.c dengan operasi list_insert_depan, list_insert_belakang, list_tampilkan, dan list_hapus_semua. Tujuan bagian ini adalah membiasakan diri dengan alokasi malloc per node dan dereference pointer ->.

Konsep #

Singly linked list terdiri dari rangkaian node, masing-masing berisi nilai (nilai) dan pointer ke node berikutnya (next). Pointer head menandai awal list; bila list kosong, head == NULL. Pointer next dari node terakhir selalu NULL sebagai penanda akhir. Tidak ada batas maksimum — list dapat tumbuh selama memori heap tersedia.

Mekanisme insert di depan: alokasikan node baru, isi nilai dan next = head lalu update head ke node baru. Operasi ini O(1) karena tidak perlu traversal. Insert di belakang berbeda: kita harus traverse ke node terakhir (yang next == NULL), lalu set next dari node terakhir ke node baru. Operasi ini O(n) kecuali kita simpan pointer tail (yang akan dipakai pada Bagian 3 untuk queue).

Traversal mengikuti pointer next dari head sampai NULL. Pada setiap node, kita bisa cetak nilai atau hitung statistik. Operasi list_hapus_semua membebaskan seluruh node dengan traverse lalu free setiap node — penting untuk menyimpan pointer next sebelum free karena node yang sudah di-free tidak boleh diakses lagi.

Implementasi #

Header linked_list.h:

c 
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

typedef struct Node {
    int nilai;
    struct Node *next;
} Node;

Node *list_insert_depan(Node *head, int nilai);
Node *list_insert_belakang(Node *head, int nilai);
void  list_tampilkan(const Node *head);
void  list_hapus_semua(Node *head);

#endif /* LINKED_LIST_H */

Implementasi linked_list.c:

c 
#include "linked_list.h"
#include <stdio.h>
#include <stdlib.h>

static Node *buat_node(int nilai) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (n == 0) return 0;
    n->nilai = nilai;
    n->next = 0;
    return n;
}

Node *list_insert_depan(Node *head, int nilai) {
    Node *n = buat_node(nilai);
    if (n == 0) return head;
    n->next = head;
    return n;
}

Node *list_insert_belakang(Node *head, int nilai) {
    Node *n = buat_node(nilai);
    if (n == 0) return head;
    if (head == 0) return n;
    Node *cur = head;
    while (cur->next != 0) cur = cur->next;
    cur->next = n;
    return head;
}

void list_tampilkan(const Node *head) {
    const Node *cur = head;
    while (cur != 0) {
        printf("%d -> ", cur->nilai);
        cur = cur->next;
    }
    printf("NULL\n");
}

void list_hapus_semua(Node *head) {
    Node *cur = head;
    while (cur != 0) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

Demo mandiri:

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

typedef struct Node {
    int nilai;
    struct Node *next;
} Node;

static Node *buat_node(int nilai) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (n == 0) return 0;
    n->nilai = nilai;
    n->next = 0;
    return n;
}

static Node *list_insert_depan(Node *head, int nilai) {
    Node *n = buat_node(nilai);
    if (n == 0) return head;
    n->next = head;
    return n;
}

static Node *list_insert_belakang(Node *head, int nilai) {
    Node *n = buat_node(nilai);
    if (n == 0) return head;
    if (head == 0) return n;
    Node *cur = head;
    while (cur->next != 0) cur = cur->next;
    cur->next = n;
    return head;
}

static void list_tampilkan(const Node *head) {
    const Node *cur = head;
    while (cur != 0) {
        printf("%d -> ", cur->nilai);
        cur = cur->next;
    }
    printf("NULL\n");
}

static void list_hapus_semua(Node *head) {
    Node *cur = head;
    while (cur != 0) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void) {
    Node *head = 0;
    head = list_insert_belakang(head, 10);
    head = list_insert_belakang(head, 20);
    head = list_insert_depan(head, 5);
    head = list_insert_belakang(head, 30);
    list_tampilkan(head);

    int panjang = 0;
    for (Node *cur = head; cur != 0; cur = cur->next) panjang++;
    printf("Panjang list: %d\n", panjang);

    list_hapus_semua(head);
    printf("List dibebaskan.\n");
    return 0;
}

Output yang Dihasilkan:

text 
5 -> 10 -> 20 -> 30 -> NULL
Panjang list: 4
List dibebaskan.

Pengujian #

Build dan jalankan modul linked list:

bash 
gcc -std=c11 -Wall -Wextra -o linked_list_demo linked_list.c main.c
./linked_list_demo

Untuk memverifikasi tidak ada memory leak, build dengan AddressSanitizer (-fsanitize=address) lalu jalankan:

bash 
gcc -std=c11 -Wall -Wextra -fsanitize=address -o linked_list_asan \
    linked_list.c main.c
./linked_list_asan

Output yang Dihasilkan (potongan akhir):

text 
5 -> 10 -> 20 -> 30 -> NULL
Panjang list: 4
List dibebaskan.

AddressSanitizer diam (tidak ada pesan error) — bila ada leak, ASan akan mencetak ERROR: LeakSanitizer: detected memory leaks dengan stack trace ke lokasi malloc yang tidak di-free. Bila Anda memakai valgrind, perintah valgrind --leak-check=full ./linked_list_demo memberi laporan serupa dengan All heap blocks were freed -- no leaks are possible bila tidak ada leak.

Mari kita telaah baris-baris kunci pada implementasi:

  1. Baris struct Node *next; di dalam struct: pointer self-referential. Struct merujuk ke struct sendiri via pointer — pola fundamental untuk struktur data rekursif. Tipe Node lengkap tersedia setelah typedef, sehingga penggunaan Node * di luar struct juga sah.
  2. Baris Node *n = (Node *)malloc(sizeof(Node));: alokasi node baru di heap. sizeof(Node) memberi ukuran struct (16 byte pada sistem 64-bit: 4 byte int + 4 byte padding + 8 byte pointer). Cast (Node *) opsional di C tetapi membantu dokumentasi.
  3. Baris if (n == 0) return head;: penjaga NULL. malloc dapat gagal bila heap penuh — kita kembalikan head lama tanpa modifikasi agar pemanggil tidak kehilangan list.
  4. Baris n->next = head; return n; (insert depan): tautkan node baru ke head lama, lalu jadikan node baru sebagai head baru. Operasi O(1) — tidak ada traversal.
  5. Baris while (cur->next != 0) cur = cur->next; (insert belakang): traverse ke node terakhir. Kondisi cur->next != 0 berhenti di node terakhir (yang next-nya NULL). Operasi O(n) — perlu traverse seluruh list.
  6. Baris while (cur != 0) { ... cur = cur->next; } (tampilkan): traverse polos. Mulai dari head, cetak nilai, lanjut ke next. Loop berhenti saat cur == NULL (akhir list).
  7. Baris Node *next = cur->next; free(cur); cur = next; (hapus semua): pola penting — simpan pointer next SEBELUM free. Bila kita free(cur) dulu lalu akses cur->next, itu undefined behavior (use-after-free).

Pada Bagian 2 kita akan memakai linked list sebagai fondasi stack — struktur LIFO dengan operasi push/pop yang lebih sederhana.

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;
}