• Data Structure is a way to organize and store data so operations like insert, delete, search, and update become efficient.
• In C, data structures are commonly implemented using structures and pointers.
• Common C-based data structures: Linked List, Stack, Queue, Circular Queue, and Trees.

1) Linked List (Singly) - Concept

• A linked list is a linear data structure made of nodes.
• Each node contains:
  • data
  • next pointer (address of next node)
• Advantages: dynamic size, easy insertion/deletion.
• Disadvantages: no direct indexing, extra memory for pointers.

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

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

int main() {
    // Create 2 nodes (basic demo)
    struct Node *n1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node *n2 = (struct Node*)malloc(sizeof(struct Node));

    n1->data = 10;
    n1->next = n2;

    n2->data = 20;
    n2->next = NULL;

    // Traverse
    struct Node *temp = n1;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");

    free(n2);
    free(n1);
    return 0;
}

2) Stack (LIFO) - Concept

• Stack follows LIFO (Last In First Out).
• Main operations:
  • push (insert)
  • pop (remove)
  • peek (top element)
  • isEmpty, isFull (array stack)
• Applications: function call stack, undo feature, expression evaluation.

// Array based stack (basic)
#include <stdio.h>
#define SIZE 5

int main() {
    int stack[SIZE];
    int top = -1;

    // push 10
    if (top < SIZE - 1) stack[++top] = 10;
    // push 20
    if (top < SIZE - 1) stack[++top] = 20;

    // pop
    if (top >= 0) printf("Popped: %d\n", stack[top--]);

    // peek
    if (top >= 0) printf("Top: %d\n", stack[top]);

    return 0;
}

3) Queue (FIFO) - Concept

• Queue follows FIFO (First In First Out).
• Main operations:
  • enqueue (insert at rear)
  • dequeue (remove from front)
  • front/rear
• Applications: scheduling, printers, buffering.

// Simple queue using array (basic)
#include <stdio.h>
#define SIZE 5

int main() {
    int q[SIZE];
    int front = 0, rear = -1;

    // enqueue 10, 20
    if (rear < SIZE - 1) q[++rear] = 10;
    if (rear < SIZE - 1) q[++rear] = 20;

    // dequeue
    if (front <= rear) printf("Dequeued: %d\n", q[front++]);

    // front element
    if (front <= rear) printf("Front: %d\n", q[front]);

    return 0;
}

4) Circular Queue - Concept

• Circular queue fixes unused space problem of normal queue.
• When rear reaches end, it goes back to start using modulus.
• Conditions:
  • Full: (rear + 1) % size == front
  • Empty: front == -1

// Circular queue formulas (concept)
rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

5) Basic Tree Concepts

• Tree is a hierarchical non-linear data structure.
• Terms:
  • Root: top node
  • Parent/Child: relationship between nodes
  • Leaf: node with no children
  • Height, Depth
• Binary Tree: each node has at most 2 children (left, right).
• Binary Search Tree (BST): left < root < right (sorted property).

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

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

struct TNode* newNode(int x) {
    struct TNode *n = (struct TNode*)malloc(sizeof(struct TNode));
    n->data = x;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int main() {
    // Basic binary tree
    struct TNode *root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);

    printf("Root: %d\n", root->data);

    // free (simple demo)
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

6) Quick Notes

• Linked List: dynamic nodes connected by pointers.
• Stack: LIFO (push/pop).
• Queue: FIFO (enqueue/dequeue).
• Circular Queue: uses modulo to reuse array space.
• Tree: hierarchical structure (root, child, leaf).