Data Structures in C

Data structures provide systematic ways to store, organize, and manage data, making operations like searching, inserting, or deleting faster. Algorithms are the step-by-step procedures that operate on these structures to perform tasks efficiently.

Together, DSA in C determines:

• How fast does your application run
• How much memory does it use
• How scalable and maintainable it becomes

From simple arrays to complex graphs, each structure brings a new way of thinking about problems.

Essential Concepts of C Language Data Structure:

• Efficiency: The choice of data structure impacts how efficiently an algorithm performs. Selecting the right data structure can reduce processing time and improve resource management.
• Complexity: Learning time complexity and space complexity is important when deciding which data structure and algorithm to use for a specific task.
• Scalability: The data structure and algorithm you utilize should be robust to accommodate the added data or user requests and scale performance.

In C, there are two main types of algorithms to learn and understand, which are the basis of data structures in C. Understanding these two types of core algorithms will be worthwhile in building flow and performance in applications.

Searching Algorithms:

• Linear Search: A simple algorithm in which we look at each element, one element at a time, until the requested element is found or it is determined the sorted list is exhausted.
• Binary Search: An algorithm that is faster for data that is sorted where the search field is broken down in half until the target element is found.

Sorting Algorithms

• Bubble Sort: A simple sorting algorithm that looks for adjacent elements and compares them while earning its way through the data.
• Merge Sort: A more efficient, divide-and-conquer algorithm that separates the data into smaller parts, sorts them individually and then merges them back together.
• Quick Sort: Another divide-and-conquer algorithm that selects a 'pivot' element and partitions the data around it, resulting in fast sorting with large datasets.

The C programming language provides a variety of built-in data types and also provides the flexibility to create custom, user-defined types. These data structures in C can be divided into two main categories: primitive and non-primitive data structures.

1. Primitive Data Structures

Primitive data structures are the basic types provided by C. These are simple and fundamental building blocks for creating more complex structures in Data Structures in C:

• Integer: This data type is used to store whole numbers, such as 1, -5, or 42.
• Float: A data type used to store numbers with decimal points, like 3.14 or -0.001.
• Character: This type is created to store single characters, such as 'a, 'B', or '@'.
• Double: It is similar to float, but used for storing decimal numbers with higher precision (more digits after the decimal point).
• Pointers: Pointers are variables that store the memory addresses of other variables. It's important in C for efficiency and performing operations.

2. Non-Primitive Data Structures

Non-primitive data structures are more complicated structures and are built using primitive data types. These allow for storing and organizing large sets of data in more flexible ways.

Linear Data Structure In C

• Arrays: An array is a collection of elements of the same data type in contiguous memory. An array has a fixed length and each element is access by a specific index.
• Linked Lists: A linked list is a dynamic structure complex of nodes. Each node is made of data and a specific reference or pointer to the next node in the list allowing for flexible adds and deletes of elements.
• Stacks and Queues: These are linear data structures that have elements arranged in a specific order. A stack is an example of a last in, first out (LIFO) structure, meaning that the last element put in the stack will be the first to come out. A queue structure operates on a first in, first out (FIFO) basis; in this case, the first element added will be the first element removed.

Non-Linear Data Structure In C

• Trees and Graphs: These are hierarchical or network-based data structures. A tree consists of nodes connected in a parent-child relationship, while a graph consists of nodes (also called vertices) connected by edges, essential for representing hierarchical or interconnected data, such as organizational charts or network diagrams.

Here is the detailed overview of common data structures in C that you should know to acquire a complete understanding of data structures, as they allow efficient storage, manipulation, and retrieval of data

1. Arrays In Data Structure Using C

Arrays in C are one of the simplest and most commonly used data structures. Arrays provide an efficient way to store a fixed collection of elements, and each element can be accessed via an index.

In C, an array can be declared by specifying its type by the array name and the number of elements it will contain.

int numbers[5] = {1, 2, 3, 4, 5};

Example Code:

#include <stdio.h>

int main() {
    // Declaration and initialization of the array
    int numbers[5] = {1, 2, 3, 4, 5};
    
    for (int i = 0; i < 5; i++) {
        printf("%d\n", numbers[i]);
    }

    return 0;
}

Output

1
2
3
4
5

Explanation Of Code:

• The array numbers[5] is declared and initialized with the values {1, 2, 3, 4, 5}.
• The for loop iterates through the array from index 0 to index 4 (since there are 5 elements).
• During each iteration, the printf function prints the value stored at the current index of the array.
• After executing the program, the numbers 1 to 5 are displayed, one per line.

Time and Space Complexity:

• In big O notation, the time complexity of walking through the array would be O(n).
• The space complexity is O(n).

2. Linked Lists

A linked list is a linear data structure that is made up of a series of nodes. Each node has data and a pointer (reference) to the next node in the series. Concerning an array, a linked list does not require contiguous memory to store its elements, and each node can be stored in different places in memory. The list is still conceptually maintained through a set of pointers.

Key Concepts and Relevant Terms

• Node: The basic unit of the linked list that contains data and a pointer to the next node in the list.
• Head of list: The first node of the linked list. Most operations, like insertions or deletions, begin at the head.
• Insertion: An operation that adds a new node onto the beginning, end, or any other position in the list.
• Deletion: An operation that removes a node from the list and updates the pointers correctly.
• Null: The end of the linked list is determined by a node whose next pointer is set to NULL.
• Dynamic size: Linked lists can grow or shrink at runtime, allowing flexible memory usage.
• Sequential access: Nodes must be accessed one by one from the head; random access is not possible.

Types of Linked Lists

• Singly linked lists: Each node points only to the next node. This means that traversal can only go in one direction (forward).
• Doubly linked lists: When using a doubly linked list in C each node contains pointers to the next node and the previous node, which allows traversal in both directions (forward and backward links).
• Circular linked lists: The last node points back to the first node (head), forming a circular structure. This can be implemented as singly or doubly linked.

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

// Define the structure of a node
struct Node {
    int data;          // Store the data in the node
    struct Node* next; // Pointer to the next node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for a new node
    newNode->data = data; // Assign the data
    newNode->next = NULL;  // Set the next pointer to NULL (end of the list)
    return newNode;        // Return the new node
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* temp = head; // Start from the head
    while (temp != NULL) {     // Traverse through the list
        printf("%d ", temp->data); // Print the data of each node
        temp = temp->next;     // Move to the next node
    }
}

int main() {
    // Create a linked list with three nodes
    struct Node* head = createNode(1);
    head->next = createNode(2);    // Link first node to second node
    head->next->next = createNode(3); // Link second node to third node
    
    // Print the linked list
    printList(head);  // Output should be: 1 2 3
    
    return 0;
}

Output

1 2 3

Explanation Of Code:

• We define a Node structure, where the node contains an integer (data) and a pointer next to the next node (next).
• The main() function creates 3 nodes with the values 1, 2, and 3 using the createNode() function, after creation, the next pointers are set to link the nodes.
• The printList() function traverses the list starting with the head node, printing the data of each node in turn until reaching the end of the list (when temp == NULL).

Time and Space Complexity:

• The time complexity of this code is O(n), where n is the number of nodes in the list.
• The space complexity of this code isO(n), where n is the number of nodes in the list.

Use Cases and Advantages

• Dynamic size: Suitable for applications where the number of elements can change frequently.
• Efficient insertion and deletion: Especially at the beginning or end of the list.
• Implementation of other structures: Used as the basis for stacks, queues, and graphs.

Disadvantages

• Sequential access only: No random access; the only way to get to a node is to traverse from the head.
• Extra memory: Each node has additional memory for the pointers.

3. Stacks

A stack data structure is a Last In, First Out (LIFO) structure—the last place you put an element in the stack is the first to be removed from the stack. Stacks are often used in situations, such as function calls, the undo feature of apps, and parsing expressions.

Example Code:

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

#define MAX 100

// Structure to represent a stack
struct Stack {
    int top;           // Index of the top element
    int items[MAX];    // Array to store stack elements
};

// Function to push an element onto the stack
void push(struct Stack* stack, int item) {
    if (stack->top == MAX - 1) {
        printf("Stack Overflow\n");
        return;  // Return if the stack is full
    }
    stack->items[++stack->top] = item;  // Increment top and add item
}

int pop(struct Stack* stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1;  // Return -1 if the stack is empty
    }
    return stack->items[stack->top--];  // Return the top element and decrement top
}

int main() {
    struct Stack stack;
    stack.top = -1;  // Initialize stack with an empty state

    push(&stack, 10);  // Push 10 onto the stack
    push(&stack, 20);  // Push 20 onto the stack
    
    printf("%d popped from stack\n", pop(&stack));  // Pop the top element and print it
    
    return 0;
}

Output

20 popped from stack

Explanation Of Code:

• We define a stack structure with a maximum size of 100.
• The stack starts empty, so the top is initialized to -1.
• The push function checks if the stack is full (i.e., top is at MAX-1) before adding an item. If full, it prints "Stack Overflow."
• When using the pop function, we check if the stack is empty (i.e., top = -1) before trying to remove an item; If the stack is empty, it prints "Stack Underflow."
• We first push 10 onto the stack, then we push 20 onto the stack.
• The stack now has 10 as the lowest element and 20 as the uppermost element on the stack.
• When we pop the topmost element from the stack (20), the output is displayed: "20 popped from the stack."

Time and Space Complexity:

• Time Complexity: Push and pop operations have a time complexity of O(1), as they perform constant-time work.
• Space Complexity: The space complexity is O(n) where n is the maximum number of elements on the stack (i.e. limited by the array size).

4. Queues

A queue is a linear data structure that functions based on a First In, First Out (FIFO) principle. The first element you put in the queue is the first element removed from the queue, which is just like being in a line at a ticket counter.

Key Operations:

• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove an item from the front of the queue.
• PeekFirst: View the front element without removing it.
• PeekLast: View the last element without removing it.
• isFull/isEmpty: Check if the queue is full or empty.

Variants:

• A circular queue utilizes available front spaces after deleting previous elements, thereby optimising the space for use in the circular queue. 
• In a Double-Ended Queue (Deque), an element can be inserted and removed from either end. 
• A Priority Queue removes elements based on priority rather than insertion order.

Typical Use Cases:

• Task scheduling (CPU process scheduling),
• Managing print jobs in a printer queue
• Using a breadth-first search (BFS) method in graph traversal
• Managing requests in a web server

Example Code:

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

#define MAX 5 // Maximum size of the queue

struct Queue {
    int front, rear;
    int items[MAX];
};

void enqueue(struct Queue* queue, int item) {
    if (queue->rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    queue->items[++queue->rear] = item;
}

int dequeue(struct Queue* queue) {
    if (queue->front > queue->rear) {
        printf("Queue Underflow\n");
        return -1; // Indicates empty queue
    }
    return queue->items[queue->front++];
}

int main() {
    struct Queue queue;
    queue.front = queue.rear = -1;

    enqueue(&queue, 10);
    enqueue(&queue, 20);

    printf("%d dequeued from queue\n", dequeue(&queue));

    return 0;
}

Output

10 dequeued from queue

Explanation Of Code:

• enqueue: This function adds an element to the end of the queue. It checks if the queue is full by comparing rear with MAX - 1. If it’s full, it displays a "Queue Overflow" message. Or the item is added, and rear is incremented.
• dequeue: The purpose of this function is to remove the element present at the front of the queue. First, it checks to see if the queue is empty (front > rear). If so, the message "Queue Underflow" is printed. If the queue is not empty, the element at the front is returned, and the front is incremented.
• Within the main function, two elements (10, and 20) are enqueued, and then an element is dequeued, and output to the screen.

Time and Space Complexity:

• Time Complexity: O(1)
• Space Complexity: O(n), where n is the maximum queue size

Quick Recap:

• Arrays provide fast indexed access and are useful for storing fixed-size data.
• Linked lists offer dynamic memory usage and flexible insertion and deletion.
• Understanding what is stack and queue in data structure is paramount in which the understanding of these abstract data types relates to data manipulation. The stack's LIFO data type is used for many functions we call, while queues FIFO may be used for scheduling events and processing tasks.
• Advanced data structures are designed to help students develop a more foundational understanding of memory, pointers, efficient traversal, and the real-world applications of logic which is essential in and for systems such as schedulers, file managers, and games.

Advanced data structures in C offer more sophisticated ways to represent and process data. These data structures are ideal when you need to work with more complex relationships or when managing large volumes of data efficiently.

1. Trees and Binary Trees

A tree is a non-linear, hierarchical data structure comprised of nodes connected by edges. The topmost node is referred to as the root node. A node can have zero or more children; however, in a binary tree, a node has at most two child nodes, which are called a left child and a right child. Trees are important for representing hierarchical relationships between data, like file systems and organizational charts.

Node Structure

Each node of a binary tree will typically contain:

• Data (the value that is being stored)
• Pointer to the left child node
• Pointer to the right child node
  

Binary Search Tree (BST)

A binary search tree is a special type of binary tree that has the property that:

• The left child of a node only contains nodes with values less than the node’s value.
• The right child of a node only contains nodes with a value greater than the node’s value.

This property makes searching, inserting, and removing in the tree more efficient.

This property allows efficient searching, insertion, and deletion.

Key Operations

• Insertion: Adding a new node requires finding its appropriate position in the tree to maintain the binary search tree property.
• Deletion: Removing a node requires rebuilding the tree structure to maintain its properties.
• Traversals: Visit all nodes in a specific order:
  
  • In-order Traversal: Left child → Root → Right child (yields sorted order in BST)
  • Pre-order Traversal: Root → Left child → Right child
  • Post-order Traversal: Left child → Right child → Root

Example Code: Node Structure and In-Order Traversal in C

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

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

struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);

    printf("In-order traversal: ");
    inorder(root);  // Output: 5 10 15

    return 0;
}

Advantages

• Efficient searching and sorting: This is particularly true when dealing with binary search trees.
• Hierarchical data representation: Naturally generates tree-like relationships.
• Fast insertion and deletion: More complex than linear structures.

Disadvantages

• Complexity: More pointers in each node that require extra memory.
• Memory usage: Requires extra memory for pointers in each node.

Applications

• Searching and sorting: Binary search trees.
• Expression parsing: Syntax trees.
• Priority queues: Heaps (a special type of binary tree).
• Hierarchical data: File systems, organizational charts

2. Heaps

A heap is a specialized tree-based data structure that satisfies the heap property. Heaps are most commonly implemented as arrays, allowing efficient access and manipulation of elements.

Key Concepts and Relevant Terms

• Heap Property: A max-heap has every parent node greater than, or equal to its children. A min-heap has every parent node less than, or equal to its children.
• Max-Heap: Largest element is at the root.
• Min-Heap: Smallest element is at the root.
• Array Implementation: Heaps are usually stored in arrays. For a node at index i:
  
  • Parent: (i-1)/2
  • Left child: 2i+1
  • Right child: 2i+2
• Insert: Insert a new element, and restore the heap property by heapifying up.
• Deleteroot/Extractmax:Remove the root element (either max or min), replace it with the last element, and restore the heap property by heapifying down.
• Heapify/Heapifydown: Refers to procedures to restore the heap property after insertion or deletion.
• Heap Overflow: Heap overflow occurs when attempting to insert into a full heap.
• Heap Sort: An efficient sorting algorithm that exploits heaps.
• Priority Queues: Heaps are often used to store priority queues, in which the order of elements is determined by priority.

Example: Max-Heap Implementation in C

#include <stdio.h>
#define MAX 100

int heap[MAX];
int size = 0;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Insert a new element into the heap
void insert(int value) {
    if (size >= MAX) {
        printf("Heap overflow\n");
        return;
    }

    heap[size] = value;
    int i = size;
    size++;

    while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(&heap[(i - 1) / 2], &heap[i]);
        i = (i - 1) / 2;
    }
}

// Heapify down from index i
void heapifydown(int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && heap[left] > heap[largest])
        largest = left;

    if (right < size && heap[right] > heap[largest])
        largest = right;

    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        heapifydown(largest);
    }
}

// Remove and return the maximum element (root)
int extractmax() {
    if (size == 0) {
        printf("Heap underflow\n");
        return -1;
    }

    int root = heap[0];
    heap[0] = heap[size - 1];
    size--;
    heapifydown(0);

    return root;
}

Primary Use Cases

• Priority Queues: Manage a task an efficient manner depending on priority.
• Heap Sort: Sort elements in O(n log n) time.
• Graph Algorithms: Flexible for other types of algorithms, such as Dijkstra’s algorithm.

3. Graph

A graph is a non-linear data structure representing a collection of vertices (also referred to as nodes) and a collection of edges that link pairs of vertices. Graphs are excellent for modeling relationships or networks, such as social networks, transportation systems, and communication networks. 

Key Concepts and Relevant Terms

• Vertices (nodes): The basic elements or points in a graph. 
• Edges: Connections between pairs of vertices. 
• G(V, E): Standard representation of a graph. V is used to describe the set of vertices in the graph, and E represents the set of edges in the graph. 
• Adjacency List: A representation where each vertex stores a list of its adjacent vertices.
• Directed Graphs: Edges have a direction, going from one vertex to another.
• Undirected Graphs: Edges are not directed; the connection is bidirectional.
• Weighted Graphs: Each edge has a weight or cost that is associated with it.
• Connected Graphs: Every vertex has a path connected to other pairs of vertices.
• Disjoint Graphs: The graph has multiple disconnected components.
• Graph Algorithms: Algorithms such as BFS, DFS, and other shortest path algorithms can be utilized on graphs. 
• Network Representation: Graphs are frequently used to represent and display networks of computers, social interactions, or interconnections.

Graph Representation in C

Graphs can be represented in several different ways, however, the most common representations are an adjacency list (suggested) or an adjacency matrix (less preferred) is one way to represent the structure of a graph. Adjacency list is preferred as an efficient sparse graph representation.

Adjacency List Example in C:

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src (undirected graph)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("Vertex %d: ", v);

        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    return 0;
}

Common Scenarios Where Graphs are Applied

• Network representation: Having computer networks, social networks and transportation systems represented.
• Pathfinding: Dijkstra's and Bryth-First Search/Depth- first search algorithms.
• Scheduling: Dependency graphs for project planning.
• Connected and Disjoint Graphs: Analyzing connectedness within networks.
• Weighted Graphs: Modelling costs, distances or capacities of real-world problems.

4. Hashing

Hashing is a method for mapping data (for example, keys) to a fixed-size value (the "hash value/digest") using a mathematical method (the "hash function"). This process leads to more efficient searches, inserts and deletes in data structures such as "hash tables".

Key Concepts and Relevant Terms

• Hash Function: The mathematical expression representing data as an indexed hash value.
• Hash Value: The output of the hash function, which will be used as the index in the hash table.
• Hash Table: A data structure that uses hash values to store data for constant-time access.
• Constant-Time Access: If all goes well, searching, inserting, and deleting all take O(1) time.
• Collision: When two different keys get hashed into the same value.
• Collision Resolution Techniques: Techniques to handle collisions may include;
  
  • Chaining: Where each table index points to a linked list of entries.
  • Open Addressing: where the algorithm looks for the next slot in the table if a collision occurs.
• Efficient Searching and Deletion: Hash tables are good data structures for searching and deletion in constant time.
• Databases and File Systems: Hashing is common in databases and file systems for indexing and fast searching and looking.

Example: Hash Table Implementation in C Using Chaining

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

#define TABLE_SIZE 10

struct Node {
    int key;
    struct Node* next;
};

struct Node* hashTable[TABLE_SIZE];

// Hash function
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert key
void insert(int key) {
    int index = hashFunction(key);

    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->next = hashTable[index];

    hashTable[index] = newNode;
}

// Search key
int search(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];

    while (temp) {
        if (temp->key == key)
            return 1;
        temp = temp->next;
    }

    return 0;
}

// Delete key
void delete(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];
    struct Node* prev = NULL;

    while (temp) {
        if (temp->key == key) {
            if (prev)
                prev->next = temp->next;
            else
                hashTable[index] = temp->next;

            free(temp);
            return;
        }

        prev = temp;
        temp = temp->next;
    }
}

Typical Applications

• Databases: Fast data retrieval and indexing.
• File Systems: Efficient file lookup and storage management.
• Efficient Searching: Used in sets, maps, and caches for constant-time lookup.

Quick Summary: Advanced Data Structures in C

• Trees and Binary Trees structure data in hierarchy, making searching, sorting, and hierarchical data high performance.  Binary Search Trees (BSTs) provide efficient insertion, deletion, and in-order traversal sorting.
• Heaps are tree-like structured data systems used for maintaining priority.  Max-heaps and min-heaps have efficient access to the root node to act on priority used in priority queues, heapsort, and graph algorithms like Dijkstra’s.
• Graphs represent networks through vertices and edges. They allow modelling of relationships, pathfinding, connectivity analysis, and real-world systems like social networks and routing maps.
• Hashing uses hash tables to obtain near constant insertion, searching, and deletion.  It is widely used in indexing, databases, caching, and file systems.

A pointer is a variable that contains a memory address instead of the actual data value. Pointers are the basis of C programming when dealing with dynamic data; data can be accessed via a pointer rather than its value. For example, in the context of Data Structures in C, Pointers allow access to memory efficiently and manipulate the data without caching large data values.

Example Code:

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

// Define the structure of a node in the linked list
struct Node {
    int data;
    struct Node* next;
};

int main() {
    // Dynamically allocate memory for the first node
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    
    // Assign data to the node
    head->data = 10;
    
    // Set the next pointer to NULL (indicating the end of the list)
    head->next = NULL;

    // Print the data stored in the node
    printf("Data: %d", head->data);
    
    // Free the allocated memory
    free(head);

    return 0;
}

Output

Data: 10

Explanation of Code:

• In the code above, we first define a struct Node containing two members: data and next.
• In the following example, I will show you how to use malloc() to dynamically allocate memory for the head node of the linked list. Using malloc() returns a pointer casting as a Node. The size of the node is determined using  sizeof(struct Node).
• In this example I am independently assigning a value of 10 to the data member of section and setting the next pointer to NULL indicating it is the last section in the linked list.
• Next, we'll print out the contents of the data in the node (head->data), which is a value of 10. 
• At this point, we'll then free the memory we allocated to store the node so we do not create memory leaks as well. 

Time and Space Complexity:

• The time complexity of the program is O(1).
• The space complexity is O(1) because we only created one node in the sample program. If we added additional nodes to the linked list the space complexity would change accordingly. 

Bottom Line

Pointers are the driving forces behind dynamic data structures in C. They let you create dynamic structures, like linked lists, trees, and graphs, without the overhead of duplicating large pieces of data. You must understand pointers. They are what make simple programs into larger, real-world systems, which are usually much more complicated. 

Structures and unions are user-defined data types in C that allow you to group different types of variables together. They allow you to store a collection of data of different types. However, they differ in terms of memory management and usage in some significant ways. 

Structures:

A structure provides you the ability to group the variables of different types into one variable using a single name to access them. This is convenient when you are trying to represent a collection of related data such as characteristics about a person, book or product.

Code Example:

#include <stdio.h>

struct Person {
    char name[50];
    int age;
    float salary;
};

int main() {
    struct Person person1 = {"John Doe", 30, 50000.50};
    
    printf("Name: %s\n", person1.name);
    printf("Age: %d\n", person1.age);
    printf("Salary: %.2f\n", person1.salary);
    
    return 0;
}

Output

Name: John Doe
Age: 30
Salary: 50000.50

Unions:

A union allows multiple data types to be stored in the same memory location. However, only one value can be stored at any given time. The memory used by a union is the size of its largest member, and all members share the same memory space.

Code Example:

#include <stdio.h>

union Data {
    int intValue;
    float floatValue;
    char charValue;
};

int main() {
    union Data data;
    
    data.intValue = 10;
    printf("Integer: %d\n", data.intValue);
    
    data.floatValue = 3.14;
    printf("Float: %.2f\n", data.floatValue);
    
    data.charValue = 'A';
    printf("Character: %c\n", data.charValue);
    
    return 0;
}

Output

Integer: 10
Float: 3.14
Character: A

Bottom Line

The difference between structures and union in C is that structures let you store multiple related values together, while unions let you save memory by storing different values in the same location, but only one at a time. Use structures when you need to keep all fields, and unions when memory efficiency matters. Together, they give C the flexibility to model real-world data effectively.

Data structures in C are fundamental to many areas of computer science and used in combinations of applications to help solve real-world problems efficiently. In C, these structures are of fundamental importance in several areas.

• Databases: In database systems, data structures are used to index and store information in a way that allows for quick retrieval and querying. Structures like B-trees and hash tables help manage large volumes of data efficiently.
• Operating Systems: Operating systems rely heavily on data structures for different tasks, like the order in which processes get executed with process scheduling. Memory management is also a commonly used data structure: managing the free memory blocks in the computer, as well as allocating memory for processes.
• Networking: Data structures are used in networking to maintain routing tables, which indicate the paths data packets must take through the network. Graphs are commonly used to represent the network's topology.
• Artificial Intelligence: Data structures are used in AI applications to represent complex data types like knowledge bases, decision trees, and search spaces. For example, graphs might be used in algorithms that solve for pathfinding, and trees can be used as models of hierarchical relationships or for decision making.

Before you move to more advanced programming, ask yourself one thing: Are you writing code that works… or code that performs? Anyone can build a program that runs, but only a developer who understands data structures can build one that scales, responds quickly, and handles real-world complexity without breaking.

Every structure you learned, arrays, linked lists, stacks, queues, trees, graphs, hashing, pointers, structures, exists because real problems demand real organization. When data grows, when time matters, when memory becomes tight, the right data structure is what saves your program.

So the real question is: do you want code that just solves the problem today, or would you prefer code that just solves the problem today and still executes efficiently tomorrow?

Understanding data structures in C is how you assimilate into that next level.

1. What are data structures in C?

Data structures in C facilitate the efficient management and storage of data. Acquaintance with data structures like arrays, linked lists, stacks, queues, trees, and graphs is crucial, as different data structures are needed for different tasks in programming. 

2. What is the difference between arrays and linked lists?

An array is a data structure that stores elements in a contiguous block of memory of a fixed size. A linked list is comprised of elements stored in nodes linked together by pointers, which allows for the dynamic size of a data structure, while also slower access due to its more complicated nature. 

3. How do pointers work in data structures?

Pointers allow for the storage of memory addresses of variables of values. Data structures such a linked list are advantageous because each group, or node, can refer to un-related data, which allows for efficient data usage while retaining the ability to link the data. 

4. What is a stack and its applications?

A stack implements data on a Last In First Out (LIFO) basis. There are many applications of a stack including managing function calls, evaluating expressions, and backtracking algorithms. 

5. What are the advantages of using a queue?

A queue is a different data structure that operates based on a first-come, first-serve basis. Similar to a stack, there are many potential uses of a queue, including managing the printing of documents, scheduling a process, and handling a data flow. 

6. What is the role of trees in data structures?

A tree shows the hierarchical relationship of an arrangement of data. A tree can be used in applications such as a database, and in an organizational cycle, such as a file system tree. Trees can also illustrate algorithms very effectively in sorting and searching.

7. How do dynamic data structures differ from static ones?

Dynamic data structures can grow or shrink during execution, like linked lists, while static ones, like arrays, have a fixed size set at compile time.