Data Structures Explained:
Arrays to Trees — Full Guide 2026

1. What Are Data Structures?

A Data Structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Think of it like this — data is the raw material (bricks), and a data structure is the architectural blueprint that decides how those bricks are arranged to build something useful.

Every program you write uses at least one data structure. When you store a list of contacts on your phone, that’s an array. When your browser lets you press Back to go to the previous page, that’s a stack. When you stand in a ticket queue at a railway station, that’s a queue in real life — and it works exactly the same way in software.

Linear vs Non-Linear Data Structures

2. Arrays — The Foundation of Data Structures

An array is a collection of elements of the same data type stored in contiguous memory locations. Each element is identified by an index (position), starting from 0. If the base address is 1000 and each integer takes 4 bytes, then arr[3] is at address 1000 + (3 × 4) = 1012.

Arrays are the simplest and most widely used data structure. Almost every other data structure is either built on top of arrays or compared against them.

  Index:  [  0  ] [  1  ] [  2  ] [  3  ] [  4  ]
  Value:  [ 10  ] [ 25  ] [ 37  ] [ 48  ] [ 56  ]
          ↑
      Base Address (e.g. 1000)

  arr[2] → Address = 1000 + (2 × 4) = 1008  →  value = 37
        

Array Operations with Code (C)

// Declare and initialize an array
int arr[5] = {10, 25, 37, 48, 56};

// Access — O(1): direct index calculation
printf("%d\n", arr[2]);   // Output: 37

// Linear Search — O(n)
for (int i = 0; i < 5; i++) {
    if (arr[i] == 48) {
        printf("Found at index %d\n", i);
        break;
    }
}

// Insertion at end — O(1) if space available
// Insertion in middle — O(n) due to shifting
for (int i = 4; i >= 2; i--) {
    arr[i + 1] = arr[i];   // shift right
}
arr[2] = 99;              // insert 99 at index 2

Time Complexity: Arrays

Real-World Applications of Arrays

3. Linked Lists — Dynamic Memory Allocation

A Linked List is a linear data structure where elements (called nodes) are stored at non-contiguous memory locations. Each node contains two parts: the data and a pointer (link) to the next node. Unlike arrays, linked lists do not require a predefined size — memory is allocated dynamically as new nodes are added.

  Singly Linked List:

  [HEAD]
    |
  [ 10 | →] ──→ [ 25 | →] ──→ [ 37 | →] ──→ [ 48 | NULL]
   Node 1          Node 2        Node 3        Node 4 (Tail)

  Doubly Linked List:

  NULL ←─ [← | 10 | →] ←──→ [← | 25 | →] ←──→ [← | 37 | → ] ──→ NULL
        

Node Structure & Basic Operations (C)

// Define a Node
struct Node {
    int data;
    struct Node* next;
};

// Insert at beginning — O(1)
struct Node* insertAtHead(struct Node* head, int val) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->next = head;   // new node points to old head
    return newNode;           // new node becomes new head
}

// Search — O(n) — must traverse from head
int search(struct Node* head, int val) {
    int pos = 0;
    while (head != NULL) {
        if (head->data == val) return pos;
        head = head->next;
        pos++;
    }
    return -1;  // not found
}

Types of Linked Lists

Array vs Linked List — Quick Comparison

4. Stacks — Last In, First Out (LIFO)

A Stack is a linear data structure that follows the LIFO principle — the last element inserted is the first one to be removed. Imagine a stack of plates: you always place a new plate on top, and you always remove the top plate first. You cannot access any plate below without removing the ones above it.

Stacks are the backbone of how computers execute function calls, evaluate expressions, and manage undo operations.

  PUSH 10, PUSH 20, PUSH 30:        POP:

  |    |         |    |             |    |
  | 30 | ← TOP   | 30 | removed     | 20 | ← new TOP
  | 20 |         | 20 |             | 10 |
  | 10 |         | 10 |             |    |
  |____|         |____|             |____|

  push(x) → add to TOP             pop() → remove from TOP
  peek()  → see TOP without removing
        

Stack Implementation (Array-based, C)

int stack[100];
int top = -1;  // -1 means empty stack

// Push — O(1)
void push(int x) {
    if (top == 99) { printf("Stack Overflow!\n"); return; }
    stack[++top] = x;
}

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

// Peek — O(1)
int peek() {
    return (top == -1) ? -1 : stack[top];
}

Real-World Applications of Stacks

5. Queues — First In, First Out (FIFO)

A Queue is a linear data structure that follows the FIFO principle — the first element inserted is the first one to be removed. Think of a line at a movie theatre: the person who arrives first gets served first. New people join at the rear (back), and people leave from the front.

  Enqueue (add to REAR):          Dequeue (remove from FRONT):

  FRONT                   REAR    FRONT                   REAR
    ↓                       ↓       ↓                       ↓
  [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]  [ 20 ][ 30 ][ 40 ][ 50 ]
  ← removes here      adds here →      10 is removed →
        

Types of Queues

from collections import deque

# Python's deque is the optimal Queue implementation
q = deque()

# Enqueue — O(1)
q.append(10)
q.append(20)
q.append(30)

# Dequeue — O(1)
removed = q.popleft()   # removes 10
print(removed)            # Output: 10

# Peek — O(1)
print(q[0])               # Output: 20 (front element)

Real-World Applications of Queues

6. Trees — Hierarchical Data Structures

A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (arrays, linked lists), trees represent relationships with a parent-child hierarchy. A tree with n nodes has exactly n–1 edges.

The root is the topmost node. Nodes with no children are called leaf nodes. The height of a tree is the length of the longest path from root to a leaf.

        Tree Terminology:

              [A]          ← Root (Level 0)
             /   \
           [B]   [C]       ← Level 1 (children of A)
          / \      \
        [D] [E]    [F]     ← Level 2 (D,E children of B; F child of C)
                   / \
                 [G] [H]   ← Leaf nodes (no children)

  • A is parent of B, C       • D, E, G, H are leaf nodes
  • Height of tree = 3        • Depth of F = 2
  • B is an internal node     • Degree of B = 2 (has 2 children)
        

Binary Tree — The Most Important Type

A Binary Tree is a tree where every node has at most 2 children — commonly called the left child and right child. Binary trees are foundational because most tree-based data structures (BST, Heap, AVL) are binary trees with additional constraints.

Tree Traversals — The Big Three

Traversal means visiting every node exactly once. The three main traversal methods differ in when you visit the root relative to the left and right subtrees:

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

// Inorder: Left → Root → Right → gives sorted order in BST
void inorder(struct Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// Preorder: Root → Left → Right
void preorder(struct Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

7. Binary Search Trees (BST)

A Binary Search Tree is a binary tree with one crucial additional property: for every node, all values in its left subtree are smaller, and all values in its right subtree are greater. This property enables incredibly efficient search, insert, and delete operations — all in O(log n) on average.

  BST Property: Left < Root < Right

              [50]
             /    \
          [30]    [70]
          /  \    /  \
        [20][40][60] [80]

  Search 40:  50 → (40<50, go left) → 30 → (40>30, go right) → 40 ✓
  Path length = 3 steps = O(log n) for balanced BST

  ⚠ Worst Case: Inserting sorted data [10,20,30,40] → becomes a linked list
              [10]
               \
              [20]
                \
               [30]   ← Skewed BST — search degrades to O(n)
                 \
                [40]
        

BST Operations — Time Complexity

8. Big-O Complexity Cheatsheet — All Data Structures

This is the table you need to memorize before any placement interview or GATE exam. Know the average and worst-case complexities for every major operation on each data structure.

9. Interview & GATE Tips — What Toppers Know

For Placement Interviews (TCS, Infosys, Amazon, Google)

For GATE CSE — Data Structures Strategy

10. Frequently Asked Questions (FAQ)