c-data-structures

C Data Structures

Master implementing fundamental and advanced data structures in C with proper memory management, including arrays, linked lists, trees, hash tables, and more.

Arrays and Pointers

Static Arrays

#include <stdio.h>

void print_array(int arr[], size_t size) { for (size_t i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); }

int main(void) { int numbers[5] = {10, 20, 30, 40, 50};

printf("Array size: %zu bytes\n", sizeof(numbers));
printf("Element size: %zu bytes\n", sizeof(numbers[0]));
printf("Number of elements: %zu\n", sizeof(numbers) / sizeof(numbers[0]));

print_array(numbers, 5);

// Array indexing is pointer arithmetic
printf("numbers[2] = %d\n", numbers[2]);
printf("*(numbers + 2) = %d\n", *(numbers + 2));

return 0;

}

Dynamic Arrays

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

typedef struct { int *data; size_t size; size_t capacity; } DynamicArray;

DynamicArray *array_create(size_t initial_capacity) { DynamicArray *arr = malloc(sizeof(DynamicArray)); if (!arr) return NULL;

arr->data = malloc(initial_capacity * sizeof(int));
if (!arr->data) {
    free(arr);
    return NULL;
}

arr->size = 0;
arr->capacity = initial_capacity;
return arr;

}

int array_push(DynamicArray *arr, int value) { if (arr->size >= arr->capacity) { size_t new_capacity = arr->capacity * 2; int *new_data = realloc(arr->data, new_capacity * sizeof(int)); if (!new_data) return -1;

    arr->data = new_data;
    arr->capacity = new_capacity;
}

arr->data[arr->size++] = value;
return 0;

}

int array_get(DynamicArray *arr, size_t index) { if (index >= arr->size) { fprintf(stderr, "Index out of bounds\n"); return -1; } return arr->data[index]; }

void array_free(DynamicArray *arr) { if (arr) { free(arr->data); free(arr); } }

int main(void) { DynamicArray *arr = array_create(2);

array_push(arr, 10);
array_push(arr, 20);
array_push(arr, 30);  // Will trigger resize

for (size_t i = 0; i &#x3C; arr->size; i++) {
    printf("%d ", array_get(arr, i));
}
printf("\n");

array_free(arr);
return 0;

}

Structs and Unions

Structs

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

typedef struct { char name[50]; int age; float gpa; } Student;

typedef struct { int x; int y; } Point;

// Struct with flexible array member typedef struct { size_t length; char data[]; // Flexible array member } String;

String *string_create(const char *str) { size_t len = strlen(str); String *s = malloc(sizeof(String) + len + 1); if (!s) return NULL;

s->length = len;
strcpy(s->data, str);
return s;

}

void demonstrate_structs(void) { Student s1 = {"Alice", 20, 3.8}; Student s2;

// Copy struct
s2 = s1;
s2.age = 21;

printf("s1: %s, age %d\n", s1.name, s1.age);
printf("s2: %s, age %d\n", s2.name, s2.age);

// Struct pointer
Student *sp = &#x26;s1;
printf("Name via pointer: %s\n", sp->name);

// Flexible array member
String *str = string_create("Hello, World!");
printf("String: %s (length: %zu)\n", str->data, str->length);
free(str);

}

Unions

#include <stdio.h> #include <stdint.h>

typedef union { uint32_t word; uint16_t halfwords[2]; uint8_t bytes[4]; } Word;

typedef enum { TYPE_INT, TYPE_FLOAT, TYPE_STRING } ValueType;

typedef struct { ValueType type; union { int i; float f; char *s; } value; } Value;

void print_value(Value *v) { switch (v->type) { case TYPE_INT: printf("int: %d\n", v->value.i); break; case TYPE_FLOAT: printf("float: %f\n", v->value.f); break; case TYPE_STRING: printf("string: %s\n", v->value.s); break; } }

int main(void) { Word w = {.word = 0x12345678}; printf("Word: 0x%08x\n", w.word); printf("Byte 0: 0x%02x\n", w.bytes[0]); printf("Byte 1: 0x%02x\n", w.bytes[1]);

Value v1 = {TYPE_INT, {.i = 42}};
Value v2 = {TYPE_FLOAT, {.f = 3.14}};
Value v3 = {TYPE_STRING, {.s = "Hello"}};

print_value(&#x26;v1);
print_value(&#x26;v2);
print_value(&#x26;v3);

return 0;

}

Linked Lists

Singly Linked List

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

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

typedef struct { Node *head; size_t size; } LinkedList;

LinkedList *list_create(void) { LinkedList *list = malloc(sizeof(LinkedList)); if (!list) return NULL;

list->head = NULL;
list->size = 0;
return list;

}

int list_push_front(LinkedList *list, int data) { Node *new_node = malloc(sizeof(Node)); if (!new_node) return -1;

new_node->data = data;
new_node->next = list->head;
list->head = new_node;
list->size++;

return 0;

}

int list_push_back(LinkedList *list, int data) { Node *new_node = malloc(sizeof(Node)); if (!new_node) return -1;

new_node->data = data;
new_node->next = NULL;

if (!list->head) {
    list->head = new_node;
} else {
    Node *current = list->head;
    while (current->next) {
        current = current->next;
    }
    current->next = new_node;
}

list->size++;
return 0;

}

int list_remove(LinkedList *list, int data) { if (!list->head) return -1;

if (list->head->data == data) {
    Node *temp = list->head;
    list->head = list->head->next;
    free(temp);
    list->size--;
    return 0;
}

Node *current = list->head;
while (current->next &#x26;&#x26; current->next->data != data) {
    current = current->next;
}

if (current->next) {
    Node *temp = current->next;
    current->next = current->next->next;
    free(temp);
    list->size--;
    return 0;
}

return -1;

}

void list_print(LinkedList *list) { Node *current = list->head; while (current) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); }

void list_free(LinkedList *list) { if (!list) return;

Node *current = list->head;
while (current) {
    Node *next = current->next;
    free(current);
    current = next;
}
free(list);

}

Doubly Linked List

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

typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;

typedef struct { DNode *head; DNode *tail; size_t size; } DoublyLinkedList;

DoublyLinkedList *dlist_create(void) { DoublyLinkedList *list = malloc(sizeof(DoublyLinkedList)); if (!list) return NULL;

list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;

}

int dlist_push_back(DoublyLinkedList *list, int data) { DNode *new_node = malloc(sizeof(DNode)); if (!new_node) return -1;

new_node->data = data;
new_node->next = NULL;
new_node->prev = list->tail;

if (!list->head) {
    list->head = new_node;
} else {
    list->tail->next = new_node;
}

list->tail = new_node;
list->size++;
return 0;

}

int dlist_push_front(DoublyLinkedList *list, int data) { DNode *new_node = malloc(sizeof(DNode)); if (!new_node) return -1;

new_node->data = data;
new_node->prev = NULL;
new_node->next = list->head;

if (!list->head) {
    list->tail = new_node;
} else {
    list->head->prev = new_node;
}

list->head = new_node;
list->size++;
return 0;

}

void dlist_print_forward(DoublyLinkedList *list) { DNode *current = list->head; while (current) { printf("%d <-> ", current->data); current = current->next; } printf("NULL\n"); }

void dlist_print_backward(DoublyLinkedList *list) { DNode *current = list->tail; while (current) { printf("%d <-> ", current->data); current = current->prev; } printf("NULL\n"); }

void dlist_free(DoublyLinkedList *list) { if (!list) return;

DNode *current = list->head;
while (current) {
    DNode *next = current->next;
    free(current);
    current = next;
}
free(list);

}

Stacks and Queues

Stack (Array-based)

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

typedef struct { int *data; size_t capacity; int top; } Stack;

Stack *stack_create(size_t capacity) { Stack *stack = malloc(sizeof(Stack)); if (!stack) return NULL;

stack->data = malloc(capacity * sizeof(int));
if (!stack->data) {
    free(stack);
    return NULL;
}

stack->capacity = capacity;
stack->top = -1;
return stack;

}

bool stack_is_empty(Stack *stack) { return stack->top == -1; }

bool stack_is_full(Stack *stack) { return stack->top == (int)(stack->capacity - 1); }

int stack_push(Stack *stack, int value) { if (stack_is_full(stack)) { return -1; }

stack->data[++stack->top] = value;
return 0;

}

int stack_pop(Stack *stack, int *value) { if (stack_is_empty(stack)) { return -1; }

*value = stack->data[stack->top--];
return 0;

}

int stack_peek(Stack *stack, int *value) { if (stack_is_empty(stack)) { return -1; }

*value = stack->data[stack->top];
return 0;

}

void stack_free(Stack *stack) { if (stack) { free(stack->data); free(stack); } }

Queue (Circular Buffer)

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

typedef struct { int *data; size_t capacity; size_t front; size_t rear; size_t size; } Queue;

Queue *queue_create(size_t capacity) { Queue *queue = malloc(sizeof(Queue)); if (!queue) return NULL;

queue->data = malloc(capacity * sizeof(int));
if (!queue->data) {
    free(queue);
    return NULL;
}

queue->capacity = capacity;
queue->front = 0;
queue->rear = 0;
queue->size = 0;
return queue;

}

bool queue_is_empty(Queue *queue) { return queue->size == 0; }

bool queue_is_full(Queue *queue) { return queue->size == queue->capacity; }

int queue_enqueue(Queue *queue, int value) { if (queue_is_full(queue)) { return -1; }

queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->size++;
return 0;

}

int queue_dequeue(Queue *queue, int *value) { if (queue_is_empty(queue)) { return -1; }

*value = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
return 0;

}

void queue_free(Queue *queue) { if (queue) { free(queue->data); free(queue); } }

Binary Trees

Binary Search Tree

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

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

typedef struct { TreeNode *root; size_t size; } BST;

BST *bst_create(void) { BST *tree = malloc(sizeof(BST)); if (!tree) return NULL;

tree->root = NULL;
tree->size = 0;
return tree;

}

TreeNode *create_node(int data) { TreeNode *node = malloc(sizeof(TreeNode)); if (!node) return NULL;

node->data = data;
node->left = NULL;
node->right = NULL;
return node;

}

TreeNode *bst_insert_helper(TreeNode *node, int data) { if (!node) { return create_node(data); }

if (data &#x3C; node->data) {
    node->left = bst_insert_helper(node->left, data);
} else if (data > node->data) {
    node->right = bst_insert_helper(node->right, data);
}

return node;

}

int bst_insert(BST *tree, int data) { tree->root = bst_insert_helper(tree->root, data); if (tree->root) { tree->size++; return 0; } return -1; }

TreeNode *bst_search_helper(TreeNode *node, int data) { if (!node || node->data == data) { return node; }

if (data &#x3C; node->data) {
    return bst_search_helper(node->left, data);
}
return bst_search_helper(node->right, data);

}

bool bst_search(BST *tree, int data) { return bst_search_helper(tree->root, data) != NULL; }

TreeNode *find_min(TreeNode *node) { while (node->left) { node = node->left; } return node; }

TreeNode *bst_delete_helper(TreeNode *node, int data) { if (!node) return NULL;

if (data &#x3C; node->data) {
    node->left = bst_delete_helper(node->left, data);
} else if (data > node->data) {
    node->right = bst_delete_helper(node->right, data);
} else {
    // Node to delete found
    if (!node->left) {
        TreeNode *temp = node->right;
        free(node);
        return temp;
    } else if (!node->right) {
        TreeNode *temp = node->left;
        free(node);
        return temp;
    }

    // Node has two children
    TreeNode *temp = find_min(node->right);
    node->data = temp->data;
    node->right = bst_delete_helper(node->right, temp->data);
}

return node;

}

void inorder_traversal(TreeNode *node) { if (node) { inorder_traversal(node->left); printf("%d ", node->data); inorder_traversal(node->right); } }

void preorder_traversal(TreeNode *node) { if (node) { printf("%d ", node->data); preorder_traversal(node->left); preorder_traversal(node->right); } }

void postorder_traversal(TreeNode *node) { if (node) { postorder_traversal(node->left); postorder_traversal(node->right); printf("%d ", node->data); } }

void bst_free_helper(TreeNode *node) { if (node) { bst_free_helper(node->left); bst_free_helper(node->right); free(node); } }

void bst_free(BST *tree) { if (tree) { bst_free_helper(tree->root); free(tree); } }

Hash Tables

Simple Hash Table

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

typedef struct HashNode { char *key; int value; struct HashNode *next; } HashNode;

typedef struct { HashNode **buckets; size_t capacity; size_t size; } HashTable;

unsigned long hash(const char *str, size_t capacity) { unsigned long hash = 5381; int c;

while ((c = *str++)) {
    hash = ((hash &#x3C;&#x3C; 5) + hash) + c;
}

return hash % capacity;

}

HashTable *hashtable_create(size_t capacity) { HashTable *table = malloc(sizeof(HashTable)); if (!table) return NULL;

table->buckets = calloc(capacity, sizeof(HashNode *));
if (!table->buckets) {
    free(table);
    return NULL;
}

table->capacity = capacity;
table->size = 0;
return table;

}

int hashtable_insert(HashTable *table, const char *key, int value) { unsigned long index = hash(key, table->capacity);

// Check if key exists
HashNode *current = table->buckets[index];
while (current) {
    if (strcmp(current->key, key) == 0) {
        current->value = value;
        return 0;
    }
    current = current->next;
}

// Create new node
HashNode *new_node = malloc(sizeof(HashNode));
if (!new_node) return -1;

new_node->key = strdup(key);
if (!new_node->key) {
    free(new_node);
    return -1;
}

new_node->value = value;
new_node->next = table->buckets[index];
table->buckets[index] = new_node;
table->size++;

return 0;

}

bool hashtable_get(HashTable *table, const char *key, int *value) { unsigned long index = hash(key, table->capacity);

HashNode *current = table->buckets[index];
while (current) {
    if (strcmp(current->key, key) == 0) {
        *value = current->value;
        return true;
    }
    current = current->next;
}

return false;

}

bool hashtable_remove(HashTable *table, const char *key) { unsigned long index = hash(key, table->capacity);

HashNode *current = table->buckets[index];
HashNode *prev = NULL;

while (current) {
    if (strcmp(current->key, key) == 0) {
        if (prev) {
            prev->next = current->next;
        } else {
            table->buckets[index] = current->next;
        }

        free(current->key);
        free(current);
        table->size--;
        return true;
    }

    prev = current;
    current = current->next;
}

return false;

}

void hashtable_free(HashTable *table) { if (!table) return;

for (size_t i = 0; i &#x3C; table->capacity; i++) {
    HashNode *current = table->buckets[i];
    while (current) {
        HashNode *next = current->next;
        free(current->key);
        free(current);
        current = next;
    }
}

free(table->buckets);
free(table);

}

Memory Management

Custom Allocator

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

typedef struct Block { size_t size; bool is_free; struct Block *next; } Block;

typedef struct { void *memory; size_t total_size; Block *free_list; } Allocator;

Allocator *allocator_create(size_t size) { Allocator *alloc = malloc(sizeof(Allocator)); if (!alloc) return NULL;

alloc->memory = malloc(size);
if (!alloc->memory) {
    free(alloc);
    return NULL;
}

alloc->total_size = size;

// Initialize free list with one large block
alloc->free_list = (Block *)alloc->memory;
alloc->free_list->size = size - sizeof(Block);
alloc->free_list->is_free = true;
alloc->free_list->next = NULL;

return alloc;

}

void *allocator_alloc(Allocator *alloc, size_t size) { Block *current = alloc->free_list; Block *prev = NULL;

// Find first fit
while (current) {
    if (current->is_free &#x26;&#x26; current->size >= size) {
        // Split block if there's enough space
        if (current->size >= size + sizeof(Block) + 1) {
            Block *new_block = (Block *)((char *)current + sizeof(Block) + size);
            new_block->size = current->size - size - sizeof(Block);
            new_block->is_free = true;
            new_block->next = current->next;

            current->size = size;
            current->next = new_block;
        }

        current->is_free = false;
        return (char *)current + sizeof(Block);
    }

    prev = current;
    current = current->next;
}

return NULL;

}

void allocator_free(Allocator *alloc, void *ptr) { if (!ptr) return;

Block *block = (Block *)((char *)ptr - sizeof(Block));
block->is_free = true;

// Coalesce with next block if free
if (block->next &#x26;&#x26; block->next->is_free) {
    block->size += sizeof(Block) + block->next->size;
    block->next = block->next->next;
}

// Coalesce with previous block if free
Block *current = alloc->free_list;
while (current &#x26;&#x26; current->next != block) {
    current = current->next;
}

if (current &#x26;&#x26; current->is_free) {
    current->size += sizeof(Block) + block->size;
    current->next = block->next;
}

}

void allocator_destroy(Allocator *alloc) { if (alloc) { free(alloc->memory); free(alloc); } }

Best Practices

Always Initialize Pointers: Initialize pointers to NULL to avoid accessing uninitialized memory. Check for NULL before dereferencing.

Free All Allocated Memory: Every malloc/calloc/realloc must have a corresponding free. Track allocations carefully to prevent memory leaks.

Check Allocation Success: Always check if malloc/calloc/realloc returns NULL before using the allocated memory.

Avoid Dangling Pointers: Set pointers to NULL after freeing them. Never use a pointer after the memory it points to has been freed.

Use Size Parameters: Pass size parameters to functions instead of hardcoding array sizes for better reusability and safety.

Implement Consistent Cleanup: Provide free/destroy functions for all data structures that perform complete cleanup in reverse order of allocation.

Validate Input Parameters: Check for NULL pointers and invalid indices before performing operations on data structures.

Use typedef for Clarity: Use typedef for structs to improve code readability and reduce verbosity.

Consider Cache Locality: Arrange struct members and access patterns to maximize CPU cache efficiency, especially for performance-critical code.

Document Ownership: Clearly document which functions own allocated memory and which are responsible for freeing it.

Common Pitfalls

Memory Leaks: Forgetting to free allocated memory or losing the last reference to allocated memory causes memory leaks.

Buffer Overflows: Writing beyond allocated array bounds corrupts memory and causes undefined behavior or security vulnerabilities.

Use After Free: Accessing memory after it has been freed causes undefined behavior and potential crashes.

Double Free: Freeing the same memory twice corrupts the heap and causes crashes. Always set pointers to NULL after freeing.

Uninitialized Pointers: Using pointers before initialization leads to accessing random memory addresses.

Shallow Copy Issues: Copying structs with pointers creates multiple references to the same memory, leading to double frees or unintended modifications.

Off-by-One Errors: Incorrect loop bounds or array indexing causes buffer overflows or missed elements.

Integer Overflow: Not checking for overflow when calculating sizes for allocation can lead to undersized allocations.

Mixing sizeof Operand Types: Using sizeof with pointer instead of pointed-to type (sizeof(ptr) vs sizeof(*ptr)) allocates wrong size.

Inefficient Reallocation: Reallocating for every element instead of doubling capacity leads to poor performance (O(n²) instead of amortized O(1)).

When to Use This Skill

Use C data structures when you need to:

Implement custom data structures for specific performance requirements
Work on embedded systems with constrained memory
Build system-level software requiring fine-grained memory control
Create high-performance applications where memory layout matters
Develop kernel modules or device drivers
Understand low-level memory management for learning purposes
Port algorithms from textbooks to production code
Build foundational libraries and frameworks
Optimize memory usage in resource-constrained environments
Implement custom allocators or memory pools

This skill is essential for systems programmers, embedded developers, performance engineers, and anyone working with C in resource-constrained or performance-critical environments.

Resources

Books

The C Programming Language by Kernighan and Ritchie
Data Structures Using C by Reema Thareja
Algorithms in C by Robert Sedgewick
Understanding and Using C Pointers by Richard Reese

Online Resources

GeeksforGeeks C Data Structures: https://www.geeksforgeeks.org/data-structures/
Learn-C.org: https://www.learn-c.org/
C Data Structures Tutorial: https://www.tutorialspoint.com/data_structures_algorithms/index.htm
Visualgo: https://visualgo.net/ (Algorithm visualizations)

Tools

Valgrind: Memory error detection and profiling
AddressSanitizer: Fast memory error detector
GDB: GNU debugger with memory inspection
cppcheck: Static analysis tool for C/C++
Electric Fence: Library for detecting memory allocation errors

c-data-structures

Safety Notice

Copy this and send it to your AI assistant to learn

Source Transparency

Related Skills

android-jetpack-compose

fastapi-async-patterns

storybook-story-writing

atomic-design-fundamentals