All About Data Structures: A Deep Dive into Essential CS Fundamentals

Data structures are the building blocks of efficient software. They determine how data is organized, accessed, and manipulated in memory. Choosing the right data structure can transform an O(n²) algorithm into O(n) or even O(1), making the difference between a sluggish application and a lightning-fast one.

This comprehensive guide explores the seven essential data structures every developer should master, with practical examples, performance analysis, and real-world use cases.

The Essential Data Structures

Let's explore the fundamental data structures every developer should know, organized from simplest to most complex.

1. Arrays

Definition: Items stored at contiguous (adjacent) memory locations, accessed by index.

Visual representation:

Memory Layout:
┌─────┬─────┬─────┬─────┬─────┐
│ 10  │ 25  │ 13  │ 47  │ 32  │
└─────┴─────┴─────┴─────┴─────┘
Index: 0     1     2     3     4

Key Characteristics

• Fixed size (in most languages like C, Java)
• Contiguous memory allocation - elements are stored in adjacent memory locations
• Direct access via index - O(1) lookup time
• Cache-friendly - sequential memory access is fast
• Insertion/deletion is expensive in the middle - O(n) due to shifting

When to Use Arrays

✅ Use when:

• You know the size in advance
• You need fast random access by position
• Elements are accessed more frequently than modified
• Memory is a concern (minimal overhead)

❌ Avoid when:

• Size changes frequently
• You insert/delete elements often in the middle
• Memory needs to be allocated dynamically

Operations and Complexity

Dynamic arrays (like JavaScript's Array, Python's list) resize when needed

Real-World Examples

RGB color storage:

const color = [255, 128, 64]; // Red, Green, Blue
const red = color[0]; // O(1) access

Monthly revenue tracking:

const revenue = [15000, 17500, 16200, 18900, 21000];
const totalRevenue = revenue.reduce((sum, month) => sum + month, 0);

Game board representation:

// Tic-tac-toe board
const board = [
  ["X", "O", "X"],
  ["O", "X", "O"],
  ["X", "O", "X"],
];
console.log(board[1][2]); // Access row 1, col 2: 'O'

Code Implementation

// Create array
const scores = [95, 87, 92, 78, 88];
// Access by index - O(1)
console.log(scores[2]); // 92
// Update by index - O(1)
scores[3] = 85;
// Insert at end - O(1) amortized
scores.push(90);
// Insert at beginning - O(n) due to shifting
scores.unshift(100); // [100, 95, 87, 92, 85, 88, 90]
// Remove from end - O(1)
scores.pop(); // [100, 95, 87, 92, 85, 88]
// Remove from beginning - O(n) due to shifting
scores.shift(); // [95, 87, 92, 85, 88]
// Iterate through all - O(n)
scores.forEach((score) => console.log(score));
// Find element - O(n)
const index = scores.indexOf(92); // 2
// Filter - O(n)
const highScores = scores.filter((score) => score >= 90);

Memory Layout

Arrays store elements in contiguous memory:

Array: [10, 20, 30, 40]
Base Address: 1000
---------------
Memory:
Address | Value
--------|------
1000    | 10
1004    | 20
1008    | 30
1012    | 40
---------------
Access arr[2]:
address = base_address + (index × element_size)
address = 1000 + (2 × 4) = 1008 ✓

This is why array access is O(1) - it's just math!

2. Linked Lists

Definition: A linear data structure where elements (nodes) are connected via pointers/references, each node containing data and a reference to the next node.

Visual representation:

Singly Linked List:
┌──────┬────┐    ┌──────┬────┐    ┌──────┬────┐
│ Data │Next│───▶│ Data │Next│───▶│ Data │Next│───▶ null
└──────┴────┘    └──────┴────┘    └──────┴────┘
  Node 1           Node 2           Node 3
--------------------------------------------------------
Doubly Linked List:
     ┌──────┬────┬────┐    ┌──────┬────┬────┐
null◀│Prev  │Data│Next│───▶│Prev  │Data│Next│───▶ null
     └──────┴────┴────┘    └──────┴────┴────┘

Types of Linked Lists

Singly Linked List:

• Each node points to next node only
• Can only traverse forward
• Less memory per node

Doubly Linked List:

• Each node points to both next and previous nodes
• Can traverse both directions
• More memory per node (two pointers)

Circular Linked List:

• Last node points back to first node
• No null at the end
• Useful for round-robin scheduling

Key Characteristics

• Dynamic size - grows and shrinks as needed
• Non-contiguous memory - nodes can be scattered in memory
• No index-based access - must traverse from head
• Efficient insertions/deletions at known positions - O(1)
• Extra memory for storing pointers

When to Use Linked Lists

✅ Use when:

• Size changes frequently
• You insert/delete elements often
• You don't need random access by index
• Memory is fragmented (non-contiguous allocation is fine)
• Implementing other structures (stacks, queues)

❌ Avoid when:

• You need frequent random access
• Memory is limited (pointer overhead)
• Cache performance matters (poor locality of reference)

Operations and Complexity

Real-World Examples

Browser history:

Current page ←→ Previous page ←→ Previous page ←→ ...
(doubly linked list for back/forward navigation)

Music playlist:

Song 1 → Song 2 → Song 3 → Song 4 → Song 1 (circular)

Undo/redo functionality:

Action 1 → Action 2 → Action 3 (current) → Action 4
         ←          ←           ←

Code Implementation

// Node structure
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
// Singly Linked List
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  // Add to beginning - O(1)
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }
  // Add to end - O(n)
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }
  // Insert at position - O(n)
  insertAt(data, index) {
    if (index < 0 || index > this.size) return false;
    if (index === 0) {
      this.prepend(data);
      return true;
    }
    const newNode = new Node(data);
    let current = this.head;
    let previous;
    let count = 0;
    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }
    newNode.next = current;
    previous.next = newNode;
    this.size++;
    return true;
  }
  // Find element - O(n)
  find(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) return current;
      current = current.next;
    }
    return null;
  }
  // Remove element - O(n)
  remove(data) {
    if (!this.head) return null;
    if (this.head.data === data) {
      this.head = this.head.next;
      this.size--;
      return data;
    }
    let current = this.head;
    let previous = null;
    while (current) {
      if (current.data === data) {
        previous.next = current.next;
        this.size--;
        return data;
      }
      previous = current;
      current = current.next;
    }
    return null;
  }
  // Print list
  print() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.data);
      current = current.next;
    }
    console.log(values.join(" → ") + " → null");
  }
}
// Usage
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print(); // 0 → 1 → 2 → 3 → null
list.insertAt(1.5, 2);
list.print(); // 0 → 1 → 1.5 → 2 → 3 → null
list.remove(1.5);
list.print(); // 0 → 1 → 2 → 3 → null

3. Stacks

Definition: A Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end (the "top").

Visual representation:

Stack Operations:
Push(3):        Push(2):        Push(1):        Pop():
                              ┌───┐           ┌───┐
                              │ 1 │ ← top     │ 2 │ ← top
                ┌───┐         ├───┤           ├───┤
                │ 2 │         │ 2 │           │ 3 │
┌───┐           ├───┤         ├───┤           └───┘
│ 3 │ ← top     │ 3 │         │ 3 │
└───┘           └───┘         └───┘

Key Characteristics

• LIFO (Last-In-First-Out) access pattern
• Two primary operations: push (add) and pop (remove)
• Top pointer tracks the most recently added element
• Can be implemented with arrays or linked lists
• Fixed or dynamic size depending on implementation

Core Operations

Push: Add element to top - O(1)

Pop: Remove element from top - O(1)

Peek/Top: View top element without removing - O(1)

isEmpty: Check if stack is empty - O(1)

Size: Get number of elements - O(1)

When to Use Stacks

✅ Use when:

• You need LIFO behavior
• Implementing undo/redo functionality
• Reversing order of elements
• Tracking state for backtracking algorithms
• Managing function call execution
• Parsing expressions (matching parentheses, evaluating postfix)

❌ Avoid when:

• You need random access to elements
• FIFO behavior is required (use queue instead)
• You need to search through all elements

Real-World Examples

Browser back button:

Current: Page 3
Stack: [Page 1, Page 2, Page 3]
Click Back → Pop Page 3, show Page 2
Click Back → Pop Page 2, show Page 1

Undo/Redo in text editor:

Actions: Type "Hello" → Type "World" → Delete "World"
Undo stack: [Type "Hello", Type "World", Delete "World"]
Undo → Pop "Delete World", restore "Hello World"

Function call stack:

function first() {
  second(); // Push second() onto call stack
}
function second() {
  third(); // Push third() onto call stack
}
function third() {
  console.log("Executing third");
  // Pop third() from call stack
}
first();
// Call stack: [first(), second(), third()]
//              ↑ bottom          ↑ top

Matching parentheses:

Input: "{[()]}"
Stack operations:
Push '{' → ['{']
Push '[' → ['{', '[']
Push '(' → ['{', '[', '(']
Pop  '(' matches ')' → ['{', '[']
Pop  '[' matches ']' → ['{']
Pop  '{' matches '}' → []
Result: Balanced ✓

Code Implementation

class Stack {
  constructor() {
    this.items = [];
  }
  // Push element - O(1)
  push(element) {
    this.items.push(element);
  }
  // Pop element - O(1)
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }
  // Peek at top element - O(1)
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }
  // Check if empty - O(1)
  isEmpty() {
    return this.items.length === 0;
  }
  // Get size - O(1)
  size() {
    return this.items.length;
  }
  // Clear stack - O(1)
  clear() {
    this.items = [];
  }
  // Print stack
  print() {
    console.log(this.items.join(" "));
  }
}
// Usage examples
const stack = new Stack();
// Basic operations
stack.push(1);
stack.push(2);
stack.push(3);
stack.print(); // 1 2 3
console.log(stack.peek()); // 3
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
// 1
stack.print();
// Practical example: Reverse string
function reverseString(str) {
  const stack = new Stack();
  // Push all characters
  for (let char of str) {
    stack.push(char);
  }
  // Pop all characters
  let reversed = "";
  while (!stack.isEmpty()) {
    reversed += stack.pop();
  }
  return reversed;
}
// "olleH"
console.log(reverseString("Hello"));
// Practical example: Balanced parentheses
function isBalanced(expression) {
  const stack = new Stack();
  const opening = "({[";
  const closing = ")}]";
  const pairs = { "(": ")", "{": "}", "[": "]" };
  for (let char of expression) {
    if (opening.includes(char)) {
      stack.push(char);
    } else if (closing.includes(char)) {
      if (stack.isEmpty()) return false;
      const top = stack.pop();
      if (pairs[top] !== char) return false;
    }
  }
  return stack.isEmpty();
}
console.log(isBalanced("{[()]}")); // true
console.log(isBalanced("{[(])}")); // false
console.log(isBalanced("{{{")); // false

Stack vs Array

While stacks can be implemented with arrays, they have conceptual differences:

4. Queues

Definition: A First-In-First-Out (FIFO) data structure where elements are added at one end (rear) and removed from the other end (front).

Visual representation:

Queue Operations:
Enqueue(1):     Enqueue(2):     Enqueue(3):     Dequeue():
┌───┐           ┌───┬───┐       ┌───┬───┬───┐   ┌───┬───┐
│ 1 │           │ 1 │ 2 │       │ 1 │ 2 │ 3 │   │ 2 │ 3 │
└───┘           └───┴───┘       └───┴───┴───┘   └───┴───┘
↑               ↑       ↑       ↑           ↑   ↑       ↑
Front/Rear      Front   Rear    Front       Rear Front   Rear

Types of Queues

Simple Queue: Standard FIFO queue

Circular Queue: Last position connects to first position (circular array)

Circular Queue:
┌───┬───┬───┬───┐
│ 3 │ 4 │ 1 │ 2 │
└───┴───┴───┴───┘
      ↑       ↑
    Rear    Front

Priority Queue: Elements have priorities, higher priority elements dequeued first

Deque (Double-ended Queue): Can add/remove from both ends

Key Characteristics

• FIFO (First-In-First-Out) access pattern
• Two primary operations: enqueue (add to rear) and dequeue (remove from front)
• Two pointers: front and rear
• Can be implemented with arrays or linked lists
• Fair processing - maintains order of arrival

Core Operations

Enqueue: Add element to rear - O(1)

Dequeue: Remove element from front - O(1)

Front/Peek: View front element without removing - O(1)

isEmpty: Check if queue is empty - O(1)

Size: Get number of elements - O(1)

When to Use Queues

✅ Use when:

• You need FIFO behavior
• Processing items in order of arrival
• Breadth-first search (BFS) in graphs/trees
• Task scheduling and job queues
• Buffering data streams
• Managing shared resources (print queues, CPU scheduling)

❌ Avoid when:

• You need LIFO behavior (use stack instead)
• Priority-based processing needed (use priority queue)
• Random access required (use array)

Real-World Examples

Print queue:

Queue: [Job1, Job2, Job3]
Printer processes: Job1 → Job2 → Job3 (in order)

Customer service:

Customers: [Alice, Bob, Charlie]
Serve: Alice (first), then Bob, then Charlie

Message queue (Kafka, RabbitMQ):

Producer → [Msg1, Msg2, Msg3, ...] → Consumer
           ↑                     ↑
         Enqueue              Dequeue

Breadth-First Search:

// BFS uses queue to process nodes level by level
//       1
//      / \
//     2   3
//    / \
//   4   5
Queue processing order:
Start: [1]
Process 1, add children: [2, 3]
Process 2, add children: [3, 4, 5]
Process 3: [4, 5]
Process 4: [5]
Process 5: []

Code Implementation

class Queue {
  constructor() {
    this.items = [];
  }
  // Enqueue (add to rear) - O(1)
  enqueue(element) {
    this.items.push(element);
  }
  // Dequeue (remove from front) - O(n) for array, O(1) for linked list
  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items.shift();
  }
  // Peek at front element - O(1)
  front() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }
  // Check if empty - O(1)
  isEmpty() {
    return this.items.length === 0;
  }
  // Get size - O(1)
  size() {
    return this.items.length;
  }
  // Clear queue - O(1)
  clear() {
    this.items = [];
  }
  // Print queue
  print() {
    console.log(this.items.join(" ← "));
  }
}
// Usage examples
const queue = new Queue();
// Basic operations
queue.enqueue("Customer 1");
queue.enqueue("Customer 2");
queue.enqueue("Customer 3");
queue.print(); // Customer 1 ← Customer 2 ← Customer 3
console.log(queue.front()); // Customer 1
console.log(queue.dequeue()); // Customer 1
console.log(queue.dequeue()); // Customer 2
queue.print(); // Customer 3
// Practical example: Hot Potato game
function hotPotato(names, num) {
  const queue = new Queue();
  // Add all players to queue
  names.forEach((name) => queue.enqueue(name));
  // Pass the potato
  while (queue.size() > 1) {
    // Pass potato num times
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // Eliminate player holding potato
    const eliminated = queue.dequeue();
    console.log(`${eliminated} was eliminated`);
  }
  return queue.dequeue(); // Winner
}
const players = ["Alice", "Bob", "Charlie", "David", "Eve"];
const winner = hotPotato(players, 3);
console.log(`Winner: ${winner}`);

Optimized Queue with Linked List

class QueueNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
// Optimized Queue
class OptimizedQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }
  // Enqueue - O(1)
  enqueue(data) {
    const newNode = new QueueNode(data);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.length++;
  }
  // Dequeue - O(1)
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const data = this.front.data;
    this.front = this.front.next;
    this.length--;
    if (this.length === 0) {
      this.rear = null;
    }
    return data;
  }
  // Peek - O(1)
  peek() {
    return this.isEmpty() ? null : this.front.data;
  }
  isEmpty() {
    return this.length === 0;
  }
  size() {
    return this.length;
  }
}

5. Trees

Definition: A hierarchical data structure consisting of nodes connected by edges, with a single root node and parent-child relationships.

Visual representation:

Binary Tree:
        1 (root)
       / \
      2   3
     / \   \
    4   5   6
Tree Terminology:
- Root: Node 1
- Parent of 4,5: Node 2
- Children of 2: Nodes 4,5
- Leaf nodes: 4,5,6
- Height: 3 levels
- Depth of node 5: 2

Tree Types

Binary Tree: Each node has at most 2 children (left, right)

Binary Search Tree (BST): Binary tree where left child < parent < right child

BST Example:
      8
     / \
    3   10
   / \    \
  1   6   14
     / \  /
    4  7 13

AVL Tree: Self-balancing BST (heights differ by at most 1)

Red-Black Tree: Self-balancing BST with color properties

B-Tree: Multi-way tree used in databases and file systems

Trie (Prefix Tree): Tree for storing strings with shared prefixes

Heap: Complete binary tree (min-heap or max-heap)

Key Characteristics

• Hierarchical structure with parent-child relationships
• Root node at the top
• Leaf nodes have no children
• No cycles - can't loop back to ancestors
• Efficient searching (BST: O(log n) average case)
• Recursive nature - subtrees are also trees

Tree Traversal Methods

Depth-First Search (DFS):

In-Order (Left → Root → Right): 4, 2, 5, 1, 3, 6 - Gives sorted order for BST

Pre-Order (Root → Left → Right): 1, 2, 4, 5, 3, 6 - Used for creating copy of tree

Post-Order (Left → Right → Root): 4, 5, 2, 6, 3, 1 - Used for deleting tree

Breadth-First Search (BFS) / Level-Order: 1, 2, 3, 4, 5, 6 - Process level by level using queue

When to Use Trees

✅ Use when:

• Data has hierarchical relationships
• Need fast search, insert, delete (BST: O(log n))
• Maintaining sorted data with dynamic changes
• Representing file systems, organization charts
• Implementing priority queues (heaps)
• Prefix-based searches (tries)

❌ Avoid when:

• Data is linear without hierarchy
• Need guaranteed O(1) access (use hash table)
• Simple key-value lookups suffice

Real-World Examples

File system:

/
├── home/
│   ├── user/
│   │   ├── documents/
│   │   └── downloads/
│   └── admin/
└── var/
    └── log/

DOM (Document Object Model):

<html>
  <head>
    <title>Page</title>
  </head>
  <body>
    <div>
      <p>Content</p>
    </div>
  </body>
</html>

Decision tree (AI/ML):

Is temperature > 25°C?
├── Yes → Is sunny?
│   ├── Yes → Go to beach
│   └── No → Stay home
└── No → Is raining?
    ├── Yes → Watch movie
    └── No → Go for walk

Code Implementation

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
// BST
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  // Insert - O(log n) average, O(n) worst case
  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined; // Duplicate
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }
  // Search - O(log n) average, O(n) worst case
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
  // Find minimum - O(log n)
  findMin(node = this.root) {
    while (node.left) {
      node = node.left;
    }
    return node.value;
  }
  // Find maximum - O(log n)
  findMax(node = this.root) {
    while (node.right) {
      node = node.right;
    }
    return node.value;
  }
  // In-order traversal (Left → Root → Right)
  inOrder(node = this.root, result = []) {
    if (node) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }
  // Pre-order traversal (Root → Left → Right)
  preOrder(node = this.root, result = []) {
    if (node) {
      result.push(node.value);
      this.preOrder(node.left, result);
      this.preOrder(node.right, result);
    }
    return result;
  }
  // Post-order traversal (Left → Right → Root)
  postOrder(node = this.root, result = []) {
    if (node) {
      this.postOrder(node.left, result);
      this.postOrder(node.right, result);
      result.push(node.value);
    }
    return result;
  }
  // Level-order traversal (BFS)
  levelOrder() {
    if (!this.root) return [];
    const result = [];
    const queue = [this.root];
    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return result;
  }
  // Get height of tree
  height(node = this.root) {
    if (!node) return -1;
    const leftHeight = this.height(node.left);
    const rightHeight = this.height(node.right);
    return Math.max(leftHeight, rightHeight) + 1;
  }
  // Check if tree is balanced
  isBalanced(node = this.root) {
    if (!node) return true;
    const leftHeight = this.height(node.left);
    const rightHeight = this.height(node.right);
    return (
      Math.abs(leftHeight - rightHeight) <= 1 &&
      this.isBalanced(node.left) &&
      this.isBalanced(node.right)
    );
  }
}
// Usage
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(18);
console.log(bst.search(7)); // true
console.log(bst.search(20)); // false
console.log(bst.inOrder()); // [3, 5, 7, 10, 12, 15, 18]
console.log(bst.preOrder()); // [10, 5, 3, 7, 15, 12, 18]
console.log(bst.postOrder()); // [3, 7, 5, 12, 18, 15, 10]
console.log(bst.levelOrder()); // [10, 5, 15, 3, 7, 12, 18]
console.log(bst.height()); // 2
console.log(bst.isBalanced()); // true

Time Complexity Comparison

Worst case occurs with skewed tree (essentially becomes linked list)

6. Graphs

Definition: A non-linear data structure consisting of vertices (nodes) connected by edges, representing relationships or connections between entities.

Visual representation:

Undirected Graph:        Directed Graph (Digraph):
    A --- B                  A ──▶ B
    |     |                  ▲     │
    |     |                  │     ▼
    C --- D                  C ◀── D
Weighted Graph:
    A ─5─ B
    |      |
    3      2
    |      |
    C ─1─  D

Graph Types

By Direction:

• Undirected: Edges have no direction (friendship: bidirectional)
• Directed (Digraph): Edges have direction (follow on social media: one-way)

By Weight:

• Weighted: Edges have values/weights (road distances)
• Unweighted: All edges are equal (friendships)

By Connectivity:

• Connected: Path exists between any two vertices
• Disconnected: Some vertices unreachable from others

Special Types:

• Cyclic: Contains at least one cycle
• Acyclic: No cycles (DAG - Directed Acyclic Graph)
• Complete: Every vertex connected to every other vertex

Graph Representations

1. Adjacency Matrix (2D array):

Graph:  A --- B
        |     |
        C --- D
Matrix:
    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  0  1 ]
C [ 1  0  0  1 ]
D [ 0  1  1  0 ]
Space: O(V²)
Edge lookup: O(1)

2. Adjacency List (array/map of lists):

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]
---------------------
Space: O(V + E)
Edge lookup: O(degree)

3. Edge List (list of edges):

[(A, B), (A, C), (B, D), (C, D)]
Space: O(E)

Key Characteristics

• Vertices (V) and Edges (E)
• Flexible relationships - any vertex can connect to any other
• Cycles may exist
• Multiple representations (matrix vs list)
• Weighted or unweighted edges
• Directed or undirected connections

Graph Traversal Algorithms

Depth-First Search (DFS) - Uses stack/recursion:

Visit A → Go deep to B → Go deep to D → Backtrack

Breadth-First Search (BFS) - Uses queue:

Visit A → Visit all neighbors (B, C) → Visit their neighbors (D)

Common Graph Algorithms

• Shortest Path: Dijkstra's, Bellman-Ford, Floyd-Warshall
• Minimum Spanning Tree: Kruskal's, Prim's
• Cycle Detection: DFS-based
• Topological Sort: For DAGs
• Connected Components: Union-Find, DFS/BFS

When to Use Graphs

✅ Use when:

• Modeling networks (social, computer, transportation)
• Finding shortest paths
• Representing dependencies
• Analyzing relationships
• Recommendation systems
• Route planning

❌ Avoid when:

• Data is hierarchical (use tree instead)
• Simple linear relationships (use array/list)
• No relationships between entities

Real-World Examples

Social network:

Users = Vertices
Friendships = Edges
----------------------
Alice ─── Bob
  |        |
  |        |
Charlie ─ David

GPS navigation:

Cities = Vertices
Roads = Edges (weighted by distance)
Find shortest path from A to D

Web crawler:

Web pages = Vertices
Hyperlinks = Directed edges
Follow links to discover new pages

Course prerequisites:

Courses = Vertices
Prerequisites = Directed edges
CS101 → CS201 → CS301
  ↓              ↓
CS102 ──────→ CS401

Code Implementation

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }
  // Add vertex - O(1)
  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }
  // Add edge (undirected) - O(1)
  addEdge(vertex1, vertex2) {
    if (!this.adjacencyList.has(vertex1)) {
      this.addVertex(vertex1);
    }
    if (!this.adjacencyList.has(vertex2)) {
      this.addVertex(vertex2);
    }
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1); // Remove for directed
  }
  // Add weighted edge
  addWeightedEdge(vertex1, vertex2, weight) {
    this.adjacencyList.get(vertex1).push({ node: vertex2, weight });
    this.adjacencyList.get(vertex2).push({ node: vertex1, weight });
  }
  // Remove edge - O(E)
  removeEdge(vertex1, vertex2) {
    this.adjacencyList.set(
      vertex1,
      this.adjacencyList.get(vertex1).filter((v) => v !== vertex2),
    );
    this.adjacencyList.set(
      vertex2,
      this.adjacencyList.get(vertex2).filter((v) => v !== vertex1),
    );
  }
  // Remove vertex - O(V + E)
  removeVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) return;
    // Remove all edges to this vertex
    for (let adjacentVertex of this.adjacencyList.get(vertex)) {
      this.removeEdge(vertex, adjacentVertex);
    }
    this.adjacencyList.delete(vertex);
  }
  // DFS - Recursive - O(V + E)
  dfsRecursive(start) {
    const result = [];
    const visited = new Set();
    const dfs = (vertex) => {
      if (!vertex) return;
      visited.add(vertex);
      result.push(vertex);
      for (let neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          dfs(neighbor);
        }
      }
    };
    dfs(start);
    return result;
  }
  // DFS - Iterative - O(V + E)
  dfsIterative(start) {
    const stack = [start];
    const result = [];
    const visited = new Set();
    visited.add(start);
    while (stack.length > 0) {
      const vertex = stack.pop();
      result.push(vertex);
      for (let neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          stack.push(neighbor);
        }
      }
    }
    return result;
  }
  // BFS - O(V + E)
  bfs(start) {
    const queue = [start];
    const result = [];
    const visited = new Set();
    visited.add(start);
    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);
      for (let neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return result;
  }
  // Find shortest path (unweighted) - BFS
  shortestPath(start, end) {
    const queue = [[start]];
    const visited = new Set();
    visited.add(start);
    while (queue.length > 0) {
      const path = queue.shift();
      const vertex = path[path.length - 1];
      if (vertex === end) {
        return path;
      }
      for (let neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([...path, neighbor]);
        }
      }
    }
    return null; // No path found
  }
  // Check if graph has cycle (undirected)
  hasCycle() {
    const visited = new Set();
    const dfs = (vertex, parent) => {
      visited.add(vertex);
      for (let neighbor of this.adjacencyList.get(vertex)) {
        if (!visited.has(neighbor)) {
          if (dfs(neighbor, vertex)) return true;
        } else if (neighbor !== parent) {
          return true; // Found cycle
        }
      }
      return false;
    };
    for (let vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        if (dfs(vertex, null)) return true;
      }
    }
    return false;
  }
  // Print graph
  print() {
    for (let [vertex, edges] of this.adjacencyList) {
      console.log(`${vertex} → ${edges.join(", ")}`);
    }
  }
}
// Usage
const graph = new Graph();
// Add vertices
["A", "B", "C", "D", "E"].forEach((v) => graph.addVertex(v));
// Add edges
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
graph.addEdge("D", "E");
graph.print();
// A → B, C
// B → A, D
// C → A, D
// D → B, C, E
// E → D
console.log("DFS:", graph.dfsRecursive("A")); // [A, B, D, C, E]
console.log("BFS:", graph.bfs("A")); // [A, B, C, D, E]
console.log("Shortest Path A→E:", graph.shortestPath("A", "E")); // [A, B, D, E]
console.log("Has Cycle:", graph.hasCycle()); // true

7. Hash Tables

Definition: A data structure that stores key-value pairs and uses a hash function to compute an index into an array of buckets, enabling fast lookups, insertions, and deletions.

Visual representation:

Hash Function:
key "apple" ──▶ hash("apple") = 5 ──▶ Array[5] = "red"
key "banana" ──▶ hash("banana") = 2 ──▶ Array[2] = "yellow"
------------
Hash Table:
Index  Value
  0  → null
  1  → null
  2  → "banana" → "yellow"
  3  → null
  4  → null
  5  → "apple" → "red"
  6  → null
------------
Collision Handling (Chaining):
Index  Linked List
  2  → ["banana","yellow"] → ["orange","orange"] → null

Key Concepts

Hash Function: Converts key to array index

hash(key) = index

Good hash function properties:

• Deterministic: Same key always produces same hash
• Uniform distribution: Spreads keys evenly across array
• Fast to compute: O(1) time complexity
• Minimizes collisions: Different keys rarely produce same hash

Collisions: When two different keys hash to the same index

Collision Resolution:

1. . Chaining: Store multiple values at same index using linked list
2. . Open Addressing: Find next available slot (linear probing, quadratic probing, double hashing)

Key Characteristics

• Average O(1) for search, insert, delete
• Unordered - no guaranteed sequence
• Unique keys - each key appears once
• Hash function critical for performance
• Load factor (n/m) affects performance
• - n = number of entries
• - m = number of buckets
• - Typically resize when load factor > 0.7

When to Use Hash Tables

✅ Use when:

• Fast lookups by key are critical
• Counting occurrences (frequency maps)
• Caching/memoization
• Removing duplicates
• Implementing sets and maps
• Database indexing

❌ Avoid when:

• Need ordered data (use BST instead)
• Need range queries (use tree)
• Memory is extremely limited (overhead for hash function + array)
• Keys are difficult to hash effectively

Real-World Examples

Database indexing:

User ID (key) → User Record (value)
hash(12345) → {name: "Alice", email: "alice@example.com"}

Caching:

URL (key) → Cached Response (value)
hash("api.example.com/users") → {data: [...], timestamp: 1234567890}

Symbol table in compiler:

Variable name (key) → Variable info (value)
hash("userName") → {type: "string", scope: "global", line: 42}

Two-sum problem:

// Find two numbers that sum to target
nums = [2, 7, 11, 15], target = 9
Hash table: {2: 0, 7: 1, ...}
For 7: Check if (9 - 7 = 2) exists in hash → Yes! Return [0, 1]

Code Implementation

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
    this.size = size;
  }
  // Simple hash function
  _hash(key) {
    let total = 0;
    const PRIME = 31; // Prime number reduces collisions
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.size;
    }
    return total;
  }
  // Set key-value pair - O(1) average
  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    // Check if key exists, update value
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        this.keyMap[index][i][1] = value;
        return;
      }
    }
    // Add new key-value pair
    this.keyMap[index].push([key, value]);
  }
  // Get value by key - O(1) average
  get(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          return this.keyMap[index][i][1];
        }
      }
    }
    return undefined;
  }
  // Check if key exists - O(1) average
  has(key) {
    return this.get(key) !== undefined;
  }
  // Delete key-value pair - O(1) average
  delete(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          this.keyMap[index].splice(i, 1);
          return true;
        }
      }
    }
    return false;
  }
  // Get all keys - O(n)
  keys() {
    const keysArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          keysArr.push(this.keyMap[i][j][0]);
        }
      }
    }
    return keysArr;
  }
  // Get all values - O(n)
  values() {
    const valuesArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!valuesArr.includes(this.keyMap[i][j][1])) {
            valuesArr.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    return valuesArr;
  }
  // Clear hash table - O(1)
  clear() {
    this.keyMap = new Array(this.size);
  }
  // Get size - O(n)
  getSize() {
    let count = 0;
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        count += this.keyMap[i].length;
      }
    }
    return count;
  }
}
// Usage
const ht = new HashTable();
// Set values
ht.set("apple", "red");
ht.set("banana", "yellow");
ht.set("grape", "purple");
ht.set("orange", "orange");
// Get values
console.log(ht.get("apple")); // "red"
console.log(ht.get("banana")); // "yellow"
console.log(ht.get("cherry")); // undefined
// Check existence
console.log(ht.has("grape")); // true
console.log(ht.has("kiwi")); // false
// Delete
ht.delete("banana");
console.log(ht.get("banana")); // undefined
// Get all keys and values
console.log(ht.keys()); // ["apple", "grape", "orange"]
console.log(ht.values()); // ["red", "purple", "orange"]
// Practical example: Count character frequency
function charFrequency(str) {
  const freq = new HashTable();
  for (let char of str.toLowerCase()) {
    if (char.match(/[a-z]/)) {
      const count = freq.get(char) || 0;
      freq.set(char, count + 1);
    }
  }
  return freq;
}
const freq = charFrequency("Hello World");
console.log(freq.get("l")); // 3
console.log(freq.get("o")); // 2
// Practical example: Two sum problem
function twoSum(nums, target) {
  const map = new HashTable();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement.toString())) {
      return [map.get(complement.toString()), i];
    }
    map.set(nums[i].toString(), i);
  }
  return null;
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

JavaScript Built-in: Map vs Object

// Map - Better for hash table use
const map = new Map();
map.set("key1", "value1");
map.set(123, "numeric key"); // Any type as key
map.set({ obj: 1 }, "object key");
console.log(map.size); // 3
map.has("key1"); // true
map.delete("key1");
// Object - Simple key-value pairs
const obj = {};
obj["key1"] = "value1";
obj[123] = "numeric key"; // Converted to string
// Only string/symbol keys
console.log(Object.keys(obj).length);
"key1" in obj; // true
delete obj.key1;

When to use Map:

• Keys that aren't strings
• Need to iterate in insertion order
• Frequent additions/deletions
• Need size property

When to use Object:

• Simple string keys
• JSON serialization needed
• Property access syntax preferred

Time Complexity Comparison

At known position †Average case (worst case can be O(n) with poor hash function)

Choosing the Right Data Structure

Decision Framework

Ask yourself these questions:

1. What operations are most frequent?

• Frequent lookups by key → Hash Table
• Frequent lookups by index → Array
• Frequent insertions/deletions → Linked List
• Need min/max quickly → Heap
• Need sorted order → BST

2. Is there a natural ordering?

• LIFO (Last-In-First-Out) → Stack
• FIFO (First-In-First-Out) → Queue
• Sorted data → BST
• Priority-based → Priority Queue (Heap)
• No ordering needed → Hash Table

3. What is the data structure?

• Linear sequence → Array, Linked List
• Hierarchical → Tree
• Network/relationships → Graph
• Key-value pairs → Hash Table

4. What are the constraints?

• Fixed size known → Array
• Dynamic size → Linked List, Dynamic Array
• Memory limited → Array (low overhead)
• Need O(1) operations → Hash Table, Stack, Queue

5. What's the access pattern?

• Random access needed → Array
• Sequential access → Linked List
• Top/Front access only → Stack/Queue
• By key access → Hash Table

Practical Use Cases by Domain

Web Development

• Browser history: Stack (back button), Linked List (back/forward)
• Event loop: Queue
• DOM: Tree
• Client-side routing: Trie
• Cache: Hash Table
• Session storage: Hash Table

Databases

• Indexing: B-Tree, Hash Table
• Query optimization: Graph
• Connection pooling: Queue
• Transaction log: Linked List
• Join operations: Hash Table

Operating Systems

• Process scheduling: Queue
• File system: Tree
• Memory management: Linked List
• Page replacement: Stack, Queue (LRU cache)
• Network routing: Graph

Algorithms

• DFS: Stack
• BFS: Queue
• Dijkstra's shortest path: Priority Queue (Heap)
• Topological sort: Graph + Stack
• Dynamic programming: Array, Hash Table (memoization)

Social Networks

• Friend connections: Graph
• Feed generation: Priority Queue
• User lookup: Hash Table
• Message threads: Tree
• Notifications: Queue

Advanced Considerations

Load Factor and Resizing

Hash tables maintain performance through load factor management:

Load Factor = Number of Entries / Array Size
Example:
Entries: 7
Array Size: 10
Load Factor: 0.7
When load factor > threshold (typically 0.75):
1. Create new array (usually 2× size)
2. Rehash all entries
3. Insert into new array

Amortized Analysis

Some operations have different average vs worst-case complexity:

Dynamic Array:

• Most insertions: O(1)
• Occasional resize: O(n)
• Amortized: O(1) - averaged over many operations

Cache Performance

Arrays have better cache performance than Linked Lists:

Array (contiguous memory):
[1][2][3][4] → Cache loads 1-4 together → Fast!
------------------------------------------------
Linked List (scattered memory):
[1]→...→[2]→...→[3] → Each node may cause cache miss → Slower!

Key Takeaways

1. Arrays - Fast access, slow insertion/deletion

• Use for: Fixed-size data, frequent random access

2. Linked Lists - Dynamic size, fast insertion/deletion at known positions

• Use for: Frequent insertions/deletions, unknown size

3. Stacks - LIFO access

• Use for: Undo/redo, backtracking, parsing

4. Queues - FIFO access

• Use for: Scheduling, buffering, BFS

5. Trees - Hierarchical, fast search (BST)

• Use for: Hierarchical data, sorted data with changes

6. Graphs - Complex relationships

• Use for: Networks, pathfinding, dependencies

7. Hash Tables - Ultra-fast lookups

• Use for: Key-value lookups, caching, deduplication

Practice Makes Perfect

Understanding data structures theoretically is just the beginning. The real mastery comes from:

• Implementing them yourself - Don't just use built-ins
• Solving problems - LeetCode, HackerRank, etc.
• Analyzing trade-offs - Why choose one over another?
• Optimizing real code - Apply to actual projects

Data structures are tools in your programming toolbox. The more you practice, the more instinctively you'll reach for the right tool for each job.