Linked lists: interview prep with practice questions

Nodes and pointers

A linked list stores each element in its own node, and each node holds a pointer to the next one. The nodes can sit anywhere in memory; the pointers chain them together. The list itself only remembers the first node, the head.

That changes the costs compared with an array. Getting to element *n* means following n pointers: O(n), no jumping by index. But if you already hold a node, inserting or removing right after it is O(1): repoint two pointers, nothing moves. A doubly linked list adds a pointer back to the previous node, so you can also remove the node you're holding and walk in both directions.

Four nodes A to D, each pointing to the next; D points to nothing

In real life

A music playlist where songs are constantly inserted after the current one and removed while playing. Inside operating systems, lists of processes and free memory blocks are classic linked lists.

In code: Python · Rust

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

head = Node("A", Node("B", Node("C")))
b = head.next
b.next = Node("X", b.next)   # insert after B: O(1)

# For a real queue or deque, use collections.deque instead

use std::collections::LinkedList;  // doubly linked
let mut l: LinkedList<&str> = LinkedList::new();
l.push_back("B");
l.push_front("A");               // O(1) at both ends

// Hand-written linked lists are famously awkward in Rust
// because each node has one owner; VecDeque is usually the better choice.

In everyday Python and Rust code you rarely write a linked list yourself: deque and VecDeque cover most uses and are faster.
Linked lists still matter in interviews and inside systems: LRU caches, allocators, the Linux kernel's lists.

Check yourself

You hold a reference to a node in the middle of a singly linked list of a million nodes. What does inserting a new node right after it cost?

Linked list or array?

On paper, linked lists win at inserting and removing in the middle. In practice, a dynamic array is faster for most workloads, for two reasons.

First, you usually have to find the position before inserting, and finding is O(n) in a list anyway. Second, array elements sit next to each other, so the CPU reads them in cache-sized chunks; list nodes are scattered, so walking a list means a slow memory access at almost every step. A linked list earns its place when you already hold the node (through a hash map, for example) and need O(1) removal and reinsertion, as in the LRU cache on the next card.

In real life

Benchmarks in most languages show that iterating over a million-element linked list is several times slower than over an array of the same size, even though both are O(n).

Check yourself

Why is iterating over a linked list usually slower than over an array of the same length, even though both are O(n)?

LRU cache: a map and a list together

A least recently used (LRU) cache keeps a fixed number of items and, when full, evicts the one used longest ago. It needs two things at once: find an item by key in O(1), and move any item to the 'most recent' end in O(1).

Neither structure does both alone. A hash map finds keys but has no order. A doubly linked list keeps order and moves a node in O(1), but finding a key in it is O(n). Together they work: the hash map points from key to node, the list keeps nodes in recency order. Get: look up the node, unlink it, put it at the front. Evict: drop the node at the back and delete its key from the map.

A key-to-node map pointing into a doubly linked list ordered from most recent to least recent

In real life

Browser caches, database buffer pools and CDN edge caches all use LRU or a close variant. It's also one of the most frequently asked interview design questions.

In code: Python · Rust

from collections import OrderedDict   # a dict plus a doubly linked list

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k)            # O(1)
        return self.d[k]
    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)   # evict least recent

# For caching function results: functools.lru_cache

// The standard library has no LRU; the widely used `lru` crate does:
// let mut cache = lru::LruCache::new(std::num::NonZeroUsize::new(2).unwrap());
// cache.put("a", 1);
// cache.get(&"a");   // marks "a" as most recent
// Internally: a hash map from key to a node in a doubly linked list.

Python's OrderedDict is exactly a hash map plus a doubly linked list, which is why move_to_end is O(1).
functools.lru_cache wraps a function so repeated calls with the same arguments come from the cache.

Check yourself

Linked lists

Nodes and pointers

You hold a reference to a node in the middle of a singly linked list of a million nodes. What does inserting a new node right after it cost?

Linked list or array?

Why is iterating over a linked list usually slower than over an array of the same length, even though both are O(n)?

LRU cache: a map and a list together

Why does an LRU cache combine a hash map with a doubly linked list rather than using just one of them?

Section complete