Learn C Language - Basic Data Structures & Algorithms

#Introduction

Now that you've mastered pointers and dynamic allocation in episode 7, you're ready to build data structures — the building blocks of real applications. Episode 9 covers linked lists, stacks, and queues, then simple sorting and searching, and how to analyze their complexity.

The data structures discussed in this episode aren't just academic exercises. Linked lists underpin hash table implementations, stacks are used by the CPU to run recursive functions, and queues manage request queues in servers.

The sorting and searching algorithms you learn will serve as a baseline for understanding why more sophisticated data structures and algorithms are needed in production systems.

#Linked Lists

#Nodes and Chained Pointers

A linked list is a sequence of nodes, where each node stores data and a pointer to the next node. Unlike arrays, elements are not adjacent in memory, so insertion and deletion in the middle are cheaper:

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

The function sisip_depan(&head, 3) receives the address of the head pointer because head itself must be modifiable. Member access via -> is shorthand for dereference-then-access: p->data is equivalent to (*p).data. Don't forget to free every node with free when it's no longer used.

#Linked List Complexity

Accessing the n-th element requires traversing from the start, so the complexity is O(n). However, insertion at the front takes constant time O(1). This trade-off distinguishes linked lists from arrays and determines when to use which.

#Stacks and Queues

#Stack: LIFO

A stack works on the last in, first out principle: the last element inserted is the first to come out. Its main operations are push to add and pop to remove:

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

The implementation above uses an array with the index atas as a position marker. Checking capacity before push and emptiness before pop prevents out-of-bounds access.

#Queue: FIFO

A queue works on the first in, first out principle, like a ticket counter line. Elements are added at the back and taken from the front. An array implementation uses two markers, depan and belakang, which wrap around when reaching the end — a technique called a circular buffer. Queues are the primary structure for request buffers in network systems and kernels.

#Basic Sorting

#Bubble Sort

Bubble sort compares adjacent element pairs and swaps them if they're out of order, repeating until no swaps remain. Simple and easy to understand, but slow for large data:

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

Bubble sort's complexity is O(n^2) in the worst case. Note that the array is passed to the function as a pointer, so changes inside the function are visible outside — leveraging the array behavior from episode 6.

#Insertion Sort and Selection Sort

Insertion sort builds the sorted result element by element, well suited for nearly sorted data. Selection sort finds the smallest element and places it in the correct position each iteration. Both are O(n^2) in the worst case, but insertion sort is practically superior for small arrays.

#Searching

#Linear Search

Linear search checks elements one by one from the start:

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 is simple and doesn't require sorted data, but its complexity is O(n). For large data, it's too slow.

#Binary Search

Binary search cuts the search area in half at each step, but requires the array to be sorted. Compare the target with the middle element, then narrow down to the left or right:

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

The formula tengah = kiri + (kanan - kiri) / 2 avoids overflow compared to (kiri + kanan) / 2. Binary search runs in O(log n), making it efficient even for millions of elements.

#Closing

Key takeaways:

• Linked lists use pointer-connected nodes and are cheap for middle insertions.
• Stacks are LIFO, queues are FIFO, and both can be built with arrays.
• Bubble, insertion, and selection sort all have O(n^2) complexity.
• Linear search is O(n), binary search is O(log n) provided the data is sorted.
• Struct access through pointers uses the arrow operator.
• Don't optimize before understanding the complexity and real needs.

In the next episode 10 we will discuss the preprocessor and build systems — the #include, #define, #ifdef, and #pragma directives, safe function macros and constants, basic Makefiles with rules and targets, and an introduction to CMake for cross-platform projects.