The idea: a chain of nodes
Picture a scavenger hunt. Each clue holds a piece of information plus directions to where the next clue is hidden. A linked list works the same way: every node holds a value and a pointer to the next node. You keep one reference to the first node, called the head, and follow the pointers one hop at a time until you reach a node whose next pointer is null, which marks the end.
This is a different bargain from an array. An array stores its elements side by side in one contiguous block, so it can jump to index 5 instantly, but inserting near the front means shifting everything after it. A linked list gives up that instant random access — to reach the fifth node you must walk from the head — in exchange for cheap insertion and deletion: once you hold the right node, you just rewire a couple of pointers.
Singly vs doubly linked lists
In a singly linked list each node points only to the next one, so you can travel forward but never back. It is compact and simple, which makes it the default choice for stacks, queues, and hash-table buckets.
A doubly linked list adds a second pointer, prev, so every node knows both its successor and its predecessor. That lets you traverse in either direction and delete a given node in O(1) without first walking the list to find the one before it — the reason an LRU cache pairs a doubly linked list with a hash map. The cost is one extra pointer per node and more bookkeeping on every update. A circular variant links the tail back to the head instead of pointing to null.
Pointer manipulation: reverse, cycles, and merge
Most linked-list problems are really pointer-rewiring puzzles, and three patterns cover the majority of them. Reversing a list is the classic three-pointer dance: keep prev, curr, and a saved next, and on each step flip curr.next to point backward — the golden rule is to save the next node before you overwrite the pointer, or you lose the rest of the list.
Cycle detection uses Floyd's tortoise-and-hare: advance one pointer by one node and another by two; if they ever meet, there is a loop, and if the fast one hits null, there isn't. Merging two sorted lists splices existing nodes together behind a dummy head node, always attaching the smaller front value. None of these move data around — they only redirect pointers, which is exactly why watching them animate node by node makes the mechanics click faster than reading the code.
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def reverse(head):
prev = None
curr = head
while curr:
nxt = curr.next # save the next node first
curr.next = prev # flip the pointer backward
prev = curr # advance prev
curr = nxt # advance curr
return prev # prev is the new headSearching is O(n) on average and in the worst case; it is O(1) only when the target happens to be the head. There is no way to binary-search a linked list because it lacks index access.
When to use it
- You need frequent insertions or deletions at the front or middle and already hold a pointer to that spot, and you don't need random access by index.
- You're implementing a stack, queue, or the buckets of a hash table, where the collection grows and shrinks constantly.
- You're building an LRU cache: a doubly linked list gives O(1) move-to-front and eviction when paired with a hash map for lookups.
- You want to avoid an array's contiguous-memory requirement or its occasional resize copy, for example in a memory allocator's free list.
Watch out for
- Overwriting a next pointer before saving it, which orphans the rest of the list. Always stash the next node in a temporary variable first.
- Mishandling head and tail edge cases — inserting into an empty list or deleting the head. A dummy/sentinel node removes most of these special cases.
- In a doubly linked list, updating only one direction. Every insert or delete must fix both the next and the prev pointers of the affected neighbors.
Linked lists are an interview staple because they force you to reason about pointers and edge cases rather than lean on library methods. Expect classics like reverse a list (iteratively and recursively), detect and find the start of a cycle with fast/slow pointers, find the middle node, merge two sorted lists, remove the k-th node from the end, and detect the intersection of two lists. Interviewers watch whether you draw the pointers, handle the empty-list and single-node cases, reach for a dummy head to simplify insert/delete logic, and avoid losing references while rewiring. Clean, bug-free pointer manipulation with correct null checks signals more than memorizing the answer; talking through your pointers as you move them is exactly what they want to see.