c-data-structures

What this skill does

# 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

```c
#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

```c
#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.

```c
#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.

```c
#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.

```c
#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.

```c
#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);
}

//