Data Structures

Arrays

Arrays store elements in contiguous memory locations, allowing fast access by index. Each element can be accessed directly using its position.

🏠 Real-Life Analogy:

Think of an apartment building where each apartment has a number. You can go directly to apartment #5 without visiting apartments 1-4 first. Arrays work the same way - you can access element at index 5 directly.

TypeScript

// Array operations
const numbers: number[] = [10, 20, 30, 40, 50];

// Access by index - O(1)
console.log(numbers[2]); // 30

// Insert at end - O(1)
numbers.push(60);

// Insert at beginning - O(n) because all elements shift
numbers.unshift(5);

// Search for element - O(n)
function findIndex(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

// Traverse array - O(n)
function printAll(arr: number[]): void {
    for (const num of arr) {
        console.log(num);
    }
}

Python

# Array operations (using lists in Python)
numbers = [10, 20, 30, 40, 50]

# Access by index - O(1)
print(numbers[2])  # 30

# Insert at end - O(1)
numbers.append(60)

# Insert at beginning - O(n) because all elements shift
numbers.insert(0, 5)

# Search for element - O(n)
def find_index(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i
    return -1

# Traverse array - O(n)
def print_all(arr):
    for num in arr:
        print(num)

OCaml

(* Array operations *)
let numbers = [|10; 20; 30; 40; 50|]

(* Access by index - O(1) *)
let third_element = numbers.(2) (* 30 *)

(* Search for element - O(n) *)
let rec find_index arr target index =
  if index >= Array.length arr then -1
  else if arr.(index) = target then index
  else find_index arr target (index + 1)

(* Traverse array - O(n) *)
let print_all arr =
  Array.iter (fun x -> Printf.printf "%d " x) arr

(* Create new array with element added *)
let add_element arr element =
  let new_arr = Array.make (Array.length arr + 1) 0 in
  Array.blit arr 0 new_arr 0 (Array.length arr);
  new_arr.(Array.length arr) <- element;
  new_arr

Linked Lists

A linked list is a linear data structure where elements (nodes) are stored in sequence, but not in contiguous memory. Each node contains data and a reference to the next node.

🔗 Real-Life Analogy:

Think of a treasure hunt where each clue leads to the next location. You can't skip ahead - you must follow the chain from one clue to the next. Similarly, in a linked list, you must traverse from the head to reach any element.

TypeScript

// Node structure
class ListNode {
    data: number;
    next: ListNode | null;
    
    constructor(data: number) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    head: ListNode | null = null;
    
    // Insert at beginning - O(1)
    insertAtHead(data: number): void {
        const newNode = new ListNode(data);
        newNode.next = this.head;
        this.head = newNode;
    }
    
    // Search for element - O(n)
    search(target: number): boolean {
        let current = this.head;
        while (current !== null) {
            if (current.data === target) return true;
            current = current.next;
        }
        return false;
    }
    
    // Delete element - O(n)
    delete(target: number): boolean {
        if (!this.head) return false;
        
        if (this.head.data === target) {
            this.head = this.head.next;
            return true;
        }
        
        let current = this.head;
        while (current.next && current.next.data !== target) {
            current = current.next;
        }
        
        if (current.next) {
            current.next = current.next.next;
            return true;
        }
        return false;
    }
}

Python

# Node structure
class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    # Insert at beginning - O(1)
    def insert_at_head(self, data):
        new_node = ListNode(data)
        new_node.next = self.head
        self.head = new_node
    
    # Search for element - O(n)
    def search(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False
    
    # Delete element - O(n)
    def delete(self, target):
        if not self.head:
            return False
        
        if self.head.data == target:
            self.head = self.head.next
            return True
        
        current = self.head
        while current.next and current.next.data != target:
            current = current.next
        
        if current.next:
            current.next = current.next.next
            return True
        return False

OCaml

(* Node structure *)
type 'a node = {
  data: 'a;
  mutable next: 'a node option;
}

type 'a linked_list = {
  mutable head: 'a node option;
}

(* Create new list *)
let create_list () = { head = None }

(* Insert at beginning - O(1) *)
let insert_at_head list data =
  let new_node = { data = data; next = list.head } in
  list.head <- Some new_node

(* Search for element - O(n) *)
let rec search_helper node target =
  match node with
  | None -> false
  | Some n -> 
      if n.data = target then true
      else search_helper n.next target

let search list target = search_helper list.head target

(* Delete element - O(n) *)
let delete list target =
  match list.head with
  | None -> false
  | Some head_node ->
      if head_node.data = target then (
        list.head <- head_node.next;
        true
      ) else (
        let rec delete_helper node =
          match node.next with
          | None -> false
          | Some next_node ->
              if next_node.data = target then (
                node.next <- next_node.next;
                true
              ) else delete_helper next_node
        in
        delete_helper head_node
      )

Stack

A stack is a Last-In-First-Out (LIFO) data structure. Elements are added and removed from the same end, called the "top" of the stack.

🍽️ Real-Life Analogy:

Think of a stack of plates in a cafeteria. You can only add a new plate to the top, and you can only take a plate from the top. The last plate you put on is the first one you'll take off.

TypeScript

class Stack {
    private items: T[] = [];
    
    // Push element to top - O(1)
    push(element: T): void {
        this.items.push(element);
    }
    
    // Pop element from top - O(1)
    pop(): T | undefined {
        return this.items.pop();
    }
    
    // Peek at top element - O(1)
    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }
    
    // Check if stack is empty - O(1)
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    
    // Get stack size - O(1)
    size(): number {
        return this.items.length;
    }
}

// Example usage
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.pop()); // 30 (last in, first out)
console.log(stack.peek()); // 20

Python

class Stack:
    def __init__(self):
        self.items = []
    
    # Push element to top - O(1)
    def push(self, element):
        self.items.append(element)
    
    # Pop element from top - O(1)
    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()
    
    # Peek at top element - O(1)
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]
    
    # Check if stack is empty - O(1)
    def is_empty(self):
        return len(self.items) == 0
    
    # Get stack size - O(1)
    def size(self):
        return len(self.items)

# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())  # 30 (last in, first out)
print(stack.peek())  # 20

OCaml

(* Stack implementation using list *)
type 'a stack = 'a list ref

(* Create new stack *)
let create_stack () = ref []

(* Push element to top - O(1) *)
let push stack element =
  stack := element :: !stack

(* Pop element from top - O(1) *)
let pop stack =
  match !stack with
  | [] -> None
  | head :: tail ->
      stack := tail;
      Some head

(* Peek at top element - O(1) *)
let peek stack =
  match !stack with
  | [] -> None
  | head :: _ -> Some head

(* Check if stack is empty - O(1) *)
let is_empty stack = !stack = []

(* Get stack size - O(n) *)
let size stack = List.length !stack

(* Example usage *)
let stack = create_stack ();;
push stack 10;;
push stack 20;;
push stack 30;;
let popped = pop stack;; (* Some 30 (last in, first out) *)
let top = peek stack;; (* Some 20 *)

Queue

A queue is a First-In-First-Out (FIFO) data structure. Elements are added at the rear (enqueue) and removed from the front (dequeue).

🚶‍♀️ Real-Life Analogy:

Think of a line at a grocery store checkout. The first person to join the line is the first person to be served. New people join at the back of the line, and people leave from the front.

TypeScript

class Queue {
    private items: T[] = [];
    
    // Add element to rear - O(1)
    enqueue(element: T): void {
        this.items.push(element);
    }
    
    // Remove element from front - O(n) due to array shift
    dequeue(): T | undefined {
        return this.items.shift();
    }
    
    // Peek at front element - O(1)
    front(): T | undefined {
        return this.items[0];
    }
    
    // Check if queue is empty - O(1)
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    
    // Get queue size - O(1)
    size(): number {
        return this.items.length;
    }
}

// Example usage
const queue = new Queue();
queue.enqueue("Alice");
queue.enqueue("Bob");
queue.enqueue("Charlie");
console.log(queue.dequeue()); // "Alice" (first in, first out)
console.log(queue.front()); // "Bob"

Python

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()  # More efficient for queue operations
    
    # Add element to rear - O(1)
    def enqueue(self, element):
        self.items.append(element)
    
    # Remove element from front - O(1)
    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.popleft()
    
    # Peek at front element - O(1)
    def front(self):
        if self.is_empty():
            return None
        return self.items[0]
    
    # Check if queue is empty - O(1)
    def is_empty(self):
        return len(self.items) == 0
    
    # Get queue size - O(1)
    def size(self):
        return len(self.items)

# Example usage
queue = Queue()
queue.enqueue("Alice")
queue.enqueue("Bob")
queue.enqueue("Charlie")
print(queue.dequeue())  # "Alice" (first in, first out)
print(queue.front())  # "Bob"

OCaml

(* Queue implementation using two lists for efficiency *)
type 'a queue = {
  mutable front: 'a list;
  mutable rear: 'a list;
}

(* Create new queue *)
let create_queue () = { front = []; rear = [] }

(* Add element to rear - O(1) *)
let enqueue queue element =
  queue.rear <- element :: queue.rear

(* Remove element from front - Amortized O(1) *)
let dequeue queue =
  match queue.front with
  | head :: tail ->
      queue.front <- tail;
      Some head
  | [] ->
      match List.rev queue.rear with
      | [] -> None
      | head :: tail ->
          queue.front <- tail;
          queue.rear <- [];
          Some head

(* Example usage *)
let queue = create_queue ();;
enqueue queue "Alice";;
enqueue queue "Bob";;
enqueue queue "Charlie";;
let first = dequeue queue;; (* Some "Alice" (first in, first out) *)

DSA Interview Guide

Ready to learn algorithms?