λDSA Learning Hubpart of DSA Atlas

Linked Lists

Beginner~3h · 8 lessons12 practice problems

Nodes and pointers instead of contiguous memory: O(1) splicing, reversal, fast/slow pointers, cycle detection, and the LRU-cache design pattern.

0 of 8 lessons checked off

Introduction

What it is

  • A linked list is a chain of nodes, each holding a value and a pointer to the next node. The list is reachable only through its head; memory is scattered, not contiguous.
  • Variants: singly linked (next only), doubly linked (next and prev), and circular (the tail points back into the list).

Why it matters

  • Linked lists invert the array trade-off: O(1) insertion/deletion at a known node, but O(n) access by index. When a structure must grow and splice constantly — queues, LRU caches, adjacency lists — pointers beat shifting.
  • For interviews, linked lists are the purest test of pointer discipline: one wrong assignment loses half the list, and interviewers watch for exactly that.

How it works

  • Every operation reduces to rewiring next pointers in the correct order: save what you're about to overwrite, then overwrite.
  • A dummy (sentinel) head node removes 'is this the first node?' special cases from insertions and deletions.
  • Two pointers moving at different speeds (fast/slow) answer questions about middles, cycles, and kth-from-end in one pass.

Where it's used

  • OS schedulers and timer wheels keep tasks in linked lists; music-player queues and undo chains are conceptual linked lists; memory allocators track free blocks with them.
  • LRU caches — asked constantly at Meta/Amazon — combine a hash map with a doubly linked list for O(1) get/put.

In interviews

  • Reverse a list (whole or in ranges), detect and locate a cycle, merge two sorted lists, remove kth from end, reorder list, copy a list with random pointers.
Analogy: A linked list is a treasure hunt: each clue holds a value and the location of the next clue. You can splice in a new clue instantly if you're standing at the right spot — but finding clue #500 means following 500 arrows.

Interactive diagram

Three pointers — prev, curr, and a saved next — flip every arrow in one O(n) pass.

∅1curr234prev∅
Three pointers

prev starts at None and curr at the head. The plan: walk the list once, flipping each node's next pointer backwards.

prev
None
curr
1

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Singly linked lists and the node model

    Nodes, head, tail, None termination; why access is O(n).

    20 min
  2. Insertion (head, tail, position)

    Pointer rewiring order and the dummy-node trick.

    20 min
  3. Deletion and search

    Unlinking via the predecessor; why you track prev.

    20 min
  4. Reversing a linked list

    The three-pointer walk — the most-asked list question.

    25 min
  5. Fast and slow pointers

    Middle of list, cycle detection, cycle entry (Floyd).

    25 min
  6. Doubly linked lists

    prev pointers, O(1) delete-given-node, sentinel pairs.

    20 min
  7. Merging and intersections

    Zipper merge of sorted lists; aligning tails for intersection.

    20 min
  8. Design: LRU cache

    Hash map + doubly linked list = O(1) get/put with eviction.

    30 min

Operations

Traversal and insertion

Walk with a cursor until the splice point, then rewire two pointers — new node first, predecessor second.

Traversal and insertion
class ListNode:    def __init__(self, val: int = 0, next: "ListNode | None" = None):        self.val = val        self.next = nextdef insert_at_head(head: ListNode | None, val: int) -> ListNode:    """O(1): the new node simply adopts the old head."""    return ListNode(val, head)def insert_at_tail(head: ListNode | None, val: int) -> ListNode:    """O(n): walk to the end, then link. (Keep a tail pointer to make it O(1).)"""    node = ListNode(val)    if head is None:        return node    cursor = head    while cursor.next:
Time: Head: O(1) · tail/position: O(n)Space: O(1)

Edge cases

  • Insertion into an empty list — the sentinel makes it fall out naturally.
  • Index equal to length appends; index beyond it should raise.
  • Single-node lists: head and tail are the same node.

Common mistakes

  • Assigning prev.next = new before capturing the old prev.next — the suffix is lost.
  • Returning the old head after a head insertion (callers keep the stale head).

Delete a node

Deletion is bypassing: point the predecessor's next past the victim. The victim just becomes unreachable.

Delete a node
def delete_value(head: ListNode | None, val: int) -> ListNode | None:    """Remove the first node holding val. O(n) time, O(1) space."""    dummy = ListNode(0, head)    prev = dummy    while prev.next and prev.next.val != val:        prev = prev.next    if prev.next:                    # found it        prev.next = prev.next.next   # bypass — node is now unreachable    return dummy.next
Time: O(n) to find · O(1) to unlinkSpace: O(1)

Edge cases

  • Deleting the head — the sentinel means no special branch.
  • Value absent: list is returned unchanged.
  • Deleting the only node returns None (empty list).

Common mistakes

  • Stopping the scan at the node itself instead of its predecessor — you need prev to rewire.
  • Checking prev.next.val without first checking prev.next isn't None.

Reverse the list

Walk once, flipping each node's next to point backwards. Save curr.next before overwriting or the remainder is lost.

∅1curr234prev∅
Three pointers

prev starts at None and curr at the head. The plan: walk the list once, flipping each node's next pointer backwards.

prev
None
curr
1
def reverse_list(head: ListNode | None) -> ListNode | None:    prev = None    curr = head    while curr:        nxt = curr.next      # 1. save the rest        curr.next = prev     # 2. flip the arrow        prev = curr          # 3. advance prev        curr = nxt           # 4. advance curr    return prev              # prev is the new head
Time: O(n)Space: O(1) — the recursive version costs O(n) stack

Edge cases

  • Empty list → returns None cleanly.
  • Single node → returned as-is, next already None.
  • Remember the old head is now the tail (next = None).

Common mistakes

  • Overwriting curr.next before saving it — the classic lost-suffix bug.
  • Returning curr (always None at loop exit) instead of prev.

Cycle detection (Floyd's tortoise and hare)

slow moves 1, fast moves 2. In a cycle the gap shrinks by 1 per tick, so they must meet; with no cycle, fast hits None.

1slow · fast2345
Tortoise and hare

slow moves one node per tick, fast moves two. If a cycle exists, fast laps slow inside the loop; if not, fast reaches None.

def has_cycle(head: ListNode | None) -> bool:    """O(n) time, O(1) space — no visited set needed."""    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow is fast:          # identity, not value equality            return True    return False
Time: O(n)Space: O(1) — the hash-set version costs O(n) space

Edge cases

  • Empty or single-node list without self-loop: no cycle.
  • A node pointing to itself is the smallest cycle.
  • To find the cycle START, reset one pointer to head and step both by 1 until they meet.

Common mistakes

  • Comparing slow.val == fast.val instead of node identity (values can repeat).
  • Advancing fast without checking fast.next — AttributeError on None.

Merge two sorted lists

A zipper: repeatedly attach the smaller head to the merged tail. A dummy node holds the zipper's start.

Merge two sorted lists
def merge_sorted(a: ListNode | None, b: ListNode | None) -> ListNode | None:    """Splice two ascending lists into one. O(n + m) time, O(1) space."""    dummy = ListNode(0)    tail = dummy    while a and b:        if a.val <= b.val:            tail.next, a = a, a.next        else:            tail.next, b = b, b.next        tail = tail.next    tail.next = a if a else b     # attach the leftover run    return dummy.next
Time: O(n + m)Space: O(1) — reuses existing nodes

Edge cases

  • Either list empty → return the other.
  • Duplicate values: <= keeps the merge stable.
  • Don't forget the leftover tail after one list empties.

Common mistakes

  • Building new nodes instead of splicing existing ones (unneeded O(n) allocation).
  • Losing the merged head by advancing dummy itself instead of a tail cursor.

Complexity analysis

OperationBestAverageWorstSpace
Access by indexO(1) headO(n)O(n)—
Search by valueO(1)O(n)O(n)O(1)
Insert / delete at headO(1)O(1)O(1)—
Insert / delete at tailO(1) w/ tail ptrO(n)O(n)—
Insert / delete after a known nodeO(1)O(1)O(1)—
ReverseO(n)O(n)O(n)O(1)

Compare row by row with arrays: everything positional flips. Doubly linked lists make delete-given-node O(1) because the predecessor comes free.

Python implementation

Production-quality code with type hints, validation, and docstrings.

A complete singly linked list with sentinel head
from typing import Iterator, Optionalclass _Node:    __slots__ = ("val", "next")    def __init__(self, val: object, next: Optional["_Node"] = None):        self.val = val        self.next = nextclass SinglyLinkedList:    """Singly linked list with sentinel head and tail pointer.    push_front/push_back are O(1); positional ops are O(n)."""    def __init__(self) -> None:        self._head = _Node(None)      # sentinel — never holds data        self._tail = self._head

What interviewers expect you to know

Properties interviewers probe

  • No random access: index i costs O(n). If you need indexes, you likely want an array.
  • Insert/delete after a KNOWN node is O(1) — 'known' is the load-bearing word; finding it is O(n).
  • Doubly linked lists give O(1) delete of a given node because prev is free; singly linked needs the predecessor.

Follow-ups to expect

  • "Reverse it recursively — what's the space cost?" (O(n) stack vs O(1) iterative.)
  • "Where does the cycle START?" — after meeting, reset one pointer to head; step both by one; they meet at the entry (Floyd part 2).
  • "Find the middle in one pass" — fast/slow; when fast hits the end, slow is at the middle.
  • "Why does LRU need a doubly linked list?" — eviction removes the tail node given only the node, needing prev in O(1).

How to narrate pointer code

  • Say the order out loud: 'save next, flip, advance' — it proves you won't lose the suffix.
  • Declare the dummy node before writing edge-case code: 'I'll use a sentinel so head deletion isn't special.'
  • Draw 3 nodes max. Every list algorithm's correctness is visible with three boxes and arrows.

Common mistakes

Losing the rest of the list

Writing curr.next = prev before saving curr.next orphans everything after curr. The save comes first — always.

Null-pointer steps

fast.next.next when fast.next is None crashes. Guard: while fast and fast.next.

Forgetting to return the new head

After reversal or head insertion the entry point changed; returning the old head hands back the tail (or a stale node).

Deleting without the predecessor

In a singly linked list you unlink FROM the node before the victim. Standing on the victim is too late (unless you copy the next node's value — mention that trick explicitly).

Comparing values instead of nodes

Cycle and intersection checks compare identity (is), not equality (==) — duplicate values otherwise cause false positives.

Edge cases skipped

Empty list, single node, and all-nodes-identical break naive code. Test all three mentally before saying 'done'.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (3)

Medium (7)

Hard (2)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. Why is inserting after a given node O(1) in a linked list but O(n) in an array?
  2. Code output2. After reverse_list on 1→2→3, what does the returned node contain and point to?
    def reverse_list(head):    prev = None    while head:        head.next, prev, head = prev, head, head.next    return prev
  3. Concept3. Floyd's cycle detection: why must fast and slow meet if a cycle exists?
  4. Scenario4. Design a structure with O(1) get(key) and O(1) evict-least-recently-used. What combination works?
  5. Complexity5. Recursively reversing a linked list of n nodes uses how much space?
  6. Concept6. What does a dummy/sentinel head node buy you?
0 of 6 answered

Frequently asked questions

Are linked lists actually used in Python, given lists are arrays?

Directly, rarely — collections.deque (a linked structure of blocks) covers most needs. But the pointer patterns transfer to trees, graphs, and cache design, which is why interviews still test them.

When do I choose a doubly linked list?

When you must delete a node given only that node, or traverse both directions — LRU caches, browser history, text editors. The cost is one extra pointer per node and more rewiring per edit.

How do I find where a cycle begins, not just that one exists?

After fast and slow meet, move one pointer back to head; advance both one step at a time. They meet exactly at the cycle entry — a provable distance identity, and a favourite follow-up.

Summary & cheat sheet

Key takeaways

  • Linked list = O(1) splicing at a known node, O(n) everything positional.
  • Save-flip-advance: the reversal rhythm that never loses the suffix.
  • Sentinel nodes delete edge cases; tail pointers make appends O(1).
  • Fast/slow pointers answer middle, cycle, and kth-from-end in one pass.
  • LRU cache = hash map + doubly linked list; both parts are needed for O(1).

Formulas & cheat sheet

  • Middle: when fast reaches the end, slow has gone n/2 steps
  • Cycle entry: head-to-entry distance = meeting-point-to-entry distance (mod cycle length)
  • kth from end: advance lead pointer k steps, then move both until lead hits None

Interview checklist

  • I can reverse a list iteratively without notes.
  • I can write Floyd's algorithm and explain the meeting guarantee.
  • I use a dummy node whenever the head can change.
  • I can merge two sorted lists by splicing, not copying.
  • I can sketch the LRU design and say why each half is needed.