Data Structures in C – A Complete Tutorial

Introduction to Data Structures

Data structures are ways to organize and store data efficiently. They are essential for:
✔ Optimizing memory usage
✔ Fast data access & manipulation
✔ Solving complex problems (e.g., searching, sorting, graphs)

In this tutorial, we’ll implement key data structures in C.

1. Arrays

Definition

A fixed-size collection of elements of the same type.

Implementation

#include <stdio.h>

int main() {
    int arr[5] = {10, 20, 30, 40, 50};  
    
    // Accessing elements
    printf("Element at index 2: %d\n", arr[2]);  // Output: 30
    
    // Modifying elements
    arr[2] = 35;
    printf("Updated element: %d\n", arr[2]);  // Output: 35
    
    return 0;
}

Pros & Cons

✅ Fast access (O(1) time)
❌ Fixed size (cannot grow dynamically)

2. Linked Lists

Definition

A dynamic data structure where elements (nodes) are connected via pointers.

Types

Singly Linked List (one-way traversal)
Doubly Linked List (two-way traversal)
Circular Linked List (last node points to head)

Implementation (Singly Linked List)

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

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // Creating nodes
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    
    // Printing the list
    printList(head);  // Output: 10 -> 20 -> 30 -> NULL
    
    return 0;
}

Pros & Cons

✅ Dynamic size (no memory wastage)
❌ Slower access (O(n) time for traversal)

3. Stacks (LIFO)

Definition

A Last-In-First-Out (LIFO) structure where insertion/deletion happens at one end (top).

Operations

push() – Insert an element
pop() – Remove the top element
peek() – Get the top element

Implementation (Using Arrays)

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;  // Empty stack

void push(int item) {
    if (top == MAX - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    stack[++top] = item;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return stack[top--];
}

void display() {
    for (int i = top; i >= 0; i--) {
        printf("%d\n", stack[i]);
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    
    printf("Stack:\n");
    display();
    
    printf("Popped: %d\n", pop());  // Output: 30
    
    return 0;
}

Pros & Cons

✅ Fast operations (O(1))
❌ Limited size (if using arrays)

4. Queues (FIFO)

Definition

A First-In-First-Out (FIFO) structure where insertion happens at rear and deletion at front.

Operations

enqueue() – Insert at rear
dequeue() – Remove from front

Implementation (Using Arrays)

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int item) {
    if (rear == MAX - 1) {
        printf("Queue Full!\n");
        return;
    }
    if (front == -1) front = 0;
    queue[++rear] = item;
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Empty!\n");
        return -1;
    }
    return queue[front++];
}

void display() {
    for (int i = front; i <= rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    
    printf("Queue: ");
    display();  // Output: 10 20 30
    
    printf("Dequeued: %d\n", dequeue());  // Output: 10
    
    return 0;
}

Pros & Cons

✅ Orderly processing
❌ Inefficient for large data (if using arrays)

5. Trees (Binary Search Tree - BST)

Definition

A hierarchical structure where each node has at most two children (left & right).

Operations

insert() – Add a node
search() – Find a node
traverse() – Inorder, Preorder, Postorder

Implementation

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

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

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

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

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

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    
    printf("Inorder Traversal: ");
    inorder(root);  // Output: 30 50 70
    
    return 0;
}

Pros & Cons

✅ Fast search (O(log n) in balanced BST)
❌ Can degrade to O(n) if unbalanced

6. Graphs (Adjacency List)

Definition

A collection of nodes (vertices) connected by edges.

Implementation

#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 = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = (struct Node**)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 (for undirected graph)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        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, 3);
    
    printGraph(graph);
    return 0;
}

Pros & Cons

✅ Efficient for sparse graphs
❌ More complex than adjacency matrix

Conclusion

Data Structure	Best Use Case	Time Complexity (Avg)
Array	Fixed-size collections	O(1) access
Linked List	Dynamic data	O(n) search
Stack	Undo operations, recursion	O(1) push/pop
Queue	Scheduling, BFS	O(1) enqueue/dequeue
BST	Searching, sorting	O(log n)
Graph	Networks, maps	O(V + E)

Menu

Wednesday, April 30, 2025