|$ curl https://forge-ai.dev/api/markdown?path=docs/c/data-structures

$cat docs/c-—-data-structures.md

updated Recently·60 min read·published

C — Data Structures

◆C◆Data Structures◆Linked Lists◆Trees◆Advanced◆Advanced🎯Free Tools

Why Data Structures?

Data structures are the backbone of efficient software. They determine how data is stored, accessed, and manipulated. Choosing the right structure can mean the difference between an O(n) scan and an O(1) lookup. C gives you no abstraction hiding the cost — every allocation, every pointer dereference, every memory layout choice is yours to make. This page covers the six foundational data structures every C programmer must master: linked lists, stacks, queues, trees, hash tables, and graphs.

📝

note

Every data structure below is implemented from scratch using only pointers and malloc/free. No libraries. This is how you truly understand what is happening under the hood.

Linked Lists

A linked list is a sequence of nodes where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not store elements in contiguous memory — they are dynamically allocated and connected via pointers. This makes insertion and deletion at arbitrary positions efficient, but random access is slow because you must traverse from the head.

Singly Linked List

The simplest linked list. Each node points to the next node, and the last node points to NULL. Traversal is one-directional — you can only move forward, never backward.

singly_linked_list.c

1	#include <stdio.h>
2	#include <stdlib.h>
3
4	typedef struct Node {
5	int data;
6	struct Node *next;
7	} Node;
8
9	/* Create a new node */
10	Node *create_node(int data) {
11	Node *node = malloc(sizeof(Node));
12	if (!node) return NULL;
13	node->data = data;
14	node->next = NULL;
15	return node;
16	}
17
18	/* Insert at the beginning — O(1) */
19	void insert_head(Node **head, int data) {
20	Node *node = create_node(data);
21	node->next = *head;
22	*head = node;
23	}
24
25	/* Insert at the end — O(n) */
26	void insert_tail(Node **head, int data) {
27	Node *node = create_node(data);
28	if (*head == NULL) {
29	*head = node;
30	return;
31	}
32	Node curr = head;
33	while (curr->next)
34	curr = curr->next;
35	curr->next = node;
36	}
37
38	/* Insert at position — O(n) */
39	void insert_at(Node **head, int pos, int data) {
40	if (pos == 0) {
41	insert_head(head, data);
42	return;
43	}
44	Node curr = head;
45	for (int i = 0; i < pos - 1 && curr; i++)
46	curr = curr->next;
47	if (!curr) return;
48	Node *node = create_node(data);
49	node->next = curr->next;
50	curr->next = node;
51	}
52
53	/* Delete first occurrence of value — O(n) */
54	void delete_value(Node **head, int data) {
55	if (*head == NULL) return;
56	if ((*head)->data == data) {
57	Node temp = head;
58	head = (head)->next;
59	free(temp);
60	return;
61	}
62	Node curr = head;
63	while (curr->next && curr->next->data != data)
64	curr = curr->next;
65	if (curr->next) {
66	Node *temp = curr->next;
67	curr->next = temp->next;
68	free(temp);
69	}
70	}
71
72	/* Search for value — O(n) */
73	Node search(Node head, int data) {
74	Node *curr = head;
75	while (curr) {
76	if (curr->data == data)
77	return curr;
78	curr = curr->next;
79	}
80	return NULL;
81	}
82
83	/* Traverse and print */
84	void print_list(Node *head) {
85	Node *curr = head;
86	while (curr) {
87	printf("%d -> ", curr->data);
88	curr = curr->next;
89	}
90	printf("NULL\n");
91	}
92
93	/* Free the entire list */
94	void free_list(Node **head) {
95	Node curr = head;
96	while (curr) {
97	Node *temp = curr;
98	curr = curr->next;
99	free(temp);
100	}
101	*head = NULL;
102	}
103
104	int main(void) {
105	Node *list = NULL;
106
107	insert_tail(&list, 10);
108	insert_tail(&list, 20);
109	insert_tail(&list, 30);
110	insert_head(&list, 5);
111	insert_at(&list, 2, 15);
112
113	print_list(list); /* 5 -> 10 -> 15 -> 20 -> 30 -> NULL */
114
115	delete_value(&list, 15);
116	print_list(list); /* 5 -> 10 -> 20 -> 30 -> NULL */
117
118	Node *found = search(list, 20);
119	if (found) printf("Found: %d\n", found->data);
120
121	free_list(&list);
122	return 0;
123	}

ℹ

info

Always pass Node **head (pointer to pointer) when modifying the head. A single pointer pass-by-value would lose the updated head reference after the function returns.

Doubly Linked List

Each node has both a next and a prev pointer, enabling traversal in both directions. This costs extra memory per node but makes certain operations simpler — for instance, deleting a node when you already have a pointer to it is O(1) because you can access the previous node directly.

doubly_linked_list.c

1	typedef struct DNode {
2	int data;
3	struct DNode *prev;
4	struct DNode *next;
5	} DNode;
6
7	typedef struct {
8	DNode *head;
9	DNode *tail;
10	int size;
11	} DoublyList;
12
13	DNode *dnode_create(int data) {
14	DNode *node = malloc(sizeof(DNode));
15	if (!node) return NULL;
16	node->data = data;
17	node->prev = NULL;
18	node->next = NULL;
19	return node;
20	}
21
22	DoublyList *dlist_create(void) {
23	DoublyList *list = malloc(sizeof(DoublyList));
24	if (!list) return NULL;
25	list->head = NULL;
26	list->tail = NULL;
27	list->size = 0;
28	return list;
29	}
30
31	/* Insert at head — O(1) */
32	void dlist_insert_head(DoublyList *list, int data) {
33	DNode *node = dnode_create(data);
34	if (list->head == NULL) {
35	list->head = list->tail = node;
36	} else {
37	node->next = list->head;
38	list->head->prev = node;
39	list->head = node;
40	}
41	list->size++;
42	}
43
44	/* Insert at tail — O(1) with tail pointer */
45	void dlist_insert_tail(DoublyList *list, int data) {
46	DNode *node = dnode_create(data);
47	if (list->tail == NULL) {
48	list->head = list->tail = node;
49	} else {
50	node->prev = list->tail;
51	list->tail->next = node;
52	list->tail = node;
53	}
54	list->size++;
55	}
56
57	/* Delete a known node — O(1) */
58	void dnode_delete(DoublyList list, DNode node) {
59	if (node->prev)
60	node->prev->next = node->next;
61	else
62	list->head = node->next;
63
64	if (node->next)
65	node->next->prev = node->prev;
66	else
67	list->tail = node->prev;
68
69	free(node);
70	list->size--;
71	}
72
73	/* Forward traversal */
74	void dlist_print_forward(DoublyList *list) {
75	DNode *curr = list->head;
76	while (curr) {
77	printf("%d <-> ", curr->data);
78	curr = curr->next;
79	}
80	printf("NULL\n");
81	}
82
83	/* Backward traversal */
84	void dlist_print_backward(DoublyList *list) {
85	DNode *curr = list->tail;
86	while (curr) {
87	printf("%d <-> ", curr->data);
88	curr = curr->prev;
89	}
90	printf("NULL\n");
91	}
92
93	void dlist_free(DoublyList *list) {
94	DNode *curr = list->head;
95	while (curr) {
96	DNode *temp = curr;
97	curr = curr->next;
98	free(temp);
99	}
100	free(list);
101	}

Circular Linked List

In a circular linked list, the last node points back to the first node instead of NULL. This is useful for round-robin scheduling, music playlists that loop, and any scenario where you need to cycle through elements continuously.

circular_linked_list.c

1	/* Circular singly linked list — last->next wraps to head */
2	void cinsert(Node **head, int data) {
3	Node *node = create_node(data);
4	if (*head == NULL) {
5	node->next = node; /* points to itself */
6	*head = node;
7	return;
8	}
9	/* Insert after head, then rotate data so new node becomes tail */
10	node->next = (*head)->next;
11	(*head)->next = node;
12	/* Swap data to make it a tail insertion */
13	int tmp = (*head)->data;
14	(*head)->data = node->data;
15	node->data = tmp;
16	}
17
18	void cprint(Node *head) {
19	if (!head) return;
20	Node *curr = head;
21	do {
22	printf("%d -> ", curr->data);
23	curr = curr->next;
24	} while (curr != head);
25	printf("(back to %d)\n", head->data);
26	}

Linked List Time Complexity

Operation	Singly	Doubly	Notes
Insert at head	`O(1)`	`O(1)`	Simply update pointers
Insert at tail	`O(n)`	`O(1)`	Singly must traverse; doubly has tail pointer
Insert at position	`O(n)`	`O(n)`	Must traverse to position
Delete by value	`O(n)`	`O(n)`	Search then delete
Delete known node	`O(n)`	`O(1)`	Doubly can access prev directly
Search	`O(n)`	`O(n)`	No random access
Access by index	`O(n)`	`O(n)`	Must traverse from head

✓

best practice

Use linked lists when you need frequent insertions/deletions and don't need random access. Use arrays when you need fast index-based access and cache-friendly memory layout.

Stacks

A stack follows the Last-In-First-Out (LIFO) principle. The most recently pushed element is the first one popped. Think of a stack of plates — you always add to and remove from the top. Stacks are fundamental to function call management, expression parsing, undo systems, and backtracking algorithms.

Array-Based Stack

stack.c

1	#define STACK_MAX 1024
2
3	typedef struct {
4	int data[STACK_MAX];
5	int top; /* index of top element, -1 when empty */
6	} Stack;
7
8	void stack_init(Stack *s) {
9	s->top = -1;
10	}
11
12	int stack_is_empty(Stack *s) {
13	return s->top == -1;
14	}
15
16	int stack_is_full(Stack *s) {
17	return s->top == STACK_MAX - 1;
18	}
19
20	int stack_push(Stack *s, int value) {
21	if (stack_is_full(s)) return 0;
22	s->data[++s->top] = value;
23	return 1;
24	}
25
26	int stack_pop(Stack s, int value) {
27	if (stack_is_empty(s)) return 0;
28	*value = s->data[s->top--];
29	return 1;
30	}
31
32	int stack_peek(Stack s, int value) {
33	if (stack_is_empty(s)) return 0;
34	*value = s->data[s->top];
35	return 1;
36	}
37
38	int stack_size(Stack *s) {
39	return s->top + 1;
40	}
41
42	/* Demo: bracket matching */
43	int is_matching_pair(char open, char close) {
44	return (open == '(' && close == ')') \|\|
45	(open == '{' && close == '}') \|\|
46	(open == '[' && close == ']');
47	}
48
49	int check_brackets(const char *expr) {
50	Stack s;
51	stack_init(&s);
52	for (int i = 0; expr[i]; i++) {
53	char c = expr[i];
54	if (c == '(' \|\| c == '{' \|\| c == '[') {
55	stack_push(&s, c);
56	} else if (c == ')' \|\| c == '}' \|\| c == ']') {
57	int top;
58	if (stack_is_empty(&s) \|\| !stack_pop(&s, &top))
59	return 0;
60	if (!is_matching_pair((char)top, c))
61	return 0;
62	}
63	}
64	return stack_is_empty(&s);
65	}
66
67	int main(void) {
68	Stack s;
69	stack_init(&s);
70	stack_push(&s, 10);
71	stack_push(&s, 20);
72	stack_push(&s, 30);
73
74	int val;
75	stack_pop(&s, &val);
76	printf("Popped: %d\n", val); /* 30 */
77
78	stack_peek(&s, &val);
79	printf("Top: %d\n", val); /* 20 */
80
81	printf(""(({}))" balanced: %s\n",
82	check_brackets("(({}))") ? "yes" : "no");
83	printf(""({[}]" balanced: %s\n",
84	check_brackets("({[}]") ? "yes" : "no");
85
86	return 0;
87	}

Linked List Stack

A linked list-based stack has no fixed capacity — it grows as long as memory is available. Push and pop are both O(1) since they operate at the head of the list.

linked_stack.c

1	typedef struct LNode {
2	int data;
3	struct LNode *next;
4	} LNode;
5
6	typedef struct {
7	LNode *top;
8	int size;
9	} LStack;
10
11	void lstack_init(LStack *s) {
12	s->top = NULL;
13	s->size = 0;
14	}
15
16	int lstack_push(LStack *s, int data) {
17	LNode *node = malloc(sizeof(LNode));
18	if (!node) return 0;
19	node->data = data;
20	node->next = s->top;
21	s->top = node;
22	s->size++;
23	return 1;
24	}
25
26	int lstack_pop(LStack s, int data) {
27	if (!s->top) return 0;
28	LNode *temp = s->top;
29	*data = temp->data;
30	s->top = temp->next;
31	free(temp);
32	s->size--;
33	return 1;
34	}
35
36	void lstack_free(LStack *s) {
37	int dummy;
38	while (lstack_pop(s, &dummy));
39	}

Stack Applications

Application	How Stack Is Used
Function call stack	Each call pushes a frame; return pops it. Local variables live on this stack.
Expression evaluation	Convert infix to postfix (shunting-yard), then evaluate using a stack.
Undo/Redo	Push actions onto undo stack; pop to undo. Push onto redo stack to redo.
Bracket matching	Push opening brackets; pop and verify on closing brackets.
DFS traversal	Push neighbors onto stack; pop to visit next node.

Queues

A queue follows the First-In-First-Out (FIFO) principle. Elements are enqueued at the back and dequeued from the front. Think of a line at a store — the first person in line is the first to be served. Queues are essential for BFS, task scheduling, producer-consumer patterns, and buffering.

Circular Queue (Array-Based)

A naive array queue wastes space as elements are dequeued from the front. A circular queue wraps around using modulo arithmetic, reusing the freed slots. The queue is full when (rear + 1) % capacity == front.

circular_queue.c

1	#define QUEUE_CAP 256
2
3	typedef struct {
4	int data[QUEUE_CAP];
5	int front; /* index of first element */
6	int rear; /* index of last element */
7	int count;
8	} CircularQueue;
9
10	void cq_init(CircularQueue *q) {
11	q->front = 0;
12	q->rear = -1;
13	q->count = 0;
14	}
15
16	int cq_is_empty(CircularQueue *q) {
17	return q->count == 0;
18	}
19
20	int cq_is_full(CircularQueue *q) {
21	return q->count == QUEUE_CAP;
22	}
23
24	int cq_enqueue(CircularQueue *q, int val) {
25	if (cq_is_full(q)) return 0;
26	q->rear = (q->rear + 1) % QUEUE_CAP;
27	q->data[q->rear] = val;
28	q->count++;
29	return 1;
30	}
31
32	int cq_dequeue(CircularQueue q, int val) {
33	if (cq_is_empty(q)) return 0;
34	*val = q->data[q->front];
35	q->front = (q->front + 1) % QUEUE_CAP;
36	q->count--;
37	return 1;
38	}
39
40	int cq_peek(CircularQueue q, int val) {
41	if (cq_is_empty(q)) return 0;
42	*val = q->data[q->front];
43	return 1;
44	}
45
46	int cq_size(CircularQueue *q) {
47	return q->count;
48	}
49
50	int main(void) {
51	CircularQueue q;
52	cq_init(&q);
53
54	cq_enqueue(&q, 10);
55	cq_enqueue(&q, 20);
56	cq_enqueue(&q, 30);
57
58	int val;
59	cq_dequeue(&q, &val);
60	printf("Dequeued: %d\n", val); /* 10 */
61
62	cq_enqueue(&q, 40);
63	cq_enqueue(&q, 50); /* wraps around if near end */
64
65	printf("Front: ");
66	cq_peek(&q, &val);
67	printf("%d\n", val); /* 20 */
68
69	printf("Size: %d\n", cq_size(&q));
70	return 0;
71	}

Linked List Queue

linked_queue.c

1	typedef struct QNode {
2	int data;
3	struct QNode *next;
4	} QNode;
5
6	typedef struct {
7	QNode *front;
8	QNode *rear;
9	int size;
10	} LinkedQueue;
11
12	void lq_init(LinkedQueue *q) {
13	q->front = q->rear = NULL;
14	q->size = 0;
15	}
16
17	int lq_enqueue(LinkedQueue *q, int data) {
18	QNode *node = malloc(sizeof(QNode));
19	if (!node) return 0;
20	node->data = data;
21	node->next = NULL;
22	if (q->rear) {
23	q->rear->next = node;
24	} else {
25	q->front = node;
26	}
27	q->rear = node;
28	q->size++;
29	return 1;
30	}
31
32	int lq_dequeue(LinkedQueue q, int data) {
33	if (!q->front) return 0;
34	QNode *temp = q->front;
35	*data = temp->data;
36	q->front = temp->next;
37	if (!q->front) q->rear = NULL;
38	free(temp);
39	q->size--;
40	return 1;
41	}
42
43	void lq_free(LinkedQueue *q) {
44	int dummy;
45	while (lq_dequeue(q, &dummy));
46	}

Priority Queue (Concept)

A priority queue dequeues the highest-priority element rather than the oldest. It is typically implemented with a heap — a complete binary tree stored in an array. Each enqueued element bubbles up to its correct position; each dequeue removes the root and restores the heap property.

📝

note

A full heap-based priority queue implementation is covered under Trees. The key idea: a min-heap gives O(1) access to the minimum element and O(log n) insert and delete.

Queue Time Complexity

Operation	Array (Circular)	Linked List
Enqueue	`O(1)`	`O(1)`
Dequeue	`O(1)`	`O(1)`
Peek/Front	`O(1)`	`O(1)`
Search	`O(n)`	`O(n)`
Space	Fixed (capacity)	Dynamic (per node overhead)

Trees

A tree is a hierarchical data structure composed of nodes. Each node has a value and pointers to its children. A binary tree restricts each node to at most two children (left and right). Trees naturally represent hierarchical data — file systems, DOM, organizational charts, and decision trees.

Binary Tree Node

tree_node.c

1	#include <stdio.h>
2	#include <stdlib.h>
3
4	typedef struct TreeNode {
5	int data;
6	struct TreeNode *left;
7	struct TreeNode *right;
8	} TreeNode;
9
10	TreeNode *tree_node_create(int data) {
11	TreeNode *node = malloc(sizeof(TreeNode));
12	if (!node) return NULL;
13	node->data = data;
14	node->left = NULL;
15	node->right = NULL;
16	return node;
17	}

Tree Traversals

There are three standard depth-first traversals. Each visits every node exactly once, differing only in when they process the current node relative to its children.

tree_traversals.c

1	/* Inorder: Left -> Root -> Right (sorted for BST) */
2	void inorder(TreeNode *root) {
3	if (!root) return;
4	inorder(root->left);
5	printf("%d ", root->data);
6	inorder(root->right);
7	}
8
9	/* Preorder: Root -> Left -> Right (useful for copying tree) */
10	void preorder(TreeNode *root) {
11	if (!root) return;
12	printf("%d ", root->data);
13	preorder(root->left);
14	preorder(root->right);
15	}
16
17	/* Postorder: Left -> Right -> Root (useful for deletion) */
18	void postorder(TreeNode *root) {
19	if (!root) return;
20	postorder(root->left);
21	postorder(root->right);
22	printf("%d ", root->data);
23	}
24
25	/* Iterative inorder using explicit stack */
26	void inorder_iterative(TreeNode *root) {
27	TreeNode *stack[256];
28	int top = -1;
29	TreeNode *curr = root;
30
31	while (curr \|\| top >= 0) {
32	while (curr) {
33	stack[++top] = curr;
34	curr = curr->left;
35	}
36	curr = stack[top--];
37	printf("%d ", curr->data);
38	curr = curr->right;
39	}
40	}
41
42	/* Level-order (BFS) using a queue */
43	void level_order(TreeNode *root) {
44	if (!root) return;
45	TreeNode *queue[256];
46	int front = 0, rear = 0;
47	queue[rear++] = root;
48
49	while (front < rear) {
50	TreeNode *node = queue[front++];
51	printf("%d ", node->data);
52	if (node->left) queue[rear++] = node->left;
53	if (node->right) queue[rear++] = node->right;
54	}
55	}

Binary Search Tree (BST)

A BST maintains the invariant: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property makes search, insert, and delete efficient — O(log n) on average. The inorder traversal of a BST produces sorted output.

bst.c

1	/* BST Insert — O(log n) average */
2	TreeNode bst_insert(TreeNode root, int data) {
3	if (!root) return tree_node_create(data);
4	if (data < root->data)
5	root->left = bst_insert(root->left, data);
6	else if (data > root->data)
7	root->right = bst_insert(root->right, data);
8	/* duplicate values ignored */
9	return root;
10	}
11
12	/* BST Search — O(log n) average */
13	TreeNode bst_search(TreeNode root, int data) {
14	if (!root) return NULL;
15	if (data == root->data) return root;
16	if (data < root->data)
17	return bst_search(root->left, data);
18	return bst_search(root->right, data);
19	}
20
21	/* Find minimum value node (leftmost) */
22	TreeNode bst_min(TreeNode root) {
23	while (root && root->left)
24	root = root->left;
25	return root;
26	}
27
28	/* BST Delete — O(log n) average
29	* Case 1: Leaf node (no children) — just free it
30	* Case 2: One child — replace node with its child
31	* Case 3: Two children — replace with inorder successor
32	* (smallest in right subtree), then delete successor
33	*/
34	TreeNode bst_delete(TreeNode root, int data) {
35	if (!root) return NULL;
36
37	if (data < root->data) {
38	root->left = bst_delete(root->left, data);
39	} else if (data > root->data) {
40	root->right = bst_delete(root->right, data);
41	} else {
42	/* Found the node to delete */
43	if (!root->left) {
44	TreeNode *temp = root->right;
45	free(root);
46	return temp;
47	}
48	if (!root->right) {
49	TreeNode *temp = root->left;
50	free(root);
51	return temp;
52	}
53	/* Two children: find inorder successor */
54	TreeNode *succ = bst_min(root->right);
55	root->data = succ->data;
56	root->right = bst_delete(root->right, succ->data);
57	}
58	return root;
59	}
60
61	/* Count nodes */
62	int tree_count(TreeNode *root) {
63	if (!root) return 0;
64	return 1 + tree_count(root->left) + tree_count(root->right);
65	}
66
67	/* Compute height */
68	int tree_height(TreeNode *root) {
69	if (!root) return -1;
70	int lh = tree_height(root->left);
71	int rh = tree_height(root->right);
72	return 1 + (lh > rh ? lh : rh);
73	}
74
75	/* Free entire tree */
76	void tree_free(TreeNode *root) {
77	if (!root) return;
78	tree_free(root->left);
79	tree_free(root->right);
80	free(root);
81	}
82
83	int main(void) {
84	TreeNode *root = NULL;
85
86	root = bst_insert(root, 50);
87	bst_insert(root, 30);
88	bst_insert(root, 70);
89	bst_insert(root, 20);
90	bst_insert(root, 40);
91	bst_insert(root, 60);
92	bst_insert(root, 80);
93
94	printf("Inorder: ");
95	inorder(root);
96	printf("\n"); /* 20 30 40 50 60 70 80 */
97
98	printf("Preorder: ");
99	preorder(root);
100	printf("\n");
101
102	printf("Level: ");
103	level_order(root);
104	printf("\n");
105
106	TreeNode *found = bst_search(root, 40);
107	printf("Search 40: %s\n", found ? "found" : "not found");
108
109	root = bst_delete(root, 30); /* Case: two children */
110	printf("After del 30: ");
111	inorder(root);
112	printf("\n");
113
114	printf("Height: %d\n", tree_height(root));
115	printf("Count: %d\n", tree_count(root));
116
117	tree_free(root);
118	return 0;
119	}

⚠

warning

An unbalanced BST degrades to a linked list in the worst case (sorted input), giving O(n) operations. Self-balancing trees like AVL or Red-Black trees guarantee O(log n) by rotating nodes after insertions and deletions. In C, you must implement these rotations manually.

BST Time Complexity

Operation	Average	Worst (unbalanced)
Search	`O(log n)`	`O(n)`
Insert	`O(log n)`	`O(n)`
Delete	`O(log n)`	`O(n)`
Inorder traversal	`O(n)`	`O(n)`

Hash Tables

A hash table maps keys to values using a hash function that converts a key into an array index. With a good hash function and low load factor, lookup, insert, and delete are all O(1) on average. C has no built-in hash map, so you build one from scratch using an array of buckets and a collision resolution strategy.

Chaining (Separate Chaining)

Each bucket holds a linked list. When two keys hash to the same index, they coexist in the same list. This is the simplest collision resolution strategy.

hashmap_chaining.c

1	#include <stdio.h>
2	#include <stdlib.h>
3	#include <string.h>
4
5	#define HT_SIZE 64
6
7	typedef struct HEntry {
8	char *key;
9	int value;
10	struct HEntry *next;
11	} HEntry;
12
13	typedef struct {
14	HEntry *buckets[HT_SIZE];
15	int count;
16	} HashMap;
17
18	/* djb2 hash function */
19	unsigned long hash_string(const char *key) {
20	unsigned long h = 5381;
21	for (int i = 0; key[i]; i++)
22	h = ((h << 5) + h) + (unsigned char)key[i];
23	return h % HT_SIZE;
24	}
25
26	HashMap *hashmap_create(void) {
27	HashMap *map = calloc(1, sizeof(HashMap));
28	return map;
29	}
30
31	void hashmap_put(HashMap map, const char key, int value) {
32	unsigned long idx = hash_string(key);
33
34	/* Update existing key */
35	for (HEntry *e = map->buckets[idx]; e; e = e->next) {
36	if (strcmp(e->key, key) == 0) {
37	e->value = value;
38	return;
39	}
40	}
41
42	/* Insert new entry at head of chain */
43	HEntry *entry = malloc(sizeof(HEntry));
44	entry->key = strdup(key);
45	entry->value = value;
46	entry->next = map->buckets[idx];
47	map->buckets[idx] = entry;
48	map->count++;
49	}
50
51	int hashmap_get(HashMap map, const char key, int *out) {
52	unsigned long idx = hash_string(key);
53	for (HEntry *e = map->buckets[idx]; e; e = e->next) {
54	if (strcmp(e->key, key) == 0) {
55	*out = e->value;
56	return 1;
57	}
58	}
59	return 0;
60	}
61
62	int hashmap_delete(HashMap map, const char key) {
63	unsigned long idx = hash_string(key);
64	HEntry **pp = &map->buckets[idx];
65	while (*pp) {
66	if (strcmp((*pp)->key, key) == 0) {
67	HEntry temp = pp;
68	*pp = temp->next;
69	free(temp->key);
70	free(temp);
71	map->count--;
72	return 1;
73	}
74	pp = &(*pp)->next;
75	}
76	return 0;
77	}
78
79	void hashmap_free(HashMap *map) {
80	for (int i = 0; i < HT_SIZE; i++) {
81	HEntry *e = map->buckets[i];
82	while (e) {
83	HEntry *temp = e;
84	e = e->next;
85	free(temp->key);
86	free(temp);
87	}
88	}
89	free(map);
90	}
91
92	int main(void) {
93	HashMap *map = hashmap_create();
94
95	hashmap_put(map, "name", 42);
96	hashmap_put(map, "age", 30);
97	hashmap_put(map, "score", 95);
98
99	int val;
100	if (hashmap_get(map, "name", &val))
101	printf("name = %d\n", val); /* 42 */
102
103	hashmap_delete(map, "age");
104	printf("age exists: %s\n",
105	hashmap_get(map, "age", &val) ? "yes" : "no");
106
107	printf("Entries: %d\n", map->count);
108	hashmap_free(map);
109	return 0;
110	}

Open Addressing

Instead of chaining, open addressing stores all entries in the array itself. On collision, it probes subsequent slots until an empty one is found. Common probing strategies: linear probing (check idx+1, idx+2, ...), quadratic probing (check idx+1², idx+2², ...), and double hashing (use a second hash function for the step size).

hashmap_open_addressing.c

1	#define OA_SIZE 128
2	#define OA_USED 1
3	#define OA_DEL 2
4
5	typedef struct {
6	char *key;
7	int value;
8	int state; /* 0=empty, OA_USED, OA_DEL */
9	} OAEntry;
10
11	typedef struct {
12	OAEntry entries[OA_SIZE];
13	int count;
14	} OAHashMap;
15
16	int oa_hash(const char *key, int attempt) {
17	unsigned long h = 5381;
18	for (int i = 0; key[i]; i++)
19	h = ((h << 5) + h) + (unsigned char)key[i];
20	/* Double hashing: step = 1 + (h % (OA_SIZE - 1)) */
21	unsigned long h2 = 1 + (h % (OA_SIZE - 1));
22	return (h + attempt * h2) % OA_SIZE;
23	}
24
25	void oa_put(OAHashMap map, const char key, int value) {
26	for (int i = 0; i < OA_SIZE; i++) {
27	int idx = oa_hash(key, i);
28	if (map->entries[idx].state != OA_USED \|\|
29	strcmp(map->entries[idx].key, key) == 0) {
30	if (map->entries[idx].state != OA_USED)
31	map->count++;
32	map->entries[idx].key = strdup(key);
33	map->entries[idx].value = value;
34	map->entries[idx].state = OA_USED;
35	return;
36	}
37	}
38	}
39
40	int oa_get(OAHashMap map, const char key, int *out) {
41	for (int i = 0; i < OA_SIZE; i++) {
42	int idx = oa_hash(key, i);
43	if (map->entries[idx].state == 0)
44	return 0; /* not found */
45	if (map->entries[idx].state == OA_USED &&
46	strcmp(map->entries[idx].key, key) == 0) {
47	*out = map->entries[idx].value;
48	return 1;
49	}
50	}
51	return 0;
52	}
53
54	int oa_delete(OAHashMap map, const char key) {
55	for (int i = 0; i < OA_SIZE; i++) {
56	int idx = oa_hash(key, i);
57	if (map->entries[idx].state == 0)
58	return 0;
59	if (map->entries[idx].state == OA_USED &&
60	strcmp(map->entries[idx].key, key) == 0) {
61	free(map->entries[idx].key);
62	map->entries[idx].state = OA_DEL;
63	map->entries[idx].key = NULL;
64	map->count--;
65	return 1;
66	}
67	}
68	return 0;
69	}

Load Factor and Rehashing

The load factor is count / capacity. As it grows beyond ~0.7, performance degrades because collisions increase. Rehashing allocates a new, larger array and reinserts all entries — an O(n) operation that amortizes over many inserts.

hashmap_rehash.c

1	void hashmap_rehash(HashMap *map) {
2	int old_cap = HT_SIZE;
3	HEntry **old_buckets = map->buckets;
4
5	/* Allocate new bucket array (zeroed) */
6	memset(map->buckets, 0, sizeof(map->buckets));
7	map->count = 0;
8
9	/* Reinsert all entries */
10	for (int i = 0; i < old_cap; i++) {
11	HEntry *e = old_buckets[i];
12	while (e) {
13	HEntry *next = e->next;
14	unsigned long idx = hash_string(e->key);
15	e->next = map->buckets[idx];
16	map->buckets[idx] = e;
17	map->count++;
18	e = next;
19	}
20	}
21	}

Hash Table Time Complexity

Operation	Average	Worst	Strategy
Insert	`O(1)`	`O(n)`	Low load factor keeps avg constant
Lookup	`O(1)`	`O(n)`	Worst: all keys hash to same bucket
Delete	`O(1)`	`O(n)`	Open addressing needs tombstone markers
Rehash	`O(n)`	`O(n)`	Amortized O(1) per insert

🔥

pro tip

Keep the load factor below 0.75. For open addressing, keep it below 0.5. If your hash function is poor (many collisions), even a low load factor won't save you. Choose a hash function suited to your key distribution.

Graphs

A graph is a set of vertices connected by edges. Graphs model networks, dependencies, social connections, and countless real-world relationships. There are two primary representations in C: adjacency matrices and adjacency lists.

Adjacency Matrix

A 2D array where adj[i][j] = 1 means an edge exists from vertex i to vertex j. Simple but uses O(V²) space regardless of edge count. Best for dense graphs.

adj_matrix.c

1	#define MAX_V 100
2
3	typedef struct {
4	int adj[MAX_V][MAX_V];
5	int n; /* number of vertices */
6	} AdjMatrix;
7
8	void am_init(AdjMatrix *g, int n) {
9	g->n = n;
10	for (int i = 0; i < n; i++)
11	for (int j = 0; j < n; j++)
12	g->adj[i][j] = 0;
13	}
14
15	void am_add_edge(AdjMatrix *g, int u, int v) {
16	g->adj[u][v] = 1;
17	g->adj[v][u] = 1; /* remove for directed graph */
18	}
19
20	void am_print(AdjMatrix *g) {
21	printf(" ");
22	for (int j = 0; j < g->n; j++) printf("%d ", j);
23	printf("\n");
24	for (int i = 0; i < g->n; i++) {
25	printf("%d: ", i);
26	for (int j = 0; j < g->n; j++)
27	printf("%d ", g->adj[i][j]);
28	printf("\n");
29	}
30	}

Adjacency List

Each vertex has a linked list of its neighbors. Uses O(V + E) space — efficient for sparse graphs. This is how most graph algorithms are implemented in practice.

adj_list.c

1	typedef struct Edge {
2	int dest;
3	int weight;
4	struct Edge *next;
5	} Edge;
6
7	typedef struct {
8	Edge *adj[MAX_V];
9	int n;
10	} AdjList;
11
12	void al_init(AdjList *g, int n) {
13	g->n = n;
14	for (int i = 0; i < n; i++)
15	g->adj[i] = NULL;
16	}
17
18	void al_add_edge(AdjList *g, int u, int v, int w) {
19	/* Add v to u's list */
20	Edge *e1 = malloc(sizeof(Edge));
21	e1->dest = v;
22	e1->weight = w;
23	e1->next = g->adj[u];
24	g->adj[u] = e1;
25
26	/* Add u to v's list (undirected) */
27	Edge *e2 = malloc(sizeof(Edge));
28	e2->dest = u;
29	e2->weight = w;
30	e2->next = g->adj[v];
31	g->adj[v] = e2;
32	}
33
34	void al_print(AdjList *g) {
35	for (int i = 0; i < g->n; i++) {
36	printf("%d: ", i);
37	for (Edge *e = g->adj[i]; e; e = e->next)
38	printf("-> %d(w=%d) ", e->dest, e->weight);
39	printf("\n");
40	}
41	}
42
43	void al_free(AdjList *g) {
44	for (int i = 0; i < g->n; i++) {
45	Edge *e = g->adj[i];
46	while (e) {
47	Edge *temp = e;
48	e = e->next;
49	free(temp);
50	}
51	}
52	}

Matrix vs List

Property	Adjacency Matrix	Adjacency List
Space	`O(V²)`	`O(V + E)`
Check edge exists	`O(1)`	`O(degree)`
List neighbors	`O(V)`	`O(degree)`
Add edge	`O(1)`	`O(1)`
Best for	Dense graphs (E near V²)	Sparse graphs (E near V)

Data Structure Comparison

Choosing the right data structure depends on your access patterns, memory constraints, and performance requirements. This table summarizes the trade-offs.

Structure	Access	Search	Insert	Delete	Space	Use Cases
Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	O(n)	Fixed-size collections, lookup tables
Singly Linked List	`O(n)`	`O(n)`	`O(1)` head	`O(1)` known	O(n) + ptrs	Stacks, frequent insert/delete at head
Doubly Linked List	`O(n)`	`O(n)`	`O(1)` both ends	`O(1)` known	O(n) + 2 ptrs	LRU cache, undo/redo, browser history
Stack	`O(n)`	`O(n)`	`O(1)` top	`O(1)` top	O(n)	Function calls, expression eval, DFS
Queue	`O(n)`	`O(n)`	`O(1)` rear	`O(1)` front	O(n)	BFS, scheduling, buffering
BST	`O(n)`	`O(log n)`	`O(log n)`	`O(log n)`	O(n)	Sorted data, range queries, dictionaries
Hash Table	`O(n)`	`O(1)` avg	`O(1)` avg	`O(1)` avg	O(n)	Fast lookup, caching, counting

$Blueprint — Engineering Documentation·Section ID: C-DATA-STRUCTURES·Revision: 1.0

X GitHub YouTube Instagram Facebook Discord Telegram Buy me a coffee Sponsor