Linked Lists

Nodes that each hold a value and a pointer to the next. Cheap splicing, no random access.

Level: beginner

What is it?

A linked list stores each element in a node that also holds a reference to the next node. A singly linked list has one direction; a doubly linked list keeps previous pointers too. There is no contiguous block, so there is no index arithmetic: to reach the k-th element you follow k links from the head.

Why does it matter?

Linked lists teach pointer manipulation, the same skill needed for trees and graphs, and they give O(1) insertion and removal when you already hold the node. They also show why arrays usually win: pointer chasing is slow on modern hardware.

Mental model

A treasure hunt. Each clue tells you where the next one is, and you cannot skip ahead. Adding a new clue in the middle is trivial — rewrite two notes — but finding clue number 500 means following 499 notes.

How it works

Each node: value plus next (and prev in a doubly linked list).
Insert or delete after a known node: change a couple of pointers, O(1).
Access or search by position: walk from the head, O(n).
Keeping a tail pointer makes appends O(1); a doubly linked list makes removal of a known node O(1).
Nodes are scattered in memory, so traversal has poor cache locality and per-node pointer overhead.
Classic interview moves: reverse a list, detect a cycle with slow and fast pointers, and merge two sorted lists.

Steps

Create a node
Point its next at the successor
Point the predecessor at the node
Walk by following next
Stop at null

Code example: Reversing a list by flipping links

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def reverse(head):
    prev = None
    while head:
        nxt = head.next      # remember the rest
        head.next = prev     # flip this link
        prev, head = head, nxt
    return prev

head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)   # 3 2 1

Complexity and trade-offs

Time: Access/search O(n); insert/delete at a known node O(1)

Space: O(n) plus one pointer per node

Trade-offs

Cheap splicing and no resizing
No random access and poor cache behavior
Extra memory for pointers

Real-world usage

Free lists and allocators, LRU caches (with a hash map), and OS process queues
Building blocks for stacks, queues, and adjacency lists
Undo history and browser navigation

Common mistakes

Losing the rest of the list by overwriting next before saving it.
Forgetting the empty-list and single-node cases.
Choosing a linked list for speed when an array would be faster in practice.

Interview questions

How do you detect a cycle in a linked list?

Floyd's tortoise and hare: advance one pointer by one step and another by two. If there is a cycle they eventually meet; if the fast pointer reaches null there is none. It uses O(1) extra space.

Why is inserting into a linked list O(1) but often slower than an array in practice?

The pointer update is constant once you hold the node, but finding that node is O(n), and nodes scattered across memory cause cache misses, which arrays avoid.

What does a doubly linked list add?

A prev pointer, so you can walk backward and remove a node in O(1) without finding its predecessor, at the cost of more memory and pointers to maintain.