Data Structure

A Data Structure is a specialized format for organizing, processing, retrieving, and storing data in computer memory so that operations can be performed efficiently. An algorithm cannot exist in isolation; it requires a structured mathematical or logical representation of data upon which its operational steps are executed.

The design and selection of an appropriate data structure involve analyzing: (1) the volume and relationship of data items, (2) the frequency of basic operations (searching, insertion, deletion, traversal), and (3) the physical resource constraints (CPU execution time and primary memory consumption).

Data structures are broadly categorized into two fundamental tiers:

• Primitive Data Structures: Basic, atomic data types directly supported by hardware and machine-level instruction sets. In C, these include int, float, char, double, and raw memory memory addresses (pointers). They hold a single atomic value at any instant.
• Non-Primitive Data Structures: Sophisticated structures derived from primitive data types to manage collections of homogeneous or heterogeneous data elements. These are further subdivided into:

Regardless of their structural classification, all data structures support a standard set of core operational primitives:

1. Traversing: Accessing and processing each element of the data structure exactly once (e.g., printing all values or computing their sum).
2. Insertion: Adding a new data element into a designated position within the data structure.
3. Deletion: Removing an existing data element from the data structure.
4. Searching: Locating the position or memory address of an element satisfying a given target key (Linear Search, Binary Search).
5. Sorting: Arranging elements in a predetermined logical sequence (ascending or descending order) using algorithms such as Bubble, Selection, or Insertion sort.
6. Merging: Combining two distinct, typically sorted data collections into a unified composite data structure.

A One-Dimensional Array is a linear data structure comprising a fixed-size, contiguous block of memory holding elements of identical data type (homogeneous). In C, arrays are zero-indexed, meaning an array of size $N$ spans indices $0, 1, 2, \dots, N-1$.

Because elements are stored contiguously, the physical byte address of any arbitrary element $A[i]$ can be calculated mathematically in instantaneous $O(1)$ constant time without inspecting intermediate elements.

Given an array $A$ with Base Address $B$ (the memory address of the first element $A[\text{LB}]$), lower bound index $\text{LB}$ (in C, $\text{LB} = 0$), and element width $W$ in bytes:

For example, if an integer array int marks[50] starts at Base Address $2000$ and each int consumes $4$ bytes ($W = 4, \text{LB} = 0$):

$$\text{Address of } marks[15] = 2000 + (15 - 0) \times 4 = 2000 + 60 = 2060$$

Algorithm 1: Insertion at Position $k$

Inserting an element at index $k$ in an array containing $N$ elements requires shifting all elements from index $N-1$ down to $k$ one position to the right to create an empty vacancy:

// Pre-condition: N < MAX_SIZE, 0 <= k <= N
for (int i = N - 1; i >= k; i--) {
    A[i + 1] = A[i]; // Shift right
}
A[k] = new_value;
N++; // Increment count

Time Complexity: Best Case $O(1)$ (inserting at end), Worst Case $O(n)$ (inserting at index 0, shifting all $N$ elements).

Algorithm 2: Deletion at Position $k$

Deleting the element at index $k$ requires shifting all subsequent elements from index $k+1$ up to $N-1$ one position to the left:

// Pre-condition: N > 0, 0 <= k < N
for (int i = k; i < N - 1; i++) {
    A[i] = A[i + 1]; // Shift left
}
N--; // Decrement count

A 2D array represents data as a rectangular grid of $M$ rows and $N$ columns, declared in C as int A[M][N]. However, physical computer memory (RAM) is strictly linear (a 1D sequence of addressable byte cells). Therefore, compilers must serialize the 2D grid into a 1D sequence using one of two standard ordering conventions:

1. Row-Major Order (RMO): Elements are stored row-by-row sequentially. All elements of Row 0 are stored first, followed by Row 1, Row 2, and so forth. This is the universal standard used by C, C++, Python, and Java.
2. Column-Major Order (CMO): Elements are stored column-by-column sequentially. All elements of Column 0 are stored first, followed by Column 1, Column 2, etc. Used in Fortran and MATLAB.

A Stack is an ordered linear data structure governed by the LIFO (Last-In, First-Out) or FILO (First-In, Last-Out) principle. In a stack, elements can be added or removed only from one designated extremity, termed the TOP of the stack. The opposite end is fixed and called the base.

In an array-based static implementation of maximum capacity MAX, an integer variable TOP tracks the index of the uppermost element:

• Initial Empty State: TOP = -1.
• PUSH Operation: Inserts an element onto the top of the stack.
  Boundary Check: If TOP == MAX - 1, attempting to push triggers a Stack Overflow error condition. Otherwise, increment TOP by 1 and store the value: Stack[++TOP] = val;.
• POP Operation: Removes and returns the topmost element.
  Boundary Check: If TOP == -1, attempting to pop triggers a Stack Underflow error condition. Otherwise, retrieve the element and decrement TOP: val = Stack[TOP--];.
• PEEK / TOP Operation: Returns the value at Stack[TOP] without removing it.
• isEmpty(): Returns true if TOP == -1.
• isFull(): Returns true if TOP == MAX - 1.

#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! Cannot push %d\n", val);
        return;
    }
    stack[++top] = val;
}

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

1. Function Calls and Runtime Call Stack: Whenever a function is invoked, the operating system pushes an Activation Record (containing local variables, arguments, and return instruction address) onto the system call stack. In recursion, successive calls push frames until the base case is reached, after which frames are popped in reverse order.
2. Expression Conversion (Infix, Prefix, Postfix):
   • Infix Notation: Operators placed between operands: A + B * C (relies on operator precedence and parentheses).
   • Prefix Notation (Polish Notation): Operators precede operands: + A * B C (parentheses-free).
   • Postfix Notation (Reverse Polish Notation - RPN): Operators follow operands: A B C * + (ideal for single-pass hardware evaluation).
3. Infix to Postfix Conversion Algorithm: Uses an operator stack to buffer operators based on precedence rules: higher precedence operators are popped before lower precedence operators are pushed; parentheses force immediate sub-expression resolution.
4. Postfix Expression Evaluation: Uses an operand stack. Operands are pushed directly onto the stack. When an operator is encountered, the top two operands are popped, the operation is computed, and the result is pushed back onto the stack.
5. Parentheses Balancing & Syntax Checking: Compilers parse source code by pushing opening delimiters ((, {, [) and popping when closing delimiters appear. A mismatched pop or non-empty stack at EOF indicates a syntax error.
6. Backtracking Algorithms: Browser Back/Forward navigation, text editor Undo/Redo stacks, and graph maze traversal (Depth-First Search).

A Queue is a linear data structure governed by the FIFO (First-In, First-Out) principle. In a standard queue, elements are inserted at one end, designated as the REAR, and deleted from the opposite end, designated as the FRONT.

Common real-world analogs include a queue of ticket buyers or vehicles at a toll booth: the first to arrive is the first to be served.

In a linear array-based queue of size MAX, two pointers FRONT and REAR are initialized to -1:

• ENQUEUE(val): Increments REAR and inserts Queue[REAR] = val. (If FRONT == -1, set FRONT = 0).
• DEQUEUE(): Retrieves Queue[FRONT] and increments FRONT. If FRONT > REAR, reset both to -1.

A Circular Queue overcomes false overflow by treating the array as an unbroken ring where the cell following index MAX - 1 wraps around to index 0 using the modulo arithmetic operator %.

#include <stdio.h>
#define MAX 5

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

int isFull()  { return (rear + 1) % MAX == front; }
int isEmpty() { return front == -1; }

void enqueue(int val) {
    if (isFull()) {
        printf("Circular Queue Overflow!\n");
        return;
    }
    if (isEmpty()) front = 0;
    rear = (rear + 1) % MAX;
    cqueue[rear] = val;
}

int dequeue() {
    if (isEmpty()) {
        printf("Circular Queue Underflow!\n");
        return -1;
    }
    int val = cqueue[front];
    if (front == rear) {
        front = rear = -1; // Reset to empty
    } else {
        front = (front + 1) % MAX;
    }
    return val;
}

• Double-Ended Queue (Deque): Insertion and deletion operations are permitted at both the FRONT and REAR ends. Types: Input-Restricted Deque (insertion at one end, deletion at both) and Output-Restricted Deque (deletion at one end, insertion at both).
• Priority Queue: Each element carries an assigned priority. Deletion does not follow FIFO order; instead, the element with the highest priority is dequeued first. Used in OS interrupt handling and shortest-job-first CPU scheduling.
• Real-World Applications: OS Round-Robin CPU process scheduling, printer spooling buffers (print jobs queued in FIFO order), asynchronous network packet routing buffers, and Breadth-First Search (BFS) graph traversal.

While arrays provide ultra-fast $O(1)$ direct index access, they suffer from significant limitations in practical applications:

• Fixed Static Capacity: Array size is predetermined at compile time. Over-allocating wastes primary memory; under-allocating causes execution failure.
• Contiguous Memory Constraint: Arrays demand a single contiguous block of physical memory. If 10 MB of RAM is scattered across fragmented free blocks, allocating a 10 MB contiguous array fails.
• Costly Insertions and Deletions: Inserting or deleting an element at the beginning or middle requires shifting up to $N$ elements, incurring an expensive $O(n)$ time penalty.

A Singly Linked List is a dynamic linear data structure composed of discrete elements called Nodes allocated independently in Heap memory. Each node consists of two essential parts:

1. Data Field: Holds the actual informational payload (e.g., int, char, or record struct).
2. Next Pointer Field: Holds the memory address of the succeeding node in the chain.

In C, a node is implemented using a self-referential structure:

struct Node {
    int data;               // Informational payload
    struct Node *next;      // Self-referential pointer to next node
};

struct Node *head = NULL;   // Points to the first node (NULL if empty)

1. Traversal: Visiting each node sequentially from head until reaching NULL:

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

2. Insertion at Beginning ($O(1)$ Time):

void insertAtBeginning(struct Node **head_ref, int new_data) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref; // Link new node to former first node
    *head_ref = new_node;       // Move head pointer to new node
}

3. Deletion of First Node ($O(1)$ Time):

void deleteFromBeginning(struct Node **head_ref) {
    if (*head_ref == NULL) return; // List is empty
    struct Node *temp = *head_ref; // Buffer address of first node
    *head_ref = (*head_ref)->next; // Advance head pointer
    free(temp);                    // Deallocate memory to prevent memory leak
}

Searching is the algorithmic procedure of locating the index of a specified target key within a data collection.

• Linear Search (Sequential Search): Sequentially compares the target with every element from index $0$ to $N-1$ until a match occurs or the end of the collection is reached.
  Prerequisite: None. Operates on unsorted and sorted arrays alike.
  Time Complexity: Best Case $O(1)$ (target at index 0); Worst Case $O(n)$ (target at last index or absent); Average Case $O(n)$ ($n/2$ comparisons).
• Binary Search (Divide and Conquer): Repeatedly divides a sorted search interval in half. Compares the target against the middle element mid = low + (high - low) / 2. If target matches A[mid], search terminates. If target is smaller, search continues in left half (high = mid - 1); if larger, in right half (low = mid + 1).
  Prerequisite: The array MUST be sorted.
  Time Complexity: Best Case $O(1)$; Worst/Average Case $O(\log_2 n)$.
  Efficiency Gain: On an array of 1,000,000 sorted elements, Linear Search requires up to $1,000,000$ comparisons, while Binary Search requires at most $\lceil \log_2(1,000,000) \rceil = 20$ comparisons.

Sorting rearranges an unordered collection into ascending or descending sequence.

1. Bubble Sort (Exchange Sort):
   Compares adjacent pairs of elements A[j] and A[j+1] and swaps them if they are out of order. After Pass $k$, the $k$-th largest element bubbles up to its final correct position at the end.
   Optimization: A boolean swapped flag terminates the algorithm early if a complete pass makes zero swaps, yielding an optimal $O(n)$ best-case time on already sorted data.
   Complexity: Best $O(n)$, Worst/Average $O(n^2)$. Space: $O(1)$ auxiliary.
2. Selection Sort:
   Repeatedly finds the minimum element from the unsorted subarray and swaps it with the element at the beginning of the unsorted subarray. Advances the boundary of the sorted subarray one position per pass.
   Swaps: Performs at most $N-1$ total swaps throughout execution ($O(n)$ swaps), making it ideal when write operations to memory are physically expensive.
   Complexity: Best, Worst, and Average are all identical: $O(n^2)$ because finding the minimum always requires nested iteration.
3. Insertion Sort:
   Builds the final sorted array one element at a time. Takes element $A[i]$ and inserts it into its correct sorted position within the already sorted subarray $A[0 \dots i-1]$ by shifting larger elements one position to the right.
   Adaptive Property: Extremely fast on small or nearly sorted datasets ($O(n)$ comparisons when data is nearly sorted).
   Complexity: Best $O(n)$, Worst/Average $O(n^2)$. Space: $O(1)$ auxiliary.