Study

Data Structures & Algorithms

DSA I as small systems you can inspect.

This page only covers the material present in my DSA I notes: Java review, iterator/comparator basics, Big-O, ArrayLists, recursion and binary search, linked lists, stacks, and queues.

  • Worst-case Big-O and primitive operation counting
  • Arrays, ArrayLists, backing arrays, shifting, and resize costs
  • Recursive base cases, stack traces, and binary search
  • Singly, doubly, and circular linked list update rules
  • Stack and queue ADTs with linked and array-backed implementations

learning map

  1. Module 0 · Foundations

    Foundations and Java review

    The notes start by translating Java syntax, generics, wrapper types, Iterable, Iterator, Comparable, and Comparator into concepts familiar from JS/TS.

  2. Module 0 · Big-O

    Big-O and primitive operations

    Big-O is treated as the tightest reasonable upper bound for worst-case growth, after dropping constants and lower-order terms.

  3. Module 1

    Arrays, ArrayLists, recursion

    ArrayLists use a backing array, shift elements for middle insert/remove, and resize by copying into a larger array. Recursion needs a base case and progress toward it.

  4. Module 2

    Linked lists

    Linked lists trade random access for pointer updates. The notes compare SLL, DLL, and CLL edge cases and operation costs.

  5. Module 3

    Stacks and queues

    Stacks restrict work to one end. Queues add at the back and remove at the front. ArrayQueue uses a circular array and unwraps on resize.

visual lab

Big-O growth

Line shape shows growth; the cursor reads the selected input size.

48163264128opsn
O(1)

1

O(log n)

5

O(n)

32

O(n log n)

160

O(n²)

1,024

ArrayList backing array

Pick an operation, then apply it to watch positions change.

index 0keepA
index 1keepB
index 2keepC
index 3keepD
index 4empty
index 5empty

Call stack

Call factorial(4); it must wait.

1/9
callfactorial(4)

Binary search

Target: 19. 19 > 13, eliminate the left half through mid.

1/3
0low2
1window5
2window8
3mid13
4window19
5window21
6high34

1. low 0, mid 3, high 6: 19 > 13, eliminate the left half through mid.

Stack / Queue ADTs

Stack changes happen at one top end; queue changes enter at back and leave from front.

Stack / LIFO

heldA
heldB
topC

Queue / FIFO

frontA
waitB
backC

concept notes

ArrayList resize

When the backing array is full, the implementation creates a larger array and copies existing elements before adding new data.

Module 1 · ArrayLists

Recursion trace

Each recursive call waits on a smaller call until the base case returns, then results unwind back up the call stack.

Module 1 · Recursion

Circular queue

ArrayQueue keeps a front index. Enqueue lands at (front + size) % capacity; dequeue advances front by one modulo capacity.

Module 3 · Stacks & Queues

test yourself

Module 0 · Foundations

Foundations and Java review

What does an enhanced for loop use under the hood?

An Iterator — hasNext() / next(). Implementing Iterable is what lets a type work with it.

Comparable vs Comparator?

Comparable defines the natural order of a type (compareTo); Comparator is an external, swappable ordering rule.

Module 0 · Big-O

Big-O and primitive operations

What exactly does Big-O capture here?

The tightest reasonable upper bound on worst-case growth, after dropping constants and lower-order terms.

If two algorithms are both O(n), are they equally fast?

Not necessarily — constants and lower-order terms are dropped from Big-O but can still matter in practice.

Module 1

Arrays, ArrayLists, recursion

Why is ArrayList addToBack amortized O(1) but addAtIndex O(n)?

addToBack only resizes occasionally; addAtIndex must shift every later element one slot to the right.

What must every recursion have, and how does binary search use it?

A base case plus progress toward it. Binary search halves the search window each step until it is empty.

Module 2

Linked lists

Why is removeFromBack O(n) for an SLL but O(1) for a DLL?

An SLL must walk from head to find the new tail; a DLL reads tail.prev directly.

How can a circular linked list add to both ends in O(1)?

Keep one pointer to the head and use a data-swap trick so the front and back are both reachable in O(1).

Module 3

Stacks and queues

Stack vs queue ordering?

Stack is LIFO and works at one end; queue is FIFO — add at the back, remove from the front.

Where does an ArrayQueue enqueue land?

At index (front + size) % capacity — a circular array that unwraps into a larger one on resize.