Space Complexity

Why does a deeply recursive function crash with a stack overflow while an equivalent loop happily processes a million elements? Why does passing an array into a function sometimes mutate the caller's data and sometimes not? The answers all live one level below your code, in the runtime **memory model** that decides where every variable, object, and function call physically lives. This lesson opens up that model. You will see the difference between the **stack** (small, fast, organized into per-call frames) and the **heap** (larger, manually or garbage-collected, where objects and arrays actually live), watch how every function call pushes a stack frame and every `return` pops one, and trace how recursion stacks frames on top of frames until the base case unwinds them. You will also meet references and pointers conceptually, learn what triggers a stack overflow, and get a working mental model of garbage collection and memory leaks. This lesson builds on **Space Complexity Fundamentals**, where you learned to count auxiliary versus total space and saw why some algorithms claim `O(1)` space while others need `O(n)`. Memory Models gives you the underlying picture: those `O(...)` numbers describe stack frames, heap allocations, and reference graphs that you can now visualize concretely. Next, you will pivot to the mathematical side of the foundations track with **Discrete Mathematics Basics**, picking up the sets, relations, and logic vocabulary that algorithm analysis depends on.

An algorithm that runs in `O(n)` time but allocates a fresh array of size `n^2` will not fit in memory long before it would have finished computing. Memory is finite, and many algorithms quietly trade it for speed; the only way to make that trade-off visible is to analyze space the same way you analyze time. **Space Complexity Fundamentals** extends the Big-O lens from operation counting to memory usage. You will see why we draw a line between auxiliary space (the extra storage an algorithm allocates) and total space (auxiliary plus the input itself), and you will classify common algorithms as `O(1)` constant, `O(n)` linear, or `O(n^2)` quadratic in space. You will meet the in-place vs out-of-place distinction that interviewers love to probe, and you will study a first space-time trade-off where caching results turns repeated work into stored data. In **Big-O Notation (Upper Bound)**, you learned to read complexity classes from loop structure and to recognize that `O(c * n)` collapses to `O(n)`. The same vocabulary and the same simplification rules apply here, but the resource being counted is bytes of allocated memory rather than units of work. Once you can reason about both axes at once, you will be ready for **Logarithms & Exponentiation**, where you will build the mathematical intuition behind `O(log n)`, the complexity class that powers binary search, balanced trees, and most efficient divide-and-conquer algorithms.

An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A **Circular Linked List** encodes that shape directly, with the last node's `next` pointer wired to the head instead of `null`. This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for `null`), insertion at the head and at the tail in `O(1)` when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal. In **Linked Lists (Singly)**, traversal terminated when you reached a `null` next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later). With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

Inserting at the front of an array of one million items forces every existing element to slide one slot to the right. A **Linked List** sidesteps that copy entirely: a head insertion is two pointer assignments and nothing else, no matter how many nodes follow. In this lesson, each node holds a value and a `next` reference, and you chain those nodes into a singly linked list with explicit head and optional tail pointers. You will implement traversal, head and tail and middle insertion, deletion by value and by position, and linear search, and you will analyze each operation precisely so the trade-off against arrays becomes concrete: `O(1)` insertion at the head, `O(n)` access by index, and per-node memory overhead for the pointer. In **Arrays & Strings**, the `O(n)` cost of inserting near the front came from shifting; the linked list was invented to remove that shift. **Memory Models** introduced the difference between a contiguous block on the stack or heap and scattered allocations connected by references, and that mental model is exactly how a node-based structure lives in memory. Once you are comfortable manipulating `next` pointers, **Stack (LIFO)** uses a linked list (or a dynamic array) as its underlying storage and adds a strict push, pop, peek discipline on top.

The mathematical definition `factorial(n) = n * factorial(n - 1)` defines a function in terms of itself, with `factorial(0) = 1` as the stopping point. That two-line definition is also a complete program if your language lets a function call itself. Recursion is what turns self-referential definitions into runnable code, and many problems (tree traversal, graph search, divide and conquer, dynamic programming) describe themselves most naturally that way. **Recursion Fundamentals** breaks down how that machinery actually works. You will learn to identify a base case (when the recursion stops) and a recursive case (how the problem reduces to a smaller instance), trace the call stack as frames are pushed and popped, and reason about return values flowing back up the chain. Examples run through factorial, naive Fibonacci, sum of an array, and integer power, plus a first look at recursion-tree intuition, tail recursion, stack overflow, and the `O(depth)` space cost of deep recursion. In **How to Read Code (JS & Python)**, you saw functions call other functions. **Debugging by Tracing** taught you to follow those calls step by step. Recursion is the case where the function on the call stack is the same function, again and again, with smaller inputs each time. Next, **Backtracking (Intro)** extends recursion with an explicit undo step to systematically explore combinatorial search spaces.