Singly Linked List

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.

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Reversing a singly linked list is a four-line iteration with three pointers (`prev`, `curr`, `next`), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no random access: every operation has to be expressed as careful, ordered pointer rewrites, and one missed assignment loses the rest of the list forever. **Linked List Algorithms** is the lesson where pointer manipulation becomes a reliable skill. You will reverse a list iteratively and recursively, then extend the technique to reverse in groups of `k`. You will use Floyd's fast and slow pointers to detect cycles, find the cycle start, locate the middle element, and check whether a list is a palindrome. You will merge two sorted lists, then merge `k` sorted lists with a min-heap. The lesson also covers removing the nth node from the end, finding the intersection of two lists, deep-copying a list with random pointers, and the dummy-node trick that eliminates head-edge cases entirely. In **Linked Lists (Singly)**, you saw how nodes and `next` pointers form a list and why insertion at a known position is `O(1)`. **Two Pointers (Intro)** introduced fast and slow indices on arrays; this lesson reuses the same idea on pointer-linked nodes. Next, **Tree Algorithms** generalizes pointer-and-recursion thinking to branching structures.