S025 · Linked Lists — Singly, Doubly, When They Win

Module M03: Data Structures & Algorithms · Session 25 of 130 · Track: SW 🔗

What you'll be able to do after this session

• Explain Linked Lists to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S008 — Data Structures — list, tuple, dict, set (when to use what)

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Linked Lists explained visually (NeetCode) — nodes and pointers in 10 minutes.
• 🎥 Deep dive (30–60 min) · MIT 6.006 — Linked lists, dynamic arrays, amortization — the trade-off, formally.
• 🎥 Hands-on demo (10–20 min) · Reverse a linked list — every variant walkthrough (NeetCode) — the interview classic, done cleanly.
• 📖 Canonical article · Wikipedia — Linked list — singly, doubly, circular, all in one place.
• 📖 Book chapter / tutorial · Wikipedia — Doubly linked list — why one prev pointer changes everything.
• 📖 Engineering blog · Python docs — collections.deque — Python's production-ready doubly linked list.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Pointers made explicit.

If an array is a row of numbered mailboxes glued together, a linked list is more like a scavenger hunt: each note tells you where to find the next one. Each node carries a value and a pointer (memory address) to the next node. To find the 7th item, you have to start at the head and follow 6 pointers — no arithmetic shortcut.

That sounds strictly worse than an array. So why do linked lists exist? Because when you want to insert or delete in the middle, an array has to shift every element after that position (O(n)); a linked list just rewires two pointers (O(1)) — if you already have a pointer to the node. That "if" is the whole nuance.

A doubly linked list adds a prev pointer to each node so you can walk backwards. That's what powers collections.deque in Python, LRU cache eviction lists, and browser history.

One-sentence gotcha to carry forever: Linked lists are almost never the right choice in modern high-performance code — cache misses on every pointer chase make them dramatically slower than arrays for iteration, even when Big-O says they should be comparable. They win only when you need O(1) insert/delete at both ends (deque) or in the middle of a list you're already holding a pointer into (LRU cache).

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Worked example — inserting 25 between 20 and 30:

Before: 10 → 20 → 30 → 40. To insert 25 after 20:

1. Create new node N: value=25, next=None.
2. Set N.next = 20.next (which is 30). Now N points at 30.
3. Set 20.next = N.

Total: 3 pointer writes. No elements moved. In an array of 1 million elements, inserting at position 500,000 would shift 500,000 elements — a million pointer writes in a linked list still beats that.

Worked example — reverse a singly linked list (interview classic):

Iterative pattern with three pointers prev, curr, nxt:

prev=None  curr=[10]->[20]->[30]->None
                     ^curr

step 1: nxt = curr.next (=[20])
        curr.next = prev  (=None)   # flip pointer
        prev = curr; curr = nxt
        state:  None<-[10]   [20]->[30]->None
                             ^curr

step 2: [10]<-[20]   [30]->None
                     ^curr
step 3: [10]<-[20]<-[30]   None
                           ^curr (None) → done
return prev

Array vs Linked List — the honest comparison table:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# linked_list_playground.py
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt
 
# ---- 1. Build a linked list from a Python list ----
def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head
 
def show(head):
    parts = []
    while head:
        parts.append(str(head.value))
        head = head.next
    return " -> ".join(parts) + " -> NULL"
 
lst = build([10, 20, 30, 40])
print("original:", show(lst))
 
# ---- 2. Insert after a given value ----
def insert_after(head, target, new_value):
    curr = head
    while curr:
        if curr.value == target:
            curr.next = Node(new_value, curr.next)
            return
        curr = curr.next
 
insert_after(lst, 20, 25)
print("after insert 25 after 20:", show(lst))
 
# ---- 3. Reverse a singly linked list, iteratively ----
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev
 
rev = reverse(build([1,2,3,4,5]))
print("reversed:", show(rev))
 
# ---- 4. Detect a cycle (Floyd's tortoise & hare) ----
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
# make [1]->[2]->[3]->[4]->back to [2]
a, b, c, d = Node(1), Node(2), Node(3), Node(4)
a.next=b; b.next=c; c.next=d; d.next=b
print("has_cycle:", has_cycle(a))
 
# ---- 5. Practical: use collections.deque for O(1) both ends ----
from collections import deque
dq = deque([1,2,3])
dq.appendleft(0)      # O(1)
dq.append(4)          # O(1)
dq.popleft()          # O(1)
print("deque:", list(dq))

Checklist:

1. show(lst) prints 10 -> 20 -> 30 -> 40 -> NULL.
2. After insert, 10 -> 20 -> 25 -> 30 -> 40 -> NULL.
3. Reversed: 5 -> 4 -> 3 -> 2 -> 1 -> NULL.
4. has_cycle returns True.
5. deque operations are near-instant regardless of size — try 10 million elements.

Try this modification: write middle(head) that returns the middle node in one pass using two pointers (slow moves 1 step, fast moves 2). This "runner technique" is the second most common linked-list interview trick after reverse.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Real systems rarely use hand-rolled singly linked lists — they use implementations of linked-list ideas hidden inside battle-tested containers. Where they show up:

1. LRU caches. Every LRU cache in production (Redis's allkeys-lru, Guava Cache, Memcached, Python's functools.lru_cache) is conceptually a hashmap keyed by cache-key whose values are nodes in a doubly linked list ordered by recency. On a hit: unlink the node, move it to the head. On eviction: drop the tail. Both operations are O(1) precisely because you already hold a pointer to the node (via the hashmap) and the list is doubly linked so you can unlink without a scan.

2. Task queues and schedulers. collections.deque in Python and LinkedBlockingDeque in Java power work-stealing pools and event loops. Kernel task lists (task_struct in Linux) are intrusive doubly linked lists — the prev/next pointers are embedded in the struct itself so no allocation is needed to enqueue.

3. Memory allocators and free lists. malloc's internal free lists chain unused blocks with pointers stored inside the free memory itself. Zero overhead when the block is free, and O(1) alloc/free in the common case.

Common bugs:

• Losing the head pointer. Standard trainee mistake: reverse a list, forget to return prev, and the original head still points at what is now the tail — but the tail's next is None, so you've silently returned a list of length 1. Always return the new head.
• Off-by-one in doubly linked lists. Insert/delete requires updating up to 4 pointer fields (prev/next of the new/old nodes and both neighbours). Missing one produces a corrupted list that iterates fine forwards but blows up backwards.
• Concurrent modification. Multiple threads touching the same linked list without locks produces cycles ("list becomes a bag with itself in it"). Modern high-perf systems either use per-thread lists + steal, or lock-free structures (Michael-Scott queue) that are far more complex than hand-drawn linked lists suggest.

The mental heuristic: reach for a linked list only when (a) you need O(1) insert/delete at points you already hold pointers to, or (b) you're implementing something structural (LRU, queue, allocator). For "a list of things I want to iterate" — use an array.

(e) Quiz + exercise · 10 min

1. What are the exact steps to insert a new node between nodes A and B in a singly linked list?
2. Why is iterating a linked list slower than iterating an array of the same length, even though both are O(n)?
3. Explain Floyd's tortoise-and-hare cycle detection in one sentence.
4. When would you choose a doubly linked list over a singly linked list?
5. Why does an LRU cache combine a hashmap and a doubly linked list, and what happens on a cache hit?

Stretch (connects to S024 — Hashmaps): Sketch pseudocode for an LRU cache with capacity K supporting get(key) and put(key, value) both in O(1). You will need a hashmap and a doubly linked list — describe exactly what each operation does to both structures.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Linked Lists? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S026): Stacks & Queues — LIFO/FIFO in Practice
• Previous (S024): Hashmaps & Sets — Hash Functions, Collisions
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.