Big-O growth
Line shape shows growth; the cursor reads the selected input size.
O(1)
1
O(log n)
5
O(n)
32
O(n log n)
160
O(n²)
1,024
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
-
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.
-
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.
-
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.
-
Module 2
Linked lists
Linked lists trade random access for pointer updates. The notes compare SLL, DLL, and CLL edge cases and operation costs.
-
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
ArrayList backing array
Pick an operation, then apply it to watch positions change.
index 0 keep A
index 1 keep B
index 2 keep C
index 3 keep D
index 4 empty
index 5 empty
Call stack
Call factorial(4); it must wait.
call factorial(4)
Binary search
Target: 19. 19 > 13, eliminate the left half through mid.
0 low 2
1 window 5
2 window 8
3 mid 13
4 window 19
5 window 21
6 high 34
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
held A
held B
top C
Queue / FIFO
front A
wait B
back C
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.