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 and Java review

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

/ Enhanced for loops use iterators
/ Comparable owns natural order
/ Comparator is an external ordering rule

Module 0

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.

/ Count primitive operations
/ Use the tightest bound
/ Constants can still matter in practice

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.

/ addToBack is amortized O(1)
/ addAtIndex shifts right
/ Binary search halves the window

Module 2

Linked lists

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

/ SLL removeFromBack is O(n)
/ DLL tail.prev makes back removal O(1)
/ CLL can add to both ends with a data swap trick

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.

/ Stack is LIFO
/ Queue is FIFO
/ ArrayQueue enqueue index is (front + size) % capacity

visual lab

Big-O growth

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

log scale

Input size: 32

O(1)

O(log n)

O(n)

O(n log n)

160

O(n²)

1,024

ArrayList backing array

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

Operation

Index: 2

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.

1/9

call factorial(4)

Binary search

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

1/3

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

source-backed notes

ArrayList resize

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

m1-arrays-and-arraylists.md

Recursion trace

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

m1-recursion.md + refs/m1-recursion-summary.md

Circular queue

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

m3-stacks-and-queues.md

Managed as a curated projection, not a second notebook.

/Add new topics only after they exist in the 3B study notes.
/Run pnpm study:check before shipping study-page changes.
/When hashes drift, review the source notes and update the public model deliberately.

15 source files

_index.md 73d4f27c

m0-java-review.md f27c8973

m0-iterable-comparable.md b2821863

m0-big-o-concepts.md 90226695

m1-arrays-and-arraylists.md bfdeb22d

m1-recursion.md f7f47484

m2-linked-lists.md 10e2ac72

m3-stacks-and-queues.md 7ac6c8ec

refs/m0-analysis-of-algorithms-summary.md e5177c16

refs/m0-iterators-summary.md d3af23e0

refs/m1-arrays-arraylist-summary.md c69c36c0

refs/m1-recursion-summary.md 716d4a7b

refs/m2-iterators-summary.md f20d6a73

refs/m2-linked-list-variations-summary.md 1ce8d2a3

refs/m2-singly-linked-lists-summary.md 8b70103d