Data Structures

NPTEL / GATE CS / UGC NET Foundation Module Exam Weightage: 1–2 Questions directly testing ADT vs concrete data structures, classification taxonomy (Linear vs Non-Linear, Static vs Dynamic, Homogeneous vs Heterogeneous), and the asymptotic bounds of fundamental operations.

1. Prerequisites & What You Should Know#

Before studying data structures formally, you should be comfortable with:

• Variables & Data Types: Understanding basic primitives like int, float, char, and how compilers store them.
• Memory Addresses & Pointers: Conceptualizing that RAM is a sequential collection of numbered byte cells.
• Functions & Interfaces: Knowing the difference between calling a function and how its inner logic executes.
• Mathematical Sets & Relations: Basic set notation ($S = \{x_1, x_2, \dots, x_n\}$) and ordering relations.

2. What is a Data Structure? (Conceptual Foundation)#

2.1 Data vs. Information vs. Data Structure#

To understand data structures, we must first distinguish three fundamental layers:

1. Data: Raw, unorganized facts or values without context (e.g., 42, "Alice", 3.14). On its own, raw data carries no semantic meaning.
2. Information: Data processed, contextualized, and organized so that it becomes meaningful (e.g., "Alice scored 42 points in exam round 3").
3. Data Structure: A specialized mathematical and algorithmic format for organizing, storing, managing, and relating data so that operations (such as retrieval, insertion, modification, and deletion) can be performed efficiently.

+————————————+       Organization & Relationships       +——————————————————————+
|  Raw Data  |  —————————————————————————————————————>  |    Data Structure    |
| (42, "Bob")|       (Arrays, Pointers, Hierarchy)      | (Indexed, Linked, etc)|
+————————————+                                          +——————————————————————+
                                                                   │
                                                                   │ Optimized Algorithms
                                                                   ▼
                                                        +——————————————————————+
                                                        | Useful Information   |
                                                        | Fast O(1) / O(log n) |
                                                        +——————————————————————+

2.2 The Real-World Warehouse Analogy#

Imagine a massive shipping warehouse storing 500,000 packages:

• Unstructured Pile: Dumping all 500,000 packages in an unsorted pile on the warehouse floor. Finding any single item requires inspecting packages one by one ($O(n)$ time).
• Indexed Grid (Array): Numbered aisles and shelves where each box has an exact fixed coordinate. You reach box #314 instantly ($O(1)$ time).
• Dispatch Queue (FIFO): Packages arranged on a conveyor belt so that the earliest arrived package ships first ($O(1)$ enqueue/dequeue).
• Hierarchical Shelves (Tree): Sorting items by Country $\to$ State $\to$ City $\to$ Postal Code. Narrowing down the location takes logarithmic steps ($O(\log n)$ time).

Axiom of Computer Science: Algorithm + Data Structure = Program (Niklaus Wirth, 1976) An algorithm cannot exist in isolation; it operates exclusively upon data structured in memory. Choosing the wrong data structure degrades the most brilliant algorithm.

3. Formal Mathematical Definition of Data Structures#

In formal computer science and university curricula (NPTEL, GATE, UGC NET), a data structure is not merely code; it is defined mathematically.

3.1 The 4-Tuple Model: $D = (D, F, A, P)$#

Formally, a data structure $D$ is characterized as a 4-tuple:

$D = (D_0, \mathcal{F}, \mathcal{A}, \mathcal{P})$

Where:

1. $D_0$ (Domain): The set of data objects or elements being structured (e.g., integers $\mathbb{Z}$, strings $\Sigma^*$).
2. $\mathcal{F}$ (Functions / Operations): The set of valid mappings and functions permitted on the domain (e.g., $\text{Insert}: D_0 \times \text{Elem} \to D_0$, $\text{Delete}: D_0 \to D_0$).
3. $\mathcal{A}$ (Axioms / Semantic Rules): The formal mathematical equations and identities that must always hold true (e.g., in a Stack: $\text{Pop}(\text{Push}(S, x)) = S$).
4. $\mathcal{P}$ (Preconditions): The prerequisite constraints for operations to be valid (e.g., $\text{Pop}(S)$ requires $\text{IsEmpty}(S) = \text{False}$; violation produces Stack Underflow).

3.2 The Relational Model: $(S, R)$#

Alternative mathematical formulation: A data structure is an ordered pair:

$\mathcal{DS} = (S, R)$

Where:

• $S$ is a finite set of data items: $S = \{d_1, d_2, \dots, d_n\}$.
• $R$ is a set of relationships over $S$: $R = \{r_1, r_2, \dots, r_m\}$, where each $r_i \subseteq S \times S$.
  • In a Linear Structure: $R$ is a strict total order relation where every element (except first and last) has a unique immediate predecessor and unique immediate successor.
  • In a Hierarchical Structure (Tree): $R$ is an asymmetric acyclic parent-child relation with a unique root having no predecessor.
  • In a Graph: $R$ is an arbitrary binary adjacency relation with no structural constraints.

4. Comprehensive Classification of Data Structures#

Data structures are categorized across several orthogonal taxonomic axes:

                                  Data Structures
                                 /               \
                      Primitive                    Non-Primitive
                     /    |    \                  /             \
                  int   float   char           Linear          Non-Linear
                  bool  pointer               /      \          /         \
                                          Static    Dynamic   Trees     Graphs
                                            |       /  |  \      |         |
                                          Array   LL Stack Queue BST, AVL  Directed,
                                                                 Heap, Trie Undirected

4.1 Classification Dimension 1: Primitive vs. Non-Primitive#

4.2 Classification Dimension 2: Linear vs. Non-Linear#

Linear:      [ Node 1 ] <——> [ Node 2 ] <——> [ Node 3 ] <——> [ Node 4 ]
             (Single predecessor, single successor — sequential traversal)

Non-Linear:               [ Root / Node A ]
                           /             \
                   [ Child B ]         [ Child C ]
                    /       \                 \
               [ Leaf D ]  [ Leaf E ]       [ Leaf F ]
             (Hierarchical parent-child or arbitrary graph network)

4.3 Classification Dimension 3: Static vs. Dynamic#

4.4 Classification Dimension 4: Homogeneous vs. Heterogeneous#

• Homogeneous Data Structures: All stored elements must be of the identical data type (e.g., standard C arrays where every element occupies exactly sizeof(T) bytes).
• Heterogeneous Data Structures: Elements can be of varying, dissimilar data types (e.g., C struct, Python tuples/lists, JSON objects, database tuples).

4.5 Classification Dimension 5: Persistent vs. Ephemeral#

• Ephemeral Data Structures: Any modification (insert, delete) destroys the prior version; only the latest mutated state is preserved (e.g., standard arrays and pointers mutated in-place).
• Persistent Data Structures: Preserves historic versions when updated:
  • Partially Persistent: All versions can be read, but only the newest version can be modified.
  • Fully Persistent: Any version can be both inspected and modified, creating a version tree (used in Git, functional programming languages, and undo history).

5. Abstract Data Types (ADT) vs. Concrete Data Structures#

A paramount question in GATE CS and university oral exams is: "What is the precise difference between an ADT and a Data Structure?"

5.1 The Interface Contract: WHAT vs. HOW#

+—————————————————————————————————————————————————————————+
|               ABSTRACT DATA TYPE (ADT)                  |
|                 Logical Specification                   |
|                                                         |
|   "WHAT operations can be performed?"                   |
|   - Push(x): Add element to top                         |
|   - Pop(): Remove element from top                      |
|   - Peek(): Inspect top element                         |
|   - IsEmpty(): Check if empty                           |
+—————————————————————————————————————————————————————————+
                            │
               Implemented via Concrete DS
                            ▼
+—————————————————————————————+———————————————————————————+
| Array-Based Implementation  | Linked List Implementation|
|                             |                           |
| - int data[MAX];            | - struct Node {           |
| - int top = -1;             |     int val;              |
|                             |     Node* next;           |
| Fast index lookups          |   };                      |
| Fixed size bound            | Truly dynamic heap growth |
+—————————————————————————————+———————————————————————————+

1. Abstract Data Type (ADT):

   • A mathematical model specifying WHAT operations can be performed and WHAT constraints apply, without defining how elements are placed in physical memory.
   • It defines the public interface, behaviors, and semantic contracts.
   • The user of an ADT does not know (and does not care) whether an array, a linked list, or memory mapped files are used internally.

2. Concrete Data Structure:

   • The physical, concrete implementation in programming code detailing HOW data is represented in RAM and HOW algorithms manipulate those bits.

5.2 Classic ADT vs. Concrete DS Mapping#

6. Multi-Language Implementation of an ADT#

To solidify the ADT concept, below is a complete implementation of a Stack ADT showing strict separation of interface and implementation across C, C++, and Python.

/**
 * In ANSI C, an ADT is implemented via:
 * 1. An OPAQUE POINTER in the header file (hiding struct internals).
 * 2. Strict function signatures defining the ADT operations.
 * 3. Dynamic allocation ensuring true memory encapsulation.
 */

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

// --- ADT Interface (Header Declaration) ---
typedef struct StackADT* Stack;

Stack stack_create(size_t capacity);
void  stack_destroy(Stack s);
bool  stack_push(Stack s, int value);
bool  stack_pop(Stack s, int* popped_val);
bool  stack_peek(const Stack s, int* peek_val);
bool  stack_is_empty(const Stack s);
bool  stack_is_full(const Stack s);

// --- Concrete Implementation (Source File) ---
struct StackADT {
    int* data;
    size_t capacity;
    int top; // Index of top element, -1 when empty
};

Stack stack_create(size_t capacity) {
    if (capacity == 0) return NULL;
    Stack s = (Stack)malloc(sizeof(struct StackADT));
    if (!s) return NULL;
    s->data = (int*)malloc(capacity * sizeof(int));
    if (!s->data) {
        free(s);
        return NULL;
    }
    s->capacity = capacity;
    s->top = -1;
    return s;
}

void stack_destroy(Stack s) {
    if (s) {
        free(s->data);
        free(s);
    }
}

bool stack_is_empty(const Stack s) {
    return s == NULL || s->top == -1;
}

bool stack_is_full(const Stack s) {
    return s != NULL && (size_t)(s->top + 1) == s->capacity;
}

bool stack_push(Stack s, int value) {
    if (stack_is_full(s)) return false; // Overflow guard
    s->data[++(s->top)] = value;
    return true;
}

bool stack_pop(Stack s, int* popped_val) {
    if (stack_is_empty(s)) return false; // Underflow guard
    *popped_val = s->data[(s->top)--];
    return true;
}

bool stack_peek(const Stack s, int* peek_val) {
    if (stack_is_empty(s)) return false;
    *peek_val = s->data[s->top];
    return true;
}

7. Fundamental Operations on Data Structures#

Regardless of structure type, data structures support six foundational primitive operations:

+—————————————————————————————————————————————————————————+
|               Core Operations on Data                   |
+—————————————————+———————————————————————————————————————+
| 1. Traversing   | Visit every node/element exactly once |
| 2. Searching    | Locate element matching target key    |
| 3. Insertion    | Add new item at target position       |
| 4. Deletion     | Remove specified element & rewire     |
| 5. Sorting      | Arrange items in ascending/descending |
| 6. Merging      | Combine two collections into single DS|
+—————————————————+———————————————————————————————————————+

1. Traversing: Systematically processing or inspecting each element in the data structure exactly once without omissions or infinite looping.
2. Searching: Locating the memory address or logical index of a data element satisfying a search predicate (Linear Search $O(n)$, Binary Search $O(\log n)$, Hash Lookup $O(1)$).
3. Insertion: Adding a new element into the collection. In arrays this requires shifting items right ($O(n)$); in linked lists it requires pointer rewiring ($O(1)$ at known pointer).
4. Deletion: Locating and removing an existing item, reclaiming memory, and maintaining structural invariants.
5. Sorting: Arranging elements in a defined logical ordering (Quicksort, Mergesort, Heapsort).
6. Merging: Combining two distinct collections into a single unified structure (e.g., merging two sorted linked lists in $O(n_1 + n_2)$).

8. Data Structure Selection Decision Framework#

How do real-world system architects and competitive programmers select the ideal data structure? Follow this mental decision tree:

                            What is your primary operational need?
                                              │
         ┌──────────────────┬─────────────────┼──────────────────┬──────────────────┐
         ▼                  ▼                 ▼                  ▼                  ▼
    Access by Index    Frequent Insert/    LIFO Ordering      FIFO Ordering      Key-Value Lookup
    at O(1) Speed      Delete at Ends      (Undo/Recursion)   (Buffering/Jobs)   at O(1) Average
         │                  │                 │                  │                  │
         ▼                  ▼                 ▼                  ▼                  ▼
    Array / Vector     Linked List          Stack              Queue           Hash Table / Map

Comparative Performance Matrix#

9. GATE & UGC NET Exam Traps & Conceptual Insights#