Topics

Linked Lists: A Study Guide

A linked list stores a sequence as a chain of nodes, where each node holds a value and a reference to the next node (and, in a doubly linked list, to the previous one). Unlike an array, the elements are not contiguous in memory, so you cannot jump to index k in constant time. That single difference drives every trade-off below.

Why Linked Lists Matter#

Linked lists show up in interviews less for their raw usefulness and more because they force you to reason about pointers carefully. Reversing a list, detecting a cycle, or merging two sorted lists all reward candidates who can track “what points to what” without a diagram. They also underpin real structures: hash-table buckets, LRU caches, and adjacency lists all lean on linked-list mechanics.

Key Operations and Their Big-O#

OperationTimeNotes
Access by indexO(n)No random access; walk from the head
Search for a valueO(n)Linear scan
Insert/delete at headO(1)The core advantage over arrays
Insert/delete at tailO(1) with tail pointer, else O(n)Keep a tail reference for queues
Insert/delete given the nodeO(1) singly (with next), O(1) doublySplicing pointers

The takeaway: linked lists win when you insert and delete near a known node and lose whenever you need indexed access.

A Short Example#

Reversing a singly linked list in place is the canonical warm-up:

 1class Node:
 2    def __init__(self, val, nxt=None):
 3        self.val = val
 4        self.next = nxt
 5
 6def reverse(head):
 7    prev = None
 8    while head:
 9        nxt = head.next   # save before we overwrite it
10        head.next = prev  # flip the pointer
11        prev = head
12        head = nxt
13    return prev           # new head

Common Pitfalls#

  • Losing the rest of the list. Overwrite head.next before saving nxt and everything after is gone. Save first, then reassign.
  • Forgetting the dummy head. Insertions and deletions at the front become uniform if you start with a sentinel dummy node and return dummy.next.
  • Null-pointer edge cases. Empty lists and single-node lists break naive loops. Test both.
  • Fast/slow pointer bugs. For cycle detection and finding the middle, advance the fast pointer by two only after confirming fast and fast.next are non-null.

Where the Curriculum Covers This#

The 60-day challenge devotes several days to linked lists: