Data Structures in C

What Are Data Structures?

Data structures are the backbone of efficient programming. They define how data is organized, stored, and accessed in memory. Mastering data structures is arguably the single most impactful skill a programmer can develop.

C is the perfect language to learn data structures because it operates close to the metal, you manage memory explicitly with malloc and free, use pointers directly, and see exactly how each structure lives in memory. No abstractions hiding the complexity.

Prerequisites: Before diving in, you should be comfortable with C basics, variables, loops, functions, and most importantly, pointers. Pointers are the connective tissue of nearly every dynamic data structure in C.

Arrays

An array is the simplest and most widely used data structure. It stores elements of the same type in contiguous memory locations. In C, arrays are zero-indexed and their size is fixed at declaration (for static arrays).

#include <stdio.h>

int main() {
    // Static array — size fixed at compile time
    int arr[5] = {10, 20, 30, 40, 50};

    // Access by index — O(1)
    printf("Element at index 2: %d\n", arr[2]);

    // Traverse — O(n)
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }

    // Dynamic array using malloc
    int n = 10;
    int *dyn = (int*) malloc(n * sizeof(int));
    if (!dyn) { perror("malloc"); return 1; }

    for (int i = 0; i < n; i++) dyn[i] = i * 2;

    free(dyn);  // Always free dynamic memory!
   return 0;
    }

Linked Lists

A linked list is a dynamic data structure where each element (node) holds data and a pointer to the next node. Unlike arrays, nodes are not stored contiguously, they're scattered across the heap, linked by pointers.

Singly Linked List

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

// Node definition
typedef struct Node {
    int         data;
    struct Node *next;
} Node;

// Create a new node
Node* create_node(int val) {
    Node *n = (Node*) malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

// Prepend to front — O(1)
Node* prepend(Node *head, int val) {
    Node *n = create_node(val);
    n->next = head;
    return n;  // new head
}

// Append to end — O(n)
Node* append(Node *head, int val) {
    Node *n = create_node(val);
    if (!head) return n;
    Node *cur = head;
    while (cur->next) cur = cur->next;
    cur->next = n;
    return head;
}

// Print list
void print_list(Node *head) {
    while (head) {
        printf("%d → ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Free all nodes
void free_list(Node *head) {
    while (head) {
        Node *tmp = head->next;
        free(head);
        head = tmp;
    }
    }

int main() {
    Node *list = NULL;
    list = append(list, 10);
    list = append(list, 20);
    list = prepend(list, 5);
    print_list(list);  // 5 → 10 → 20 → NULL
    free_list(list);
    }

Stacks

A stack follows LIFO - Last In, First Out. Think of a plate stack: you add to the top (push) and remove from the top (pop). Stacks are fundamental to function call management, expression parsing, and backtracking algorithms.

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

#define MAX 100

typedef struct {
    int items[MAX];
    int top;
} Stack;

void  stack_init(Stack *s)          { s->top = -1; }
bool  stack_empty(Stack *s)        { return s->top == -1; }
bool  stack_full(Stack *s)         { return s->top == MAX - 1; }

void push(Stack *s, int val) {
    if (stack_full(s)) { printf("Stack overflow!\n"); return; }
    s->items[++s->top] = val;
  }

int pop(Stack *s) {
    if (stack_empty(s)) { printf("Stack underflow!\n"); return -1; }
    return s->items[s->top--];
  }

int peek(Stack *s) {
    if (stack_empty(s)) return -1;
    return s->items[s->top];
   }

int main() {
    Stack s;
    stack_init(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Peek: %d\n", peek(&s));   // 30
    printf("Pop:  %d\n", pop(&s));    // 30
    printf("Pop:  %d\n", pop(&s));    // 20
    }

Queues

A queue follows FIFO - First In, First Out. Like a real queue: new elements join at the rear, and elements leave from the front. The circular queue implementation avoids wasted space from naive array implementations.

#define SIZE 5
c
typedef struct {
    int items[SIZE];
    int front, rear, count;
} Queue;

void q_init(Queue *q) { q->front = q->rear = q->count = 0; }

void enqueue(Queue *q, int val) {
    if (q->count == SIZE) { printf("Queue full!\n"); return; }
    q->items[q->rear] = val;
    q->rear  = (q->rear + 1) % SIZE;  // wrap around
    q->count++;
}

int dequeue(Queue *q) {
    if (q->count == 0) { printf("Queue empty!\n"); return -1; }
    int val = q->items[q->front];
    q->front = (q->front + 1) % SIZE;
    q->count--;
    return val;
}

Binary Trees

A binary tree is a hierarchical structure where each node has at most two children - left and right. Trees are fundamental in filesystems, expression evaluation, and database indexing.

typedef struct TreeNode {
    int              data;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* new_node(int val) {
    TreeNode *n = (TreeNode*) malloc(sizeof(TreeNode));
    n->data = val; n->left = n->right = NULL;
    return n;
}

// In-order: Left → Root → Right (sorted for BST)
void inorder(TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// Pre-order: Root → Left → Right (copy/serialize)
void preorder(TreeNode *root) {
    if (!root) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// Post-order: Left → Right → Root (deletion, eval)
void postorder(TreeNode *root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// Height of tree
int height(TreeNode *root) {
    if (!root) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    return 1 + (lh > rh ? lh : rh);
}

Binary Search Trees (BST)

A BST is a binary tree with a strict ordering property: left child < parent < right child. This enables O(log n) average-case search, insertion, and deletion - making it far superior to linear search for large datasets.

// Insert into BST — O(log n) average
TreeNode* bst_insert(TreeNode *root, int val) {
    if (!root) return new_node(val);
    if (val < root->data)
        root->left  = bst_insert(root->left,  val);
    else if (val > root->data)
        root->right = bst_insert(root->right, val);
    return root;
}

// Search in BST — O(log n) average
TreeNode* bst_search(TreeNode *root, int val) {
    if (!root || root->data == val) return root;
    if (val < root->data)
        return bst_search(root->left,  val);
    return bst_search(root->right, val);
}

int main() {
    TreeNode *root = NULL;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++)
        root = bst_insert(root, vals[i]);

    inorder(root);  // → 20 30 40 50 60 70 80 (sorted!)

    TreeNode *found = bst_search(root, 40);
    printf("\nFound: %d\n", found ? found->data : -1);
}

Hash Tables

A hash table maps keys to values using a hash function that converts a key into an array index. When done right, lookups, insertions, and deletions are all O(1) on average - the fastest of any general-purpose data structure.

#define TABLE_SIZE 64

typedef struct Entry {
    char        *key;
    int          value;
    struct Entry *next;  // chaining for collisions
} Entry;

Entry *table[TABLE_SIZE] = {NULL};

// djb2 hash function
unsigned int hash(const char *key) {
    unsigned long h = 5381;
    int c;
    while ((c = *key++)) h = ((h << 5) + h) + c;
    return h % TABLE_SIZE;
}

void ht_insert(const char *key, int val) {
    unsigned int idx = hash(key);
    Entry *e = (Entry*) malloc(sizeof(Entry));
    e->key   = strdup(key);
    e->value = val;
    e->next  = table[idx];  // prepend to chain
    table[idx] = e;
}

int ht_get(const char *key) {
    unsigned int idx = hash(key);
    Entry *cur = table[idx];
    while (cur) {
        if (strcmp(cur->key, key) == 0) return cur->value;
        cur = cur->next;
    }
    return -1;  // not found
}

int main() {
    ht_insert("name",  42);
    ht_insert("score", 100);
    printf("name  → %d\n", ht_get("name"));   // 42
    printf("score → %d\n", ht_get("score"));  // 100
}

Graphs

A graph is a set of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and arbitrary connectivity. They model real-world networks: roads, social connections, dependency graphs, and more.

#define V 6

typedef struct AdjNode {
    int             dest;
    struct AdjNode *next;
} AdjNode;

AdjNode *graph[V] = {NULL};

void add_edge(int u, int v) {
    AdjNode *n = (AdjNode*) malloc(sizeof(AdjNode));
    n->dest = v; n->next = graph[u]; graph[u] = n;
    n = (AdjNode*) malloc(sizeof(AdjNode));
    n->dest = u; n->next = graph[v]; graph[v] = n;
}

// BFS — explores level by level, shortest path (unweighted)
void bfs(int start) {
    bool visited[V] = {false};
    int  queue[V], front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (AdjNode *a = graph[node]; a; a = a->next) {
            if (!visited[a->dest]) {
                visited[a->dest] = true;
                queue[rear++] = a->dest;
            }
        }
    }
}

Time Complexity Cheatsheet

Choosing the right data structure is about knowing these trade-offs cold. This table summarizes the key operations across all structures covered.

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)	O(1)	O(n)
Stack (array)	O(n)	O(n)	O(1)	O(1)	O(n)
Queue (circular)	O(n)	O(n)	O(1)	O(1)	O(n)
BST (average)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
BST (worst)	O(n)	O(n)	O(n)	O(n)	O(n)
Hash Table (avg)	O(1)	O(1)	O(1)	O(1)	O(n)
Graph (adj list)	—	O(V+E)	O(1)	O(E)	O(V+E)

What's Next?

You've now seen the foundational data structures in C - from simple arrays to complex graphs. The key insight is this: there is no universally "best" structure. The right choice depends on your access patterns, memory constraints, and the operations you need most.

To solidify your understanding, implement each structure from scratch and test it. Once comfortable, explore:

The journey from arrays to graphs mirrors the journey from a beginner to a systems programmer. Keep building, keep breaking things, and keep reading the memory layouts. That's how C teaches you to think.

About the Author
The author is passionate about Embedded Systems, C Programming, IoT, and software development, with a focus on simplifying complex technical concepts through practical learning. Inspired by Bengaluru's vibrant technology ecosystem and leading embedded training institutions such as the Indian Institute of Embedded Systems (IIES), the author creates industry-oriented content to help students and professionals build strong engineering foundations.