Linked Lists — Nodes and Pointers
Imagine a treasure hunt where each clue tells you where the next clue is hidden. You can hide clues anywhere in town, and adding a new clue in the middle only means rewriting one old clue. But to reach clue 50, you have no choice: you follow clues 1 to 49 first. That is a linked list.
The rule
Each node holds a value and where the next node lives.
A linked list does not need one big block of memory. Each element sits in its own small node, which can be anywhere in memory. A node holds two things:
- the value,
- a pointer: the memory address of the next node.
The list itself only remembers the address of the first node, called the head. The last node's pointer is empty (null, None, nullptr), which marks the end.
class Node:
def __init__(self, value):
self.value = value
self.next = None # address of the next node, or nothingBecause order lives in the pointers, not in positions, a linked list has the opposite strengths of an array:
| Array | Linked list | |
|---|---|---|
| Reach element k | one jump | walk k pointers |
| Insert after a node you hold | shift everything after | change two pointers |
| Extra memory | none | one pointer per node |
A doubly linked list also stores a pointer back to the previous node, so you can walk both ways at the price of a second pointer in every node.
The shortcut
Arrays jump, lists walk. For any operation, ask: "Do I already hold the node I need?" If yes, a list is cheap. If you must find it by position, you walk from the head, one hop per node.
Start
The list is A → B → C, and you already hold node B.
The trap is doing those two steps the other way round. If you set B's next to X first, nobody points to C any more, and the rest of the list is lost.
Drills
Answer fast — trust the rule.
What does the last node of a singly linked list store as its next pointer?
Starting at the head (position 0), how many pointer hops reach the node at position 49?
You hold node B in A → B → C and want to insert X after B. Which step must come first?
Which job suits a linked list better than an array?
Remember
- A node holds a value and the address of the next node; the head starts the list.
- Arrays jump, lists walk: position lookups cost one hop per node.
- The trap: link the new node forward before redirecting the old one, or you lose the tail.