DSA Complete Guide - Data Structures & Algorithms

1

What is DSA?

Data Structures

Methods of organizing and storing data in a computer so that it can be accessed and modified efficiently.

Define relationships between data items
Determine operations that can be performed
Impact time and space efficiency

Algorithms

Step-by-step procedures or formulas for solving problems and performing computations.

Finite sequence of well-defined instructions
Take inputs and produce outputs
Must terminate and be effective

Key Insight: DSA is the foundation of computer science. While data structures are about organizing data, algorithms are about processing that data efficiently.

2

Why DSA is Important

Efficiency

Enables writing optimized code that runs faster and uses less memory.

Problem Solving

Develops logical thinking and systematic approach to solving complex problems.

Career Growth

Essential for technical interviews at top tech companies like Google, Amazon, Microsoft.

Real-World Applications

Search Engines

Indexing & retrieval

GPS Navigation

Shortest path algorithms

Databases

B-trees, indexing

Social Networks

Graph algorithms

3

Core Fundamentals

Time & Space Complexity

Big O Notation

Mathematical notation describing how runtime or space requirements grow as input size increases.

Notation	Name	Example
`O(1)`	Constant Time	Array access
`O(log n)`	Logarithmic	Binary search
`O(n)`	Linear	Linear search
`O(n log n)`	Linearithmic	Merge sort
`O(n²)`	Quadratic	Bubble sort
`O(2ⁿ)`	Exponential	Fibonacci naive

Space Complexity

Amount of memory space required by an algorithm relative to input size.

// Example: O(1) space complexity
function sumArray(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// Example: O(n) space complexity
function copyArray(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i]);
  }
  return newArr;
}

Recursion

What is Recursion?

A function that calls itself directly or indirectly to solve a problem by breaking it into smaller subproblems.

Recursion Requirements:

Base Case (stopping condition)
Recursive Case (calls itself)
Progress toward base case

// Factorial using recursion
function factorial(n) {
  // Base case
  if (n <= 1) {
    return 1;
  }
  // Recursive case
  return n * factorial(n - 1);
}

// Fibonacci sequence
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Bit Manipulation

Common Operations

Operator	Name	Description
`&`	AND	Sets each bit to 1 if both bits are 1
`\|`	OR	Sets each bit to 1 if either bit is 1
`^`	XOR	Sets each bit to 1 if only one bit is 1
`~`	NOT	Inverts all bits
`<<`	Left Shift	Shifts bits left, fills with 0
`>>`	Right Shift	Shifts bits right

Common Applications

Checking if number is even/odd: (n & 1) == 0
Multiplying/dividing by powers of 2: n << 1 (×2), n >> 1 (÷2)
Swapping numbers without temp: a ^= b; b ^= a; a ^= b;
Checking if power of 2: (n & (n-1)) == 0
Counting set bits (popcount)

// Check if number is power of two
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// Count number of 1 bits
function countSetBits(n) {
  let count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

4

Data Structures

Linear Data Structures

Array

Collection of elements identified by index or key.

O(1) Access

Pros: Fast access, memory efficient
Cons: Fixed size, expensive insert/delete
Use: Storing sequential data

Linked List

Nodes containing data and reference to next node.

O(n) Access O(1) Insert/Delete

Types: Singly, Doubly, Circular
Pros: Dynamic size, easy insert/delete
Use: Browser history, undo functionality

Stack

LIFO (Last In, First Out) structure.

O(1) Push/Pop

Operations: Push, Pop, Peek
Pros: Simple, efficient
Use: Function calls, expression evaluation

Queue

FIFO (First In, First Out) structure.

O(1) Enqueue/Dequeue

Types: Simple, Circular, Priority, Deque
Pros: Fair ordering
Use: Printers, task scheduling

String

Sequence of characters.

O(1) Access O(n) Search

Important Algorithms: KMP, Rabin-Karp
Use: Text processing, pattern matching

Hash Table

Key-value storage using hash function.

O(1)* Average Search

Collision Handling: Chaining, Open Addressing
Pros: Fast average operations
Use: Dictionaries, caches, databases

Non-Linear Data Structures

Tree

Hierarchical structure with root and child nodes.

Tree Types:

• Binary Tree
• Binary Search Tree
• AVL Tree
• Red-Black Tree
• B-Tree

Complexities:

O(log n) BST Search

O(n) Worst Search

Use: File systems, DOM, database indexing

Heap

Complete binary tree with heap property.

O(log n) Insert/Delete O(1) Find Min/Max

Types: Min-Heap, Max-Heap
Use: Priority queues, heap sort

Graph

Collection of vertices and edges connecting them.

Representation:

• Adjacency Matrix
• Adjacency List
• Edge List

Types:

• Directed/Undirected
• Weighted/Unweighted
• Cyclic/Acyclic

Use: Social networks, maps, networks

Trie (Prefix Tree)

Tree-like structure for storing strings.

O(L) Search (L = word length)

Pros: Fast prefix search
Use: Autocomplete, spell checkers

5

Algorithms

Searching Algorithms

Linear Search

Sequentially checks each element until target is found.

O(n) Time Complexity O(1) Space Complexity

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Found
    }
  }
  return -1; // Not found
}

Binary Search

Efficiently searches sorted array by repeatedly dividing search interval.

O(log n) Time Complexity O(1) Iterative Space

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable
Bubble Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Selection Sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	No
Insertion Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	No
Heap Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	No

Quick Sort Implementation

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  let pivot = arr[right];
  let i = left - 1;
  
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

Merge Sort Implementation

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

Algorithm Design Paradigms

Greedy Algorithms

Make locally optimal choice at each step hoping for global optimum.

Examples: Dijkstra, Kruskal, Huffman Coding
Pros: Simple, efficient
Cons: Doesn't always give optimal solution
Use: Coin change, scheduling

Dynamic Programming

Break problems into overlapping subproblems, solve each once, store solutions.

Approaches: Top-down (memoization), Bottom-up (tabulation)
Examples: Fibonacci, Knapsack, LCS
Use: Optimization problems

Divide & Conquer

Break problem into smaller subproblems, solve recursively, combine results.

Examples: Merge Sort, Quick Sort, Binary Search
Steps: Divide, Conquer, Combine
Use: Sorting, searching, matrix multiplication

6

Advanced Topics

Graph Algorithms

DFS (Depth-First Search)

Explore as far as possible along each branch before backtracking.

O(V + E) Time (Adjacency List)

function DFS(graph, start) {
  let visited = new Set();
  let stack = [start];
  
  while (stack.length) {
    let node = stack.pop();
    
    if (!visited.has(node)) {
      visited.add(node);
      // Process node
      
      for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

BFS (Breadth-First Search)

Explore neighbor nodes before moving to next level.

O(V + E) Time (Adjacency List)

function BFS(graph, start) {
  let visited = new Set([start]);
  let queue = [start];
  
  while (queue.length) {
    let node = queue.shift();
    // Process node
    
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Dijkstra's Algorithm

Finds shortest path from source to all vertices in weighted graph.

O(E log V) Time (with binary heap)

Use: GPS navigation, network routing

Kruskal's Algorithm

Finds Minimum Spanning Tree (MST) for weighted undirected graph.

O(E log E) Time

Use: Network design, circuit wiring

Advanced Data Structures

Segment Tree

Tree data structure for storing intervals or segments for range queries.

O(log n) Query/Update O(n) Space

Operations: Range sum, min, max, gcd

Fenwick Tree (Binary Indexed Tree)

Efficient data structure for cumulative frequency tables.

O(log n) Query/Update O(n) Space

Use: Frequency counting, prefix sums

Disjoint Set (Union-Find)

Data structure that tracks elements partitioned into disjoint subsets.

O(α(n)) Amortized (inverse Ackermann)

Use: Kruskal's algorithm, network connectivity

Suffix Array & Suffix Tree

Data structures for efficient string pattern searching.

O(m + log n) Pattern Search

Use: Text editors, DNA sequence analysis

7

Languages & Implementation

Which Language to Choose?

Python

Best for beginners & interviews

Simple, readable syntax
Focus on logic over syntax
Rich standard library
Great for learning concepts

Java

Industry standard & interviews

Strong OOP foundation
Strict type system
Extensive collections framework
Preferred by many companies

++

C++

For performance & competitive programming

Fast execution speed
Memory control
STL (Standard Template Library)
Standard in competitions

JavaScript

For web developers

Browser & server-side
Modern ES6+ features
Weak typing (pro & con)
Useful for frontend interviews

Recommendation

Start with Python to learn concepts, then practice in the language you'll use professionally.

DSA concepts are language-agnostic. Master the concepts first, then implementation becomes easier in any language.