Skip to content
BoKSA

Data Structures in C

Data Structures in C

Introduction

An array is a row of lockers — great until you need to insert a locker in the middle or grow the row without knowing the final size in advance. Data structures are organised ways to store and find data. The ones in this article — linked lists, queues, stacks, and binary search trees — all build on pointers and structs from the previous articles.

You meet them in real systems: RTOS ready-lists are queues; undo buffers are stacks; symbol tables and maps use trees; sensor chains use lists. On embedded hardware, you also choose how you allocate nodes (heap vs pool) because time and memory are limited.

Why not always use arrays?

Arrays Linked structures
Fast index access arr[i] Must walk from head to find item i
Fixed size (unless dynamic alloc) Grow one node at a time
Memory contiguous — cache-friendly Nodes scattered — pointer chasing
Insert in middle — shift many elements Insert — change a few pointers

Neither is "best" — pick based on what your program does most often.

Linked lists — train carriages

Each node holds data and a pointer to the next node. The head pointer tells you where the train starts.

1
head → [ 10 | • ] → [ 20 | • ] → [ 30 | NULL ]

1
2
3
4
5
6
7
8
typedef struct linked_list_node {
    int data;
    struct linked_list_node *next;
} linked_list_node_t;

typedef struct linked_list {
    linked_list_node_t *head;
} linked_list_t;

In plain terms

Each carriage knows only the next carriage — not where the whole train is stored. Add a carriage at the front: hook the new one to the old head, then move head forward.

Insert at front (fast)

1
2
3
4
5
6
void insert_front(linked_list_t *list, int value) {
    linked_list_node_t *node = malloc(sizeof(linked_list_node_t));
    node->data = value;
    node->next = list->head;
    list->head = node;
}

Constant time — you never shift elements.

Insert at end (slow without tail pointer)

Walk from head until next == NULL, then attach. For many appends, keep a tail pointer too.

Remove a node

Find the node before the one to delete, then:

1
2
prev->next = victim->next;
free(victim);

Forgetting free leaks memory. Deleting the head is a special case — update head to head->next.

Doubly linked lists — forward and backward

Each node also points back:

1
2
NULL ← [ • | 10 | • ] ⇄ [ • | 20 | • ] ⇄ [ • | 30 | • ] → NULL
        head                                              tail

Deleting a known node is O(1) — you do not need to scan from head to find the predecessor. Linux kernel lists and some timer implementations use this pattern.

Queues — first in, first out (FIFO)

Like a line at a shop: the first person waiting is served first. Perfect for work waiting to be processed: UART bytes to transmit, sensor samples, RTOS messages.

1
front → [ A ] → [ B ] → [ C ] → rear

1
2
3
4
5
6
7
8
9
typedef struct queue_node {
    int data;
    struct queue_node *next;
} queue_node_t;

typedef struct queue {
    queue_node_t *first;
    queue_node_t *last;
} queue_t;

Enqueue (add at rear):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void enqueue(queue_t *q, int value) {
    queue_node_t *node = malloc(sizeof(queue_node_t));
    node->data = value;
    node->next = NULL;
    if (q->last)
        q->last->next = node;
    else
        q->first = node;   /* queue was empty */
    q->last = node;
}

Dequeue (remove from front):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int dequeue(queue_t *q, int *ok) {
    if (!q->first) { *ok = 0; return 0; }
    queue_node_t *node = q->first;
    int value = node->data;
    q->first = node->next;
    if (!q->first) q->last = NULL;
    free(node);
    *ok = 1;
    return value;
}

Producer ISR enqueues; main loop dequeues — classic embedded pattern. FreeRTOS queues hide this behind an API but the idea is the same.

Stacks — last in, first out (LIFO)

Like a stack of plates: you add and remove from the top only. Used for nested work: parsing expressions, undo history, depth-first search, or "most recent interrupt request first" in some designs.

1
2
3
4
5
6
7
8
typedef struct stack_node {
    int data;
    struct stack_node *next;
} stack_node_t;

typedef struct stack {
    stack_node_t *top;
} stack_t;

Push puts a node on top; pop removes it. Both are O(1). An empty stack has top == NULL.

Binary search trees — sorted hierarchy

A binary tree node has at most two children: left and right. In a binary search tree (BST), every left descendant is smaller, every right descendant is larger than the node's key.

1
2
3
4
5
        8
       / \
      5   14
     / \    \
    3   7    16

1
2
3
4
5
typedef struct tree_node {
    int key;
    struct tree_node *left;
    struct tree_node *right;
} tree_node_t;

Search for value v: start at root. If v < key, go left; if v > key, go right; if equal, found. Each step eliminates half the tree on average.

In-order traversal (left, node, right) prints keys sorted — useful for debugging.

Watch out: inserting sorted input (1, 2, 3, 4, 5…) creates a straight line — search becomes O(n). Balanced trees (AVL, red-black) fix that in advanced courses.

Big-O in plain language

Notation Meaning for n items
O(1) Time stays constant — ideal for real-time hot paths
O(log n) Doubling data adds one extra step — good for large maps
O(n) Scan everything once — OK for small n on MCU

Embedded tip: a sorted array of 20 entries with linear search may beat a complex tree — simpler code, predictable memory.

Embedded-friendly alternatives

Textbook approach Production firmware
malloc per node Static pool of N nodes
Linked list Circular buffer in fixed array
BST Sorted array + binary search for small n

Determinism and no fragmentation often matter more than textbook purity.

Relevant topics

Starting points

  1. Draw insert-front on paper — three boxes, three arrows, before coding.
  2. Implement queue enqueue/dequeue; enqueue A, B, C — dequeue must return A, B, C.
  3. Insert 8, 5, 14, 3, 7, 16 into a BST — draw the tree, then in-order print.
  4. Replace malloc with a fixed array of 32 nodes for a list.

Focus points

  • Empty structure — always check head == NULL / top == NULL.
  • Free removed nodes or return to pool.
  • Queue needs last for O(1) enqueue.
  • BST balance — know worst case degrades to a list.

Key points

  • Linked lists chain nodes with pointers; flexible size, extra memory per node.
  • Queues are FIFO; stacks are LIFO — match the problem's ordering rule.
  • BST keeps keys sorted for search; left smaller, right greater.
  • On MCUs, prefer pools and ring buffers when malloc is risky.