Data Structures in C

A data structure is a way of organizing and storing data in memory so it can be accessed and modified efficiently. C allows building powerful data structures using pointers and dynamic memory. This topic covers three fundamental data structures: Linked Lists, Stacks, and Queues.

Linked List

A linked list is a linear data structure where each element (called a node) stores a value and a pointer to the next node. Unlike arrays, nodes do not have to be stored in adjacent memory locations — they are connected through pointers.

Node Structure

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

Create, Insert, and Display a Singly Linked List

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

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

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

void insertAtEnd(struct Node **head, int value) {
    struct Node *newNode = createNode(value);
    if (*head == NULL) { *head = newNode; return; }
    struct Node *cur = *head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = newNode;
}

void insertAtBegin(struct Node **head, int value) {
    struct Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

void deleteNode(struct Node **head, int value) {
    if (*head == NULL) return;
    if ((*head)->data == value) {
        struct Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    struct Node *cur = *head;
    while (cur->next && cur->next->data != value)
        cur = cur->next;
    if (cur->next) {
        struct Node *temp = cur->next;
        cur->next = temp->next;
        free(temp);
    }
}

void display(struct Node *head) {
    struct Node *cur = head;
    while (cur != NULL) { printf("%d -> ", cur->data); cur = cur->next; }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL;

    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtBegin(&head, 5);

    printf("List   : "); display(head);

    deleteNode(&head, 20);
    printf("After deleting 20: "); display(head);

    return 0;
}

Output

List   : 5 -> 10 -> 20 -> 30 -> NULL
After deleting 20: 5 -> 10 -> 30 -> NULL

Array vs Linked List

Stack

A stack follows the LIFO (Last In, First Out) principle. The last item pushed is the first to be popped. Think of a stack of books — the last book placed on top is the first one removed.

Common Stack Uses

• Undo/Redo operations in editors
• Function call management in programs
• Expression evaluation (e.g., brackets matching)
• Back/Forward navigation in browsers

Stack Using Array

#include <stdio.h>
#define MAX 5

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

int isFull()  { return top == MAX - 1; }
int isEmpty() { return top == -1; }

void push(int val) {
    if (isFull()) { printf("Stack Overflow!\n"); return; }
    stack[++top] = val;
    printf("Pushed: %d\n", val);
}

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

void peek() {
    if (isEmpty()) printf("Stack is empty.\n");
    else printf("Top: %d\n", stack[top]);
}

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

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

Output

Pushed: 10
Pushed: 20
Pushed: 30
Top: 30
Stack (top to bottom): 30 20 10 
Popped: 30
Popped: 20
Top: 10

Queue

A queue follows the FIFO (First In, First Out) principle. The first item added is the first one removed. Think of a line at a bank — the person who arrives first is served first.

Common Queue Uses

• Print spoolers (print jobs processed in order)
• CPU task scheduling
• Breadth-first search in graphs
• Keyboard buffer for typed input

Queue Using Array

#include <stdio.h>
#define MAX 5

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

int isFull()  { return rear == MAX - 1; }
int isEmpty() { return front == -1 || front > rear; }

void enqueue(int val) {
    if (isFull()) { printf("Queue is full!\n"); return; }
    if (front == -1) front = 0;
    queue[++rear] = val;
    printf("Enqueued: %d\n", val);
}

int dequeue() {
    if (isEmpty()) { printf("Queue is empty!\n"); return -1; }
    return queue[front++];
}

void display() {
    if (isEmpty()) { printf("Queue is empty.\n"); return; }
    printf("Queue (front to rear): ");
    for (int i = front; i <= rear; i++) printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    enqueue(100); enqueue(200); enqueue(300);
    display();
    printf("Dequeued: %d\n", dequeue());
    display();
    enqueue(400);
    display();
    return 0;
}

Output

Enqueued: 100
Enqueued: 200
Enqueued: 300
Queue (front to rear): 100 200 300 
Dequeued: 100
Queue (front to rear): 200 300 
Enqueued: 400
Queue (front to rear): 200 300 400 

Stack vs Queue

Summary

Linked lists provide dynamic memory-based linear storage where each node is linked by a pointer. Stacks (LIFO) and queues (FIFO) are abstract data types that can be implemented using arrays or linked lists. These three structures are the building blocks for more complex algorithms and systems like compilers, operating systems, and databases.