Data Structures & Algorithms

Comprehensive Final Exam Review

---

PART 1: Structured Data & Objects

What is Structured Data?

Structured data organizes information into well-defined formats so programs can store, access, and manipulate it efficiently.

Key categories:

Type	Description	Ruby Example
Primitive	Single values	42, "hello", true
Composite	Groups of values	Arrays, Hashes, Structs
Abstract	Logical structure	Stack, Queue, Tree

Structured data is the foundation of every data structure we study.

---

Objects – Attributes and Methods

An object bundles data (attributes) and behavior (methods) together.

class BankAccount
  # Attributes
  attr_accessor :owner, :balance

  def initialize(owner, balance = 0)
    @owner   = owner     # instance variable = attribute
    @balance = balance
  end

  # Methods (behavior)
  def deposit(amount)
    @balance += amount
  end

  def withdraw(amount)
    @balance -= amount if amount <= @balance
  end

  def to_s
    "#{@owner}: $#{@balance}"
  end
end

acct = BankAccount.new("Alice", 500)
acct.deposit(200)
puts acct   # => Alice: $700

---

Records and Fields

A record is a composite data structure with named fields — similar to a row in a database table.

In Ruby, use Struct for lightweight records:

# Define a record type with named fields
Student = Struct.new(:name, :id, :gpa)

# Create instances (records)
s1 = Student.new("Alice",  1001, 3.9)
s2 = Student.new("Bob",    1002, 3.4)
s3 = Student.new("Carol",  1003, 3.7)

puts s1.name  # => Alice
puts s1.gpa   # => 3.9

# Structs support iteration over fields
s1.each_pair { |field, val| puts "#{field}: #{val}" }
# name: Alice
# id: 1001
# gpa: 3.9

Key idea: Records map directly to objects with fixed attributes.

---

Memory Allocation

How does Ruby reserve space for data?

Stack Memory          Heap Memory
+------------+         +---------------------+
|  x = 5     | ------> |  Integer object: 5  |
|  s = "hi"  | ------> |  String object: "hi"|
|  arr = []  |-------> |  Array object: []   |
+------------+         +---------------------+
  Variables              Actual Objects
  (references)           (allocated data)

x   = 42          # stack holds reference; Fixnum on heap
str = "hello"     # stack ref → String object on heap
arr = [1, 2, 3]   # stack ref → Array object on heap

puts x.object_id    # unique heap address identifier
puts str.object_id
puts arr.object_id

In Ruby, almost everything lives on the heap. The stack holds references (pointers) to objects.

---

PART 2: Static vs Dynamic Structures

Static Memory Structures

Static structures have a fixed size determined at compile time or program start.

# Fixed-size array (static-style in concept)
DAYS_OF_WEEK = Array.new(7)   # allocated once, size = 7
DAYS_OF_WEEK[0] = "Monday"
DAYS_OF_WEEK[6] = "Sunday"

# Constants and fixed tables are classic static structures
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].freeze

# .freeze prevents modification — enforces static behavior
# PRIMES << 31  # => RuntimeError: can't modify frozen Array

Characteristics of static structures:

• Size is fixed
• Memory is predictable and fast to access
• No overhead from memory management
• Waste space if not fully used

---

Dynamic Structures – Heap Allocation

Dynamic structures grow and shrink at runtime on the heap.

# Ruby Array is fully dynamic
list = []               # starts empty

10.times { |i| list << i * 2 }   # grows automatically
puts list.inspect
# => [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

list.delete_if { |x| x > 10 }    # shrinks automatically
puts list.inspect
# => [0, 2, 4, 6, 8, 10]

# Hash also grows dynamically
inventory = {}
inventory["apples"]  = 42
inventory["bananas"] = 17
inventory["mangoes"] = 5
puts inventory

Heap allocation means Ruby requests memory from the OS as needed and releases it when objects are no longer reachable.

---

Garbage Collection and Recycling

Ruby uses automatic garbage collection (GC) — you never call free().

# When an object loses all references, it becomes garbage
def create_garbage
  temp = "I am temporary"   # allocated on heap
  arr  = [1, 2, 3, 4, 5]   # allocated on heap
  # temp and arr go out of scope here → eligible for GC
end

create_garbage   # after this call, those objects are garbage

# Ruby uses a tri-color mark-and-sweep + generational GC
GC.start         # manually trigger (rarely needed)
puts GC.stat[:heap_live_slots]   # objects currently alive

How GC works: 1. Mark — trace all reachable objects from root references 2. Sweep — reclaim memory of unmarked (unreachable) objects 3. Compact (Ruby 3+) — defragment heap for better locality

---

PART 3: Linked Lists

Singly Linked Lists

Each node stores data + a pointer to the next node only.

class Node
  attr_accessor :data, :next_node
  def initialize(data)
    @data      = data
    @next_node = nil
  end
end

class SinglyLinkedList
  def initialize
    @head = nil
  end

  def prepend(data)
    node      = Node.new(data)
    node.next_node = @head
    @head     = node
  end

  def to_s
    result, cur = [], @head
    while cur
      result << cur.data
      cur = cur.next_node
    end
    result.join(" -> ") + " -> nil"
  end
end

list = SinglyLinkedList.new
[3, 2, 1].each { |v| list.prepend(v) }
puts list   # => 1 -> 2 -> 3 -> nil

---

Doubly Linked Lists

Each node has pointers to both next and previous nodes.

class DNode
  attr_accessor :data, :prev, :next_node
  def initialize(data)
    @data = data; @prev = nil; @next_node = nil
  end
end

class DoublyLinkedList
  def initialize
    @head = @tail = nil
  end

  def append(data)
    node = DNode.new(data)
    if @tail
      @tail.next_node = node
      node.prev       = @tail
    else
      @head = node
    end
    @tail = node
  end

  def traverse_backward
    cur = @tail
    while cur
      print "#{cur.data} "
      cur = cur.prev
    end
    puts
  end
end

dll = DoublyLinkedList.new
[10, 20, 30].each { |v| dll.append(v) }
dll.traverse_backward   # => 30 20 10

---

Linked List Operations

Insertion, Deletion, Traversal — the three core operations:

# INSERTION at position
def insert_after(target_data, new_data)
  cur = @head
  while cur
    if cur.data == target_data
      node           = Node.new(new_data)
      node.next_node = cur.next_node
      cur.next_node  = node
      return
    end
    cur = cur.next_node
  end
end

# DELETION by value  O(n)
def delete(data)
  return if @head.nil?
  if @head.data == data
    @head = @head.next_node; return
  end
  cur = @head
  while cur.next_node
    if cur.next_node.data == data
      cur.next_node = cur.next_node.next_node; return
    end
    cur = cur.next_node
  end
end

# TRAVERSAL  O(n)
def traverse
  cur = @head
  while cur
    print "#{cur.data} "
    cur = cur.next_node
  end
end

---

Arrays vs Hashes

# ARRAY — ordered, integer-indexed  O(1) access by index
fruits = ["apple", "banana", "cherry"]
puts fruits[0]          # => apple  (O(1))
puts fruits.length      # => 3
fruits.push("date")     # append   O(1) amortized

# HASH — key-value pairs, O(1) average lookup
ages = { "Alice" => 30, "Bob" => 25, "Carol" => 28 }
puts ages["Alice"]      # => 30   (O(1) avg)
ages["Dave"] = 22
ages.each { |name, age| puts "#{name} is #{age}" }

Feature	Array	Hash
Index type	Integer (0-based)	Any object
Access time	O(1) by index	O(1) avg by key
Order	Maintained	Maintained (Ruby 1.9+)
Use case	Sequences	Lookup tables / maps
Memory	Compact	Higher overhead

---

PART 4: Sorting Algorithms

Bubble Sort

Repeatedly swaps adjacent out-of-order elements. O(n²) — simple but slow.

def bubble_sort(arr)
  n = arr.length
  loop do
    swapped = false
    (n - 1).times do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]   # swap
        swapped = true
      end
    end
    break unless swapped   # early exit if already sorted
  end
  arr
end

data = [64, 34, 25, 12, 22, 11, 90]
puts bubble_sort(data).inspect
# => [11, 12, 22, 25, 34, 64, 90]

Complexity: Time O(n²) best/worst | Space O(1)

---

Insertion Sort

Builds the sorted array one element at a time. O(n²) worst, O(n) best (nearly sorted).

def insertion_sort(arr)
  (1...arr.length).each do |i|
    key = arr[i]
    j   = i - 1
    while j >= 0 && arr[j] > key
      arr[j + 1] = arr[j]   # shift right
      j -= 1
    end
    arr[j + 1] = key          # insert
  end
  arr
end

data = [12, 11, 13, 5, 6]
puts insertion_sort(data).inspect
# => [5, 6, 11, 12, 13]

Best for: Small datasets or nearly sorted data.

Complexity: Time O(n²) worst | O(n) best | Space O(1)

---

Merge Sort

Divide-and-conquer. Split in half, sort each half, merge. O(n log n) guaranteed.

def merge_sort(arr)
  return arr if arr.length <= 1

  mid   = arr.length / 2
  left  = merge_sort(arr[0...mid])
  right = merge_sort(arr[mid..])

  merge(left, right)
end

def merge(left, right)
  result = []
  until left.empty? || right.empty?
    if left.first <= right.first
      result << left.shift
    else
      result << right.shift
    end
  end
  result + left + right
end

data = [38, 27, 43, 3, 9, 82, 10]
puts merge_sort(data).inspect
# => [3, 9, 10, 27, 38, 43, 82]

---

Quick Sort

Pick a pivot, partition around it, recurse. O(n log n) average, O(n²) worst.

def quicksort(arr)
  return arr if arr.length <= 1

  pivot = arr[arr.length / 2]         # choose middle as pivot
  left  = arr.select { |x| x < pivot }
  mid   = arr.select { |x| x == pivot }
  right = arr.select { |x| x > pivot }

  quicksort(left) + mid + quicksort(right)
end

data = [3, 6, 8, 10, 1, 2, 1]
puts quicksort(data).inspect
# => [1, 1, 2, 3, 6, 8, 10]

Algorithm	Best	Average	Worst	Space
Bubble	O(n)	O(n²)	O(n²)	O(1)
Insertion	O(n)	O(n²)	O(n²)	O(1)
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)

---

PART 5: Stacks

Stacks – LIFO Structure

A stack is Last-In, First-Out. Think: stack of plates.

class Stack
  def initialize
    @data = []
  end

  def push(item)  = @data.push(item)
  def pop         = @data.pop
  def peek        = @data.last
  def empty?      = @data.empty?
  def size        = @data.size
  def to_s        = @data.inspect
end

s = Stack.new
s.push(10); s.push(20); s.push(30)
puts s          # => [10, 20, 30]
puts s.peek     # => 30  (top, not removed)
puts s.pop      # => 30  (removed)
puts s          # => [10, 20]

Use cases: Order reversal, undo operations, function call frames, expression evaluation.

---

Stacks – Order Reversal & Functions

Stacks reverse order and manage function call frames:

# Order reversal using a stack
def reverse_string(str)
  stack = Stack.new
  str.each_char { |c| stack.push(c) }
  result = ""
  result += stack.pop until stack.empty?
  result
end
puts reverse_string("hello")  # => "olleh"

# How the call stack works during function calls:
# Each call pushes a "frame" with local vars + return address
def factorial(n)          # frame pushed
  return 1 if n <= 1
  n * factorial(n - 1)    # new frame pushed recursively
end                       # frame popped on return

puts factorial(5)   # => 120
# Call stack at deepest point:
# [factorial(1), factorial(2), factorial(3), factorial(4), factorial(5)]

---

Recursion

Recursion uses the call stack implicitly — each call adds a new stack frame.

# Every recursive solution needs:
# 1. BASE CASE  — stops recursion
# 2. RECURSIVE CASE — moves toward base case

# Fibonacci with recursion
def fib(n)
  return n if n <= 1          # base case
  fib(n - 1) + fib(n - 2)    # recursive case
end

puts (0..7).map { |i| fib(i) }.inspect
# => [0, 1, 1, 2, 3, 5, 8, 13]

# Tower of Hanoi — classic recursion example
def hanoi(n, from, to, via)
  if n == 1
    puts "Move disk 1: #{from} → #{to}"
    return
  end
  hanoi(n - 1, from, via, to)
  puts "Move disk #{n}: #{from} → #{to}"
  hanoi(n - 1, via, to, from)
end

hanoi(3, "A", "C", "B")

---

PART 6: Queues

Queues – FIFO Structure

A queue is First-In, First-Out. Think: checkout line.

class Queue
  def initialize
    @data = []
  end

  def enqueue(item) = @data.push(item)      # add to back
  def dequeue       = @data.shift           # remove from front
  def front         = @data.first
  def empty?        = @data.empty?
  def size          = @data.size
  def to_s          = @data.inspect
end

q = Queue.new
q.enqueue("Alice"); q.enqueue("Bob"); q.enqueue("Carol")
puts q            # => ["Alice", "Bob", "Carol"]
puts q.dequeue    # => "Alice"
puts q            # => ["Bob", "Carol"]

Use cases: Task scheduling, BFS traversal, print spoolers, buffering.

---

Circular Queue

A circular queue reuses empty slots by wrapping the tail pointer around.

class CircularQueue
  def initialize(capacity)
    @cap   = capacity
    @data  = Array.new(capacity)
    @head  = 0
    @tail  = 0
    @size  = 0
  end

  def enqueue(item)
    raise "Queue full" if @size == @cap
    @data[@tail] = item
    @tail = (@tail + 1) % @cap   # wrap around!
    @size += 1
  end

  def dequeue
    raise "Queue empty" if @size == 0
    item  = @data[@head]
    @head = (@head + 1) % @cap   # wrap around!
    @size -= 1
    item
  end
end

cq = CircularQueue.new(3)
cq.enqueue(1); cq.enqueue(2); cq.enqueue(3)
puts cq.dequeue   # => 1
cq.enqueue(4)     # reuses slot 0

---

Priority Queue

Elements are dequeued in priority order, not arrival order.

class PriorityQueue
  def initialize
    @data = []   # store [priority, item] pairs
  end

  def enqueue(item, priority)
    @data << [priority, item]
    @data.sort_by! { |p, _| -p }  # highest priority first
  end

  def dequeue
    @data.shift&.last
  end

  def peek
    @data.first&.last
  end
end

pq = PriorityQueue.new
pq.enqueue("low task",      1)
pq.enqueue("critical task", 10)
pq.enqueue("normal task",   5)

puts pq.dequeue   # => "critical task"   (priority 10)
puts pq.dequeue   # => "normal task"     (priority 5)
puts pq.dequeue   # => "low task"        (priority 1)

---

PART 7: Trees

Binary Trees

A binary tree has nodes with at most two children (left and right).

class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val)
    @val = val; @left = nil; @right = nil
  end
end

# Build a Binary Search Tree (BST)
class BST
  def insert(root, val)
    return TreeNode.new(val) if root.nil?
    if val < root.val
      root.left  = insert(root.left,  val)
    else
      root.right = insert(root.right, val)
    end
    root
  end

  def inorder(root)   # Left → Root → Right (sorted output)
    return if root.nil?
    inorder(root.left)
    print "#{root.val} "
    inorder(root.right)
  end
end

bst  = BST.new
root = nil
[5, 3, 7, 1, 4, 6, 8].each { |v| root = bst.insert(root, v) }
bst.inorder(root)   # => 1 3 4 5 6 7 8

---

Math Expression Tree

Expression trees represent mathematical expressions structurally.

class ExprNode
  attr_accessor :val, :left, :right
  def initialize(val, left = nil, right = nil)
    @val = val; @left = left; @right = right
  end
end

# Tree for: (3 + 4) * (5 - 2)
#        *
#       / \
#      +   -
#     / \ / \
#    3  4 5  2

tree = ExprNode.new("*",
         ExprNode.new("+", ExprNode.new(3), ExprNode.new(4)),
         ExprNode.new("-", ExprNode.new(5), ExprNode.new(2)))

def evaluate(node)
  return node.val if node.left.nil?   # leaf = number
  l = evaluate(node.left)
  r = evaluate(node.right)
  case node.val
  when "+" then l + r
  when "-" then l - r
  when "*" then l * r
  when "/" then l / r.to_f
  end
end

puts evaluate(tree)   # => 21  [ (3+4)*(5-2) = 7*3 ]

---

B+ Trees

B+ Trees are balanced multi-way trees used in databases and file systems.

Structure of a B+ Tree (order 3):

Internal nodes: [ 10 | 20 ]
               /     |      \
         [5|7]    [12|17]   [22|30]
          ↓          ↓          ↓
       Leaf nodes (linked) → faster range queries

Key properties:
  • All data lives in LEAF nodes
  • Internal nodes are index-only
  • Leaf nodes are linked (→) for range scans
  • Guaranteed O(log n) search, insert, delete

# Conceptual B+ Tree search in Ruby
class BPlusNode
  attr_accessor :keys, :children, :is_leaf, :next_leaf
  def initialize(is_leaf = false)
    @keys = []; @children = []; @is_leaf = is_leaf
    @next_leaf = nil
  end
end

# B+ Trees are used in: MySQL InnoDB, PostgreSQL indexes,
# file systems (NTFS, ext4), and many NoSQL stores.
puts "B+ Tree ensures O(log n) operations regardless of size"

---

PART 8: Graphs

Graphs – Mazes

A graph is a set of nodes (vertices) connected by edges. Mazes are graphs!

# Represent a maze as an adjacency list
maze = {
  "start" => ["A", "B"],
  "A"     => ["C"],
  "B"     => ["C", "D"],
  "C"     => ["end"],
  "D"     => ["end"],
  "end"   => []
}

# BFS to find shortest path through maze
def bfs(graph, start, goal)
  queue   = [[start, [start]]]
  visited = {}
  until queue.empty?
    node, path = queue.shift
    return path if node == goal
    next if visited[node]
    visited[node] = true
    graph[node].each { |n| queue << [n, path + [n]] }
  end
  nil
end

path = bfs(maze, "start", "end")
puts path.join(" → ")   # => start → A → C → end

---

Transition Matrix (Adjacency Matrix)

A transition matrix represents graph edges as a 2D grid.

# Graph:  A→B, A→C, B→C, C→D
#         0=A, 1=B, 2=C, 3=D
matrix = [
  [0, 1, 1, 0],   # A connects to B, C
  [0, 0, 1, 0],   # B connects to C
  [0, 0, 0, 1],   # C connects to D
  [0, 0, 0, 0]    # D: no outgoing edges
]

LABELS = %w[A B C D]

# Print adjacency
matrix.each_with_index do |row, i|
  row.each_with_index do |val, j|
    puts "#{LABELS[i]} → #{LABELS[j]}" if val == 1
  end
end

# Check if path A→C exists: matrix[0][2]
puts "A→C edge exists? #{matrix[0][2] == 1}"   # => true
# Check if path B→A exists: matrix[1][0]
puts "B→A edge exists? #{matrix[1][0] == 1}"   # => false

---

Dijkstra’s Algorithm

Finds the shortest path in a weighted graph with non-negative weights.

def dijkstra(graph, start)
  dist    = Hash.new(Float::INFINITY)
  dist[start] = 0
  visited = {}
  pq      = [[0, start]]   # [cost, node]

  until pq.empty?
    cost, node = pq.min_by { |c, _| c }
    pq.delete([cost, node])
    next if visited[node]
    visited[node] = true

    (graph[node] || []).each do |neighbor, weight|
      new_cost = cost + weight
      if new_cost < dist[neighbor]
        dist[neighbor] = new_cost
        pq << [new_cost, neighbor]
      end
    end
  end
  dist
end

graph = {
  "A" => [["B", 1], ["C", 4]],
  "B" => [["C", 2], ["D", 5]],
  "C" => [["D", 1]],
  "D" => []
}
puts dijkstra(graph, "A").inspect
# => {"A"=>0, "B"=>1, "C"=>3, "D"=>4}

---

Flow Analysis (Max-Flow)

Flow networks model capacity-constrained systems (networks, pipelines, traffic).

# Ford-Fulkerson Max-Flow (BFS-based Edmonds-Karp)
def bfs_path(capacity, source, sink, parent)
  visited = { source => true }
  queue   = [source]
  until queue.empty?
    u = queue.shift
    capacity[u]&.each do |v, cap|
      if !visited[v] && cap > 0
        visited[v] = true
        parent[v]  = u
        return true if v == sink
        queue << v
      end
    end
  end
  false
end

# Key concepts for flow analysis:
# • Source node (supply) → Sink node (demand)
# • Each edge has a capacity constraint
# • Max-Flow = Min-Cut (Ford-Fulkerson theorem)
# • Applications: network routing, matching, scheduling

puts "Max-Flow applications:"
puts "  • Internet traffic routing"
puts "  • Supply chain optimization"
puts "  • Bipartite matching (job assignments)"
puts "  • Image segmentation"

---

EXAM SUMMARY

Quick Reference – Complexity Cheat Sheet

Structure / Algorithm	Access	Search	Insert	Delete	Space
Array (static)	O(1)	O(n)	O(n)	O(n)	O(n)
Hash / Dictionary	O(1)	O(1)	O(1)	O(1)	O(n)
Singly Linked List	O(n)	O(n)	O(1)†	O(1)†	O(n)
Doubly Linked List	O(n)	O(n)	O(1)†	O(1)†	O(n)
Stack (push/pop)	O(n)	O(n)	O(1)	O(1)	O(n)
Queue (enq/deq)	O(n)	O(n)	O(1)	O(1)	O(n)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
B+ Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Bubble Sort	—	—	—	—	O(1) worst O(n²)
Merge Sort	—	—	—	—	O(n) always O(n log n)
Quick Sort	—	—	—	—	O(log n) avg O(n log n)

† With direct reference to node

---

Key Concepts to Remember

Memory: - Stack = references/primitives | Heap = objects - GC marks reachable objects, sweeps the rest

Lists: Singly (forward only) vs Doubly (forward + backward)

Trees: - BST: left < root < right → inorder gives sorted output - B+ Tree: all data in leaves, leaves linked for range queries - Expression Tree: post-order traversal = evaluate

Graphs: - Adjacency List: sparse graphs (less memory) - Adjacency Matrix: dense graphs (O(1) edge lookup) - Dijkstra: greedy shortest path (non-negative weights only)

Stacks: LIFO → reversal, recursion, function calls

Queues: FIFO → BFS, scheduling | Circular → reuse space | Priority → ordered service

Good luck on your final exam!