Nodes joined by pointers
A singly linked list stores each element in its own node. A node holds a value plus a single reference to the next node. The list keeps a head pointer to the first node, and the final node points to nothing, marking the end. Unlike an array, the nodes need not sit next to each other in memory.
What it is good at
Because nodes are linked rather than packed, inserting or removing at the front is quick: you just adjust a couple of references.
- Prepend a value by making a new node point to the old head, then move the head.
- Remove the front by advancing the head to the second node.
No shifting of other elements is required, which a contiguous array would need.
What it is bad at
The cost is access. There is no formula to jump to the tenth element. To reach a position you must walk the chain from the head, following next pointers one at a time. You also pay extra memory for every pointer.
Key idea
A singly linked list chains forward-pointing nodes, making front insertion and deletion cheap but random access slow because reaching any position means walking from the head.