Data structures allow programmers to store, organize, and manage data efficiently. Simple arrays or sequential storage often aren't enough for complex tasks, which is why structures like lists, trees, and hash tables are used.

In C, structures (struct) provide a flexible way to implement many of these data structures.

Linked Lists

A linked list is useful when the number of elements can change dynamically. Each node contains data and a pointer to the next node.

Example node structure:

struct Node {
    int data;           // data in node
    struct Node* next;  // pointer to next node
};

Each node contains a data field and a next pointer. This allows you to add or remove elements anywhere in the list without reorganizing the entire structure, unlike with arrays.

Hash Table

Hash tables allow you to quickly retrieve data using a key. A hash function converts the key into an array index, where the value is stored.

Example hash table implementation:

struct Node {
    char* key;          // key
    int value;          // value
    struct Node* next;  // pointer to next node
};

struct HashTable {
    struct Node** table; // array of node pointers
    int size;            // table size
};

unsigned int hashFunction(char* key, int size) {
    unsigned int hash = 0;
    while (*key) {
        hash += *key++;
    }
    return hash % size;
}

Each element in the hash table is a linked list node containing a key and a value. The hash function converts the key into an array index, allowing fast lookups, even with large datasets.

Trees

Trees are useful for hierarchical data, fast searching, insertion, and deletion.

A binary tree is a tree where each node has at most two children: left and right.

Example hash table implementation:

struct node
{
	int data;
	struct node* left; 
	struct node* right; 
};

A node can be a parent for its children while also being a child of its parent. Binary trees provide efficient data organization and quick searching due to their logical "left-right" structure.

Stack

Used to model networks and relationships.

A stack is a data structure in which elements are added (push) and removed (pop) according to the LIFO principle - (Last In, First Out).

Example stack using an array:

// Stack structure
typedef struct {
    int data[MAX_SIZE]; 
    int top;
} Stack;

MAX_SIZE - the maximum number of elements a stack can contain.

// Push an element onto the stack
void push(Stack *stack, int value) {
    stack->data[++stack->top] = value;  // Increment top and add the element
    printf("Element %d pushed onto the stack\n", value);
}

// Pop an element from the stack
int pop(Stack *stack) {
    int value = stack->data[stack->top--];  // Retrieve the element and decrement top
    printf("Element %d popped from the stack\n", value);
    return value;
}

The element is added to the top of the stack (top). Stacks allow fast addition and removal of elements, with the last element added being the first one removed.

Using structures in C makes it possible to create flexible and powerful data structures such as arrays, linked lists, hash tables, trees, and stacks. Each structure is optimized for specific tasks, making programs more organized and efficient.