Data Structures & Algorithms
Linked Lists
A linked list stores a sequence of values as separate nodes, each holding its value and a reference to the next node in the chain, rather than laying every value out contiguously the way an array does. There is no requirement that the nodes sit near each other in memory, which is what makes inserting or removing a node at a known point cheap - only the neighboring references need to change. The tradeoff is that there is no way to jump directly to the k-th element; reaching it means walking the chain from the head, one node at a time.
Why it matters
- It is the clearest introduction to pointer-based structures
- Understanding a node that references another node is the same idea that underlies trees and graphs, just with each node limited to one next instead of several.
- It explains why some structures avoid the shifting cost arrays have
- A structure built on linked nodes can insert or remove at a known position without moving every other element over, unlike an array.
- It is a standard interview topic specifically because it exercises pointer manipulation
- Problems like reversing a linked list or detecting a cycle test a different skill than array manipulation does, which is exactly why they keep getting asked.
- The idea shows up inside real structures, not just as a standalone topic
- A hash table that resolves collisions by chaining is, at each bucket, keeping a small linked list of the entries that landed there.
Nodes and the chain
Each node in a singly linked list holds a value and a reference to the next node, or to nothing if it is the last node. The list itself usually just keeps a reference to the first node, called the head; everything else is reached by following next references from there. A doubly linked list adds a second reference, to the previous node, which makes it possible to walk backward as well as forward, at the cost of an extra reference to maintain per node.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
head = Node(1, Node(2, Node(3)))
current = head
while current is not None:
print(current.value)
current = current.nextWhat's cheap and what's expensive
Inserting or removing a node is O(1) once you already have a reference to the node right before the change point, because it only involves rewiring a next reference or two. Reaching that point in the first place, by position, is O(n) - there is no shortcut, since the only way to find the k-th node is to walk from the head, counting as you go. This is close to the reverse of an array's cost profile: an array gives O(1) access by index but O(n) insertion in the middle, while a linked list gives O(1) insertion at a known point but O(n) access by index.
Mistakes people make here
- Overwriting a node's next reference before saving the rest of the chain
- Reversing a linked list, or inserting into the middle of one, requires care about the order operations happen in - changing a node's next reference before you have saved a reference to what it used to point at permanently disconnects the rest of the list.
- Forgetting to handle the empty-list or single-node case
- Code written and tested against a list with several nodes often silently assumes there is always a next node to look at, and breaks on an empty list with no head at all, or a one-node list where head and tail are the same node.
- Assuming linked lists have O(1) indexed access, the way arrays do
- Reaching a specific position in a linked list still means walking that many nodes from the head - there is no way to compute a node's location directly the way array indexing does.
- Accidentally creating a cycle
- If a node's next reference, directly or through several steps, ends up pointing back to an earlier node in the same list, a simple traversal that expects to eventually reach the end will loop forever instead.
Strengths and trade-offs
Where it is strong
- Insertion and deletion at a known position is O(1), with no shifting of other elements required the way an array needs.
- The list grows and shrinks one node at a time, with no need to reallocate and copy a whole backing buffer.
- The pointer-chasing pattern it teaches reappears directly in trees and graphs, so the skill transfers rather than being a dead end.
The trade-offs
- No O(1) random access - reaching the k-th element means walking k nodes from the head, every time.
- Each node carries the memory overhead of at least one reference, which a plain array does not need.
- Worse cache locality than an array, since nodes are typically scattered across memory rather than laid out contiguously, which costs real speed even when the Big-O comparison looks favorable.
Who needs this
Mainly a CS-fundamentals and interview topic today, since most everyday application code reaches for a language's built-in dynamic array or a more specialized structure instead of hand-rolling a linked list. It is still worth knowing, because it is the reference point the cost of other structures gets explained against.
Questions about linked lists
- Why not just always use a list or array instead of a linked list?
- In most everyday code, an array-backed structure genuinely wins, because index access and cache-friendly scanning matter more often than cheap mid-list insertion does. Linked lists earn their keep in narrower cases, frequent insertion or removal at a position you already have a direct reference to, without needing index-based access.
- What's the difference between a singly and a doubly linked list?
- A singly linked list's nodes only reference the next node, so you can only walk forward. A doubly linked list's nodes also reference the previous node, letting you walk backward too, at the cost of an extra reference per node to keep in sync.
- Does Python have a built-in linked list?
- Not a dedicated one. collections.deque is implemented as a doubly linked list of fixed-size blocks internally and gives O(1) additions and removals at both ends, which covers most of what people actually reach for a linked list to do.
- Why are linked lists asked about so much in interviews if they're rarely used directly?
- Because problems built around them, reversing one, detecting a cycle, merging two sorted ones, specifically test whether you can reason carefully about references and edge cases, a skill that is hard to assess with array-based problems alone.