What this module covers: Every structure so far in this course has been array-backed — one contiguous block of memory (Module F-2). A linked list breaks that assumption: each element is its own independently allocated node, connected by pointers rather than physical adjacency. This module covers singly and doubly linked lists, why insertion/deletion trade places with arrays on cost, reversal, and the cycle-detection technique previewed in Module F-8, now applied directly.
Where an array is one block with elements at predictable offsets, a linked list is a chain of individually allocated nodes, each holding a value and a pointer to the next node:
// 1 -> 2 -> 3 -> null const third = new ListNode(3); const second = new ListNode(2); second.next = third; const head = new ListNode(1); head.next = second;
There is no address = base + i × size arithmetic here (Module F-2) — to reach the third node, you have to follow head.next.next, visiting each node in between. That's the fundamental trade: array indexing is O(1); linked list indexing (or "get the k-th element") is O(n).
Analogy: An array is the apartment building from Module F-2 — walk straight to unit 47. A linked list is a treasure hunt where each clue only reveals the location of the next clue — you cannot skip to clue 47 without having followed clues 1 through 46 first.
The trade runs the other way for insertion and deletion at a known position. Inserting into the middle of an array means shifting every subsequent element (Module F-2); inserting into a linked list is just pointer reassignment — no other node moves at all:
function insertAfter<T>(node: ListNode<T>, value: T): void { const newNode = new ListNode(value); newNode.next = node.next; node.next = newNode; // O(1) — no other node in the entire list was touched or moved }
This is genuinely O(1), regardless of how long the list is — a real, meaningful advantage over an array's O(n) middle-insertion cost, provided you already have a reference to the node you're inserting after. Finding that node in the first place is still O(n) if you don't already have a pointer to it, which is the honest caveat behind "linked lists have O(1) insertion" — it's O(1) insertion at a known point, not O(1) insertion at an arbitrary position you still have to search for.
A singly linked list (above) only points forward — from a given node, you can reach the next one, but not the previous one. A doubly linked list adds a prev pointer too:
The extra pointer costs a small amount of memory per node, but it buys something a singly linked list can't do cheaply: deleting a node in O(1), given only a reference to that node — no need to separately track or search for its predecessor, because the node already knows who it is:
function deleteNode<T>(node: DoublyListNode<T>): void { if (node.prev) node.prev.next = node.next; if (node.next) node.next.prev = node.prev; // O(1) — both neighbors are reachable directly from `node`, no search needed }
In a singly linked list, deleting a given node requires first finding its predecessor by traversing from the head — O(n) — specifically because there's no prev pointer to jump backward through. This exact capability — O(1) deletion of an arbitrary known node — is the reason Module P-3's LRU Cache is built on a doubly linked list, not a singly linked one.
Reversal is the linked-list equivalent of Module F-2's array reversal, but the mechanism is entirely different — instead of swapping values in place, you re-point every next pointer to face the other direction:
function reverseList<T>(head: ListNode<T> | null): ListNode<T> | null { let prev: ListNode<T> | null = null; let curr = head;
while (curr !== null) { const nextTemp = curr.next; // save the next node before we overwrite curr.next curr.next = prev; // reverse this node's pointer prev = curr; // advance prev curr = nextTemp; // advance curr to the node we saved }
return prev; // prev is now the new head }
Each node's next pointer is flipped exactly once, so this is O(n) time, O(1) extra space — no new nodes allocated, just pointers redirected in place, one pass. This same "three-pointer shuffle" (prev, curr, nextTemp) is the standard shape for a large fraction of linked list problems: whenever you need to modify pointers as you walk the list, you generally need a reference to where you came from, where you are, and where you're going next — because once you overwrite curr.next, the original "next" is gone unless you saved it first.
Module F-8 previewed Floyd's fast/slow pointer technique in the abstract. Here it is applied directly to a linked list:
function hasCycle<T>(head: ListNode<T> | null): boolean { let slow = head; let fast = head;
while (fast !== null && fast.next !== null) { slow = slow!.next; fast = fast.next.next; // moves twice as fast as slow
if (slow === fast) return true; // they've met — there's a cycle }
return false; // fast reached the end — no cycle }
If the list has no cycle, fast reaches null and the loop ends cleanly. If there is a cycle, fast and slow are both trapped inside it, and because fast gains one extra step on slow every iteration, it's guaranteed to eventually land on the exact same node as slow — they can't pass each other without colliding, the same way a faster runner on a looping track eventually laps a slower one. This runs in O(n) time and, notably, O(1) space — no Set of visited nodes required (which would also solve the problem, in O(n) space, using the hash-based "have I seen this?" pattern from Module F-4 instead).
A pattern that reappears directly in Module P-9 (Merge Sort): given two already-sorted linked lists, merge them into one sorted list by repeatedly taking whichever head is smaller.
function mergeSorted(a: ListNode<number> | null, b: ListNode<number> | null): ListNode<number> | null { const dummy = new ListNode(0); // placeholder — makes edge cases at the head disappear let tail = dummy;
while (a !== null && b !== null) { if (a.value <= b.value) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; }
tail.next = a !== null ? a : b; // attach whatever's left of the non-exhausted list return dummy.next; }
This is O(n + m) — every node from both lists is visited exactly once — and O(1) extra space, since it reassigns existing nodes' pointers rather than creating new ones. The dummy node is a small, common trick worth naming: it sidesteps a special case for "what's the head when the merged list is empty so far," letting the loop body treat every iteration identically.
The DOM is a tree of nodes connected by pointers, not an array — parentNode, childNodes, nextSibling, previousSibling are exactly the next/prev relationships from this module, just branching into a tree instead of a single chain (Module P-4 covers tree structure in full).
Blockchain transaction chains: each block holds a reference to the previous block's hash — a singly linked list where "next" points backward in time instead of forward, and where reversing the direction of traversal (walking from genesis block forward) requires exactly this module's insight about which pointer direction you actually have.
LRU cache eviction (Module P-3, immediately next): the O(1)-deletion-of-a-known-node property from the doubly linked list section above is the entire reason that structure is chosen over a singly linked list or a plain array for this specific job.
Why JavaScript code rarely hand-rolls linked lists for everyday use: modern CPUs are extremely fast at scanning contiguous memory (better cache locality) — an array's O(n) linear scan is often faster in practice than a linked list's O(n) pointer-chasing traversal, because each node in a linked list can live anywhere in memory, causing cache misses an array wouldn't. Linked lists earn their keep specifically when O(1) insertion/deletion at known points matters more than raw scan speed — which is a real but narrower set of cases than "generic list of things," where a plain array usually wins.
A linked list is a chain of independently allocated nodes connected by pointers, not one contiguous block — the opposite memory model from the array in Module F-2.
Indexing is O(n) (no arithmetic shortcut to the k-th node) but insertion/deletion at a known node is O(1) — no other node needs to shift, unlike an array.
Doubly linked lists add a prev pointer, enabling O(1) deletion of an arbitrary known node without first searching for its predecessor — the property Module P-3's LRU Cache depends on directly.
Reversal is a three-pointer shuffle (prev, curr, nextTemp) that flips every next pointer in one O(n) pass, O(1) extra space.
Cycle detection via fast/slow pointers (Module F-8, applied concretely here) finds a cycle in O(n) time and O(1) space, without needing a Set of visited nodes.
Arrays still usually win in practice for plain JavaScript code, because of cache locality — linked lists earn their place specifically when O(1) insert/delete at a known point is the dominant concern.
The next module, The LRU Cache: Hash Map + Doubly Linked List for O(1) Access, combines this module's doubly linked list directly with Module F-4's hash map to build the exact structure behind Redis-style cache eviction.
Knowledge Check
Why is insertAfter genuinely O(1), while finding the node to insert after (if you don't already have a reference to it) is O(n)?
Why can a doubly linked list delete an arbitrary node in O(1) given just a reference to that node, while a singly linked list cannot do the same without additional work?
In hasCycle, why is it guaranteed that slow and fast will eventually point to the exact same node if the list contains a cycle, rather than the two pointers simply passing each other forever without ever meeting?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Written by Jatin Jain Saraf · Architect of SupraScan