Linked Lists and Pointer Operations
A linked list stores order through references between nodes rather than contiguous positions. Its power comes from rewiring a few links; its difficulty comes from preserving reachability during every update.
Nodes, and What Holds Them Together
A linked list stores each element in its own separately allocated node. Every node carries a value and at least one pointer holding the address of another node. Nothing else connects them — the nodes may sit anywhere in memory, in any order, and the pointers alone define the sequence.
The list is reached through a single head reference. Lose it and the entire list becomes unreachable, which is exactly how linked lists leak memory in C: overwrite head before freeing the chain and every node behind it is orphaned.
Because there is no layout rule, there is no address arithmetic. An array can compute where element k lives; a linked list has to walk to it, following one pointer at a time. That single fact explains every cost difference in the rest of this lesson.
The end of the list is marked by a null pointer rather than a stored count. A traversal is written while (current != null), and this is why a corrupted next pointer does not raise an error — it simply walks into memory that was never part of the list.
- Node = value + pointer(s) to other nodes
- The
headreference is the only entry point - No contiguity means no address arithmetic
- Null terminates the chain; there is no stored length
The Trade Against Arrays
The comparison is the reason the structure exists, and it reduces to one sentence worth memorising: an array is faster to read by position, a linked list is faster to edit once you are already there.
Inserting into the middle of an array requires shifting every later element one slot along — O(n) of pure data movement. A linked list changes two pointers and is done, O(1), with no element ever moving. Deletion has the same shape.
But reaching that middle position costs O(n) in a linked list and O(1) in an array. So the linked list wins only when you already hold a reference to the node, or when you are always working at the ends. Inserting at position k from scratch is O(n) either way — the array pays in shifting, the list pays in walking.
There is a cost that complexity notation hides. Array elements sit consecutively, so the CPU prefetches them and a scan runs at memory bandwidth. Linked list nodes are scattered, so each hop is a potential cache miss costing hundreds of cycles. This is why an array frequently outperforms a linked list on real hardware even where the O-notation says it should not, and why std::vector is the default recommendation in C++ over std::list.
Memory overhead points the same way. A list of 32-bit integers spends 8 bytes per node on a 64-bit pointer, so two thirds of the structure is bookkeeping — before counting the per-allocation header most allocators add. An array of the same values spends nothing.
| Operation | Array | Linked list |
|---|---|---|
| Read element k | O(1) | O(n) |
| Insert or delete at the front | O(n) | O(1) |
| Insert or delete at a node you hold | O(n) — shifting | O(1) — two writes |
| Insert at position k from scratch | O(n) | O(n) |
| Search by value | O(n) | O(n) |
| Growth | Resize and copy | One node at a time |
| Cache behaviour | Sequential, prefetched | Scattered, miss-prone |
- Arrays win on access; linked lists win on in-place editing
- Positional insertion is O(n) for both — different reasons
- Linked lists grow without resize-and-copy
- Cache misses and pointer overhead often outweigh the theory
The Four Types
Variants differ in only two respects: how many pointers a node carries, and whether the chain terminates or closes on itself.
A singly linked list node holds next alone. Traversal runs forward only and the last next is null. It is the smallest node and the default choice when forward movement suffices.
A doubly linked list adds a prev pointer. This buys backward traversal and, more consequentially, deletion of a node you already hold in O(1) — the same deletion is O(n) in a singly linked list because the predecessor has to be located by walking from the head. The price is a second pointer per node and two extra writes on every structural change.
A circular linked list points the last node back to the first, so there is no null to stop on and loops must terminate by comparing against the node they started from — forget that and the traversal never ends. A circular doubly linked list does both, wrapping in each direction; it is the structure beneath many operating-system run queues and the LinkedList in several standard libraries.
The choice is not primarily about memory. It is about which operations you need to be cheap: forward-only iteration argues for singly linked, deletion of held nodes or backward movement argues for doubly linked, and endless rotation over a fixed set argues for circular.
- Singly — one pointer, forward only, cheapest
- Doubly — adds
prev, enabling O(1) deletion of a held node - Circular — no null terminator, so loop against the start node
- Circular doubly — wraps both ways; used for round-robin queues
Terms, operations, and practical uses
Node vocabulary
- HeadThe first reachable node; losing it can make the entire list unreachable.
- Next referenceThe link from one node to its successor.
- TailThe final node, whose next reference is
nullin a non-circular singly linked list. - Dummy nodeA temporary predecessor that makes head insertion and deletion follow the same rule as middle updates.
Safe pointer operations
- SaveKeep the old successor before overwriting a link.
- RewireChange exactly one reference while the remaining nodes are still reachable.
- AdvanceMove the working pointers only after the new link is correct.
Useful variants
- Doubly linked listStores both next and previous references for two-way traversal and local removal.
- Circular listConnects the tail back to an earlier node instead of
null. - Fast and slow pointersEncode a distance difference to find a midpoint, cycle, or node measured from the end.
Reverse a singly linked list
def reverse(head):
previous = None
current = head
while current:
following = current.next
current.next = previous
previous = current
current = following
return previous
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
head = Node(10, Node(20, Node(30)))
node = reverse(head)
parts = []
while node:
parts.append(str(node.value))
node = node.next
print(' → '.join(parts) + ' → null')#include <iostream>
#include <string>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {
}
};
ListNode* reverseList(ListNode* head) {
ListNode* previous = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* following = current->next;
current->next = previous;
previous = current;
current = following;
}
return previous;
}
int main() {
ListNode* head = new ListNode(10, new ListNode(20, new ListNode(30)));
ListNode* node = reverseList(head);
string out;
while(node) {
out += to_string(node->val) + " \u2192 ";
node = node->next;
}
cout << out << "null\n";
}public class Main {
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode following = current.next;
current.next = previous;
previous = current;
current = following;
}
return previous;
}
public static void main(String[] args) {
ListNode head = new ListNode(10, new ListNode(20, new ListNode(30)));
ListNode node = new Main().reverseList(head);
StringBuilder sb = new StringBuilder();
while(node != null) {
sb.append(node.val).append(" \u2192 ");
node = node.next;
}
System.out.println(sb + "null");
}
}Step through it
Running on 10 → 20 → 30 → null
Read all 10 Steps
- Initialize pointers Previous is null and current is the head node 10.
- Save 10.next Store the following node 20 before changing the only link that reaches it.
- Reverse the first link Set 10.next to previous, which is null. The original list is now split into two valid chains.
- Advance to 20 Move previous to 10 and current to the saved node 20.
- Save 20.next Store following = 30 before replacing 20.next.
- Link 20 to 10 Set 20.next to previous. The reversed chain is now 20 → 10 → null.
- Advance to 30 Move previous to 20 and current to the saved node 30.
- Save 30.next The saved following reference is null because 30 was the original tail.
- Link 30 to 20 Set 30.next to previous, joining all three nodes in reversed order.
- Return the new head Advance once more: current becomes null and previous becomes 30. Return previous as the new head.
Rewiring Safely
Whichever type you use, structural changes are a short sequence of pointer writes in which the order is not a matter of taste. Nearly every linked-list bug is a write performed one step too early.
The rule covering all of them: save the pointer you are about to overwrite, before you overwrite it. Attach the new node's outgoing links first, then redirect the incoming one, so the original chain stays readable until the replacement is fully built.
Inserting X after p is therefore X.next = p.next and only then p.next = X. Reversing those two lines overwrites the sole reference to everything past p, orphaning the entire tail of the list — a leak in C or C++, silent data loss in a managed language.
Deletion works through the predecessor, not the victim, which is the asymmetry that makes singly linked lists awkward and doubly linked lists useful. In a doubly linked list the node's own prev supplies the predecessor immediately.
Three cases deserve separate checking every time, because they are where the general code stops applying: the empty list, the single-node list, and any operation touching the head. A dummy head node placed in front of the real first node removes the third case entirely by giving every real node a predecessor, which is why so many list algorithms open by allocating one.
- Save the pointer before overwriting it — always
X.next = p.next, thenp.next = X; never the reverse- Deletion rewires the predecessor, not the node itself
- Test the empty list, the one-node list, and the head separately