name: c-data-structures description: Use when fundamental C data structures including arrays, structs, linked lists, trees, and hash tables with memory-efficient implementations. allowed-tools:

Read
Write
Edit
Grep
Glob
Bash

C Data Structures

Data structures in C require manual memory management and careful pointer manipulation. Understanding how to implement and use fundamental data structures is essential for building efficient C applications. This skill covers arrays, structs, linked lists, trees, and hash tables.

Arrays and Dynamic Arrays

Arrays provide contiguous memory storage with O(1) access time. Dynamic arrays offer flexibility at the cost of occasional reallocation.

Static Arrays

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

// Working with static arrays
void array_operations(void) {
    int numbers[5] = {1, 2, 3, 4, 5};

    // Array length (only works with static arrays)
    size_t length = sizeof(numbers) / sizeof(numbers[0]);

    // Iterate through array
    for (size_t i = 0; i < length; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    // Array as function parameter (decays to pointer)
    int sum = 0;
    for (size_t i = 0; i < length; i++) {
        sum += numbers[i];
    }
    printf("Sum: %d\n", sum);
}

Dynamic Arrays

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

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

// Initialize dynamic array
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;
}

// Append element to array
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;
}

// Free array memory
void array_free(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

Structs and Data Modeling

Structs group related data together, enabling complex data modeling and organization.

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

// Define a structure
typedef struct {
    char name[50];
    int age;
    float salary;
} Employee;

// Create and initialize struct
Employee *employee_create(const char *name, int age, float salary) {
    Employee *emp = malloc(sizeof(Employee));
    if (!emp) return NULL;

    strncpy(emp->name, name, sizeof(emp->name) - 1);
    emp->name[sizeof(emp->name) - 1] = '\0';
    emp->age = age;
    emp->salary = salary;

    return emp;
}

// Struct with nested structures
typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point top_left;
    Point bottom_right;
} Rectangle;

// Calculate rectangle area
int rectangle_area(const Rectangle *rect) {
    int width = rect->bottom_right.x - rect->top_left.x;
    int height = rect->bottom_right.y - rect->top_left.y;
    return width * height;
}

Linked Lists

Linked lists provide dynamic insertion and deletion with O(1) time complexity for operations at known positions.

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

// Singly linked list node
typedef struct Node {
    int data;
    struct Node *next;
} Node;

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

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

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

// Insert at beginning
int list_prepend(LinkedList *list, int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;

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

    return 0;
}

// Insert at end
int list_append(LinkedList *list, int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;

    node->data = data;
    node->next = NULL;

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

    list->size++;
    return 0;
}

// Remove first occurrence of value
int list_remove(LinkedList *list, int data) {
    if (!list->head) return -1;

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

    // Remove other node
    Node *current = list->head;
    while (current->next) {
        if (current->next->data == data) {
            Node *temp = current->next;
            current->next = current->next->next;
            free(temp);
            list->size--;
            return 0;
        }
        current = current->next;
    }

    return -1;  // Not found
}

// Free entire list
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 Lists

Doubly linked lists allow bidirectional traversal with previous and next pointers.

#include <stdlib.h>

// Doubly linked list node
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

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

// Create new doubly linked list
DoublyLinkedList *dlist_create(void) {
    DoublyLinkedList *list = malloc(sizeof(DoublyLinkedList));
    if (!list) return NULL;

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

// Insert at end (O(1) with tail pointer)
int dlist_append(DoublyLinkedList *list, int data) {
    DNode *node = malloc(sizeof(DNode));
    if (!node) return -1;

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

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

    list->tail = node;
    list->size++;
    return 0;
}

// Remove from end (O(1) with tail pointer)
int dlist_pop(DoublyLinkedList *list, int *data) {
    if (!list->tail) return -1;

    *data = list->tail->data;
    DNode *node = list->tail;

    if (list->tail->prev) {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
    } else {
        list->head = NULL;
        list->tail = NULL;
    }

    free(node);
    list->size--;
    return 0;
}

Binary Trees

Binary trees organize data hierarchically, enabling efficient searching, insertion, and traversal operations.

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

// Binary tree node
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Create new tree node
TreeNode *tree_node_create(int data) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (!node) return NULL;

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

// Insert into binary search tree
TreeNode *bst_insert(TreeNode *root, int data) {
    if (!root) {
        return tree_node_create(data);
    }

    if (data < root->data) {
        root->left = bst_insert(root->left, data);
    } else if (data > root->data) {
        root->right = bst_insert(root->right, data);
    }

    return root;
}

// Search in binary search tree
TreeNode *bst_search(TreeNode *root, int data) {
    if (!root || root->data == data) {
        return root;
    }

    if (data < root->data) {
        return bst_search(root->left, data);
    }

    return bst_search(root->right, data);
}

// In-order traversal (sorted order for BST)
void tree_inorder(TreeNode *root) {
    if (!root) return;

    tree_inorder(root->left);
    printf("%d ", root->data);
    tree_inorder(root->right);
}

// Free entire tree
void tree_free(TreeNode *root) {
    if (!root) return;

    tree_free(root->left);
    tree_free(root->right);
    free(root);
}

Hash Tables

Hash tables provide O(1) average-case insertion, deletion, and lookup using hash functions and collision resolution.

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

#define HASH_TABLE_SIZE 100

// Hash table entry
typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;  // For collision chaining
} Entry;

// Hash table
typedef struct {
    Entry *buckets[HASH_TABLE_SIZE];
    size_t size;
} HashTable;

// Hash function (djb2)
unsigned long hash(const char *str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }

    return hash % HASH_TABLE_SIZE;
}

// Create hash table
HashTable *hashtable_create(void) {
    HashTable *table = malloc(sizeof(HashTable));
    if (!table) return NULL;

    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        table->buckets[i] = NULL;
    }
    table->size = 0;

    return table;
}

// Insert or update key-value pair
int hashtable_set(HashTable *table, const char *key, int value) {
    unsigned long index = hash(key);
    Entry *entry = table->buckets[index];

    // Check if key exists
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return 0;
        }
        entry = entry->next;
    }

    // Create new entry
    Entry *new_entry = malloc(sizeof(Entry));
    if (!new_entry) return -1;

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

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

    return 0;
}

// Get value by key
int hashtable_get(HashTable *table, const char *key, int *value) {
    unsigned long index = hash(key);
    Entry *entry = table->buckets[index];

    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            *value = entry->value;
            return 0;
        }
        entry = entry->next;
    }

    return -1;  // Not found
}

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

    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Entry *entry = table->buckets[i];
        while (entry) {
            Entry *next = entry->next;
            free(entry->key);
            free(entry);
            entry = next;
        }
    }

    free(table);
}

Stacks and Queues

Stacks (LIFO) and queues (FIFO) are fundamental abstract data types with many applications.

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

// Stack using dynamic array
typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Stack;

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

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

    stack->size = 0;
    stack->capacity = initial_capacity;
    return stack;
}

// Push to stack
int stack_push(Stack *stack, int value) {
    if (stack->size >= stack->capacity) {
        size_t new_capacity = stack->capacity * 2;
        int *new_data = realloc(stack->data,
                                new_capacity * sizeof(int));
        if (!new_data) return -1;

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

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

// Pop from stack
int stack_pop(Stack *stack, int *value) {
    if (stack->size == 0) return -1;

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

// Peek top of stack
int stack_peek(Stack *stack, int *value) {
    if (stack->size == 0) return -1;

    *value = stack->data[stack->size - 1];
    return 0;
}

// Check if stack is empty
bool stack_is_empty(Stack *stack) {
    return stack->size == 0;
}

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

Best Practices

Always initialize pointers to NULL to prevent accessing uninitialized memory
Check malloc/calloc/realloc return values before using allocated memory
Free all allocated memory in reverse order of allocation
Use sizeof(variable) instead of sizeof(type) for better maintainability
Keep track of data structure sizes to avoid buffer overflows
Use const pointers when functions should not modify data
Initialize all struct members explicitly to avoid undefined behavior
Document time and space complexity for data structure operations
Use typedef to create cleaner type names for structs and pointers
Implement destroy/free functions for all custom data structures

Common Pitfalls

Forgetting to free memory, causing memory leaks in long-running programs
Accessing freed memory (use-after-free), causing undefined behavior
Freeing same memory twice (double-free), causing heap corruption
Not checking for NULL after malloc, leading to segmentation faults
Using uninitialized pointers, accessing random memory locations
Buffer overflows from not tracking array bounds properly
Returning pointers to local variables that go out of scope
Not updating size counters after insertion/deletion operations
Circular references in linked structures without proper cleanup
Using shallow copies when deep copies are needed, sharing mutable state

When to Use C Data Structures

Use C data structures when you need:

Maximum control over memory layout and access patterns
Minimal memory overhead without garbage collection
Predictable performance characteristics for real-time systems
Integration with hardware or low-level system interfaces
Building foundational libraries used by other languages
Understanding how high-level abstractions work internally
Educational purposes for learning algorithms and complexity analysis
Embedded systems with limited resources requiring efficiency
Performance-critical code where every byte matters
Legacy codebases requiring maintenance or extension

c-data-structures

$ 安裝