Linked Lists
Nodes chained by pointers, not laid out in contiguous memory: O(1) insert and delete at a known node, but O(n) access — the mirror image of an array's trade-off.
What you'll learn
- A linked list is nodes, each holding a value and a pointer to the next
- Singly vs doubly linked: one forward pointer, or forward and backward
- Insert/delete at a known node is O(1) — just relink the pointers
- Access and search are O(n) — there is no index, you must traverse
- Array vs linked list: opposite trade-offs, chosen by the dominant operation
Before you start
An array stores its elements in one contiguous block of memory, so element k lives
at a known offset — instant access, but inserting in the middle means shifting
everything after it. A linked list makes the opposite bargain: it scatters
elements anywhere in memory and chains them with pointers (a pointer is just a
stored reference to where the next node lives). Splicing a node in or out is trivial,
but reaching the k-th element means walking the chain from the start. This same
trade-off decides everyday design choices — an LRU cache, for instance, keeps its
entries in a linked list precisely so it can move a “just-used” item to the front in
O(1).
Nodes and pointers
A linked list is a sequence of nodes. Each node holds a value and a
pointer to the next node; the last node points to nothing (null). A separate
head reference marks the start. In a singly linked list each node points only
forward; in a doubly linked list each node also stores a prev pointer, so you
can walk backward and delete a node knowing only that node.
The cost trade-off
Because there is no index, access and search are O(n) — to reach the k-th
node you must follow k pointers from the head. But once you are at a node,
insert and delete are O(1): you just relink a couple of pointers, with no
shifting of other elements. That is the exact reverse of an array, which indexes in
O(1) but pays O(n) to insert or delete in the middle (everything after must
shift).
Pick the operation you do most. Drive each one and watch what the two structures actually have to do:
One caveat the diagram hides: the O(1) insert/delete assumes you already hold the
relevant node. If you must first find the position by value or index, that search
is O(n) — the splice itself is still O(1), but getting there is not free.
How GATE asks this
Usually an MCQ or MSQ: it states an operation (traverse, insert after a node, delete a node) and asks for the cost, or it lists array-vs-linked-list claims and asks which are true. The reliable approach is to ask two questions — do I already have the node, or must I search for it? and am I accessing by position or relinking? — then read the cost straight off the table above.
Worked example — relinking is O(1), finding is O(n)
Start with the singly linked list A -> B -> C and a head pointing at A.
Insert a node X after the head. Two pointer writes: point X.next at whatever
the head pointed to (B), then point head.next at X. No other node moves.
before: head -> A -> B -> C
step 1: X.next = head.next (X now points to B)
step 2: head.next = X (A now points to X)
after: head -> A -> X -> B -> C (2 pointer updates, O(1))Delete node B. Given the node before it (here A), one pointer write:
re-point A.next to B.next (which is C). B is now unreachable and the chain
is intact.
before: A -> B -> C
step 1: A.next = B.next (A now points to C)
after: A -> C (1 pointer update, O(1))Both edits are O(1) once you hold the right node. Contrast finding the 4th
element: with no index you must follow pointers head -> 1st -> 2nd -> 3rd -> 4th,
an O(n) traversal. The relink is cheap; the navigation is what costs.
Quick check
Quick check
Practice this in an interview
All questionsIteratively: walk the list with three pointers — prev, current, and next — rewiring each node's pointer as you go. Recursively: reverse the rest of the list, then attach the current head to the new tail. Both are O(n) time, O(1) and O(n) space respectively.
Use a dummy head node to avoid special-casing the result's first element. Walk both lists with two pointers, always appending the smaller current node to the result. When one list is exhausted, append the remainder of the other. O(n + m) time, O(1) space.
Two pointers start at the head — slow moves one step, fast moves two. If there is a cycle, fast laps slow and they meet inside the cycle. If fast reaches None, there is no cycle. This runs in O(n) time with O(1) space, no hash set needed.
Use a queue (deque) to process nodes layer by layer. At each step, snapshot the current queue length to know exactly how many nodes belong to the current level, drain those, then enqueue their children. The result is a list of lists without any depth-tracking variable.