Linked Lists: Nodes, Pointers, and When They Beat Arrays
Building a singly linked list from individual nodes, and the specific, narrow situation where it genuinely outperforms a dynamic array.
What you'll learn
- Implement a singly linked list's core operations: append, prepend, and delete
- Explain why linked-list traversal is O(n) while arrays offer O(1) index access
- Identify the specific situation where a linked list's O(1) front-insertion genuinely matters
Prerequisites
Explanation
A singly linked list stores its elements as separate nodes, each holding a value and a reference (next) to the following node — there is no contiguous block of memory the way an array has, only a chain of individually-allocated nodes connected by references, starting from a head reference the list keeps track of. { value: 10, next: { value: 20, next: { value: 30, next: null } } } is a three-node list; the last node's next is null, marking the end.
This structure inverts the array's tradeoffs almost exactly. Prepending (adding a new node at the front) is O(1): create a new node whose next points at the current head, then update head to point at the new node — no existing node moves or is copied, unlike an array's O(n) front-insertion. But indexed access (get(i)) becomes O(n): there's no way to jump directly to the ith node, since nodes aren't stored at predictable, computable addresses — you must walk the chain from head, following next references one at a time, exactly i times. Appending to the end is also O(n) for a plain singly linked list unless you separately maintain a tail reference (a common, worthwhile optimization) — without one, reaching the last node still requires walking the whole chain.
The practical decision rule follows directly from this: a linked list wins specifically when a program does frequent insertions/removals at the front (or at an already-known node) and rarely needs indexed access by position — a genuinely narrow use case in practice, which is exactly why dynamic arrays (with their O(1) amortized append and O(1) index access) are the default choice for most real code, and linked lists are reached for deliberately, not by default. Doubly linked lists (each node also holding a prev reference) make removal of an already-known node O(1) in both directions and are what underlies structures like a deque, covered in the next module.
Example
A minimal singly linked list built from plain objects -- no class needed to see the node/pointer structure clearly.
function makeNode(value, next = null) {
return { value, next };
}
// Build the list 10 -> 20 -> 30 by hand, back to front:
const list = makeNode(10, makeNode(20, makeNode(30)));
function toArray(head) {
const result = [];
let current = head;
while (current !== null) {
result.push(current.value);
current = current.next; // walk the chain one node at a time -- O(n) traversal
}
return result;
}
console.log(toArray(list)); // [10, 20, 30]
function prepend(head, value) {
return makeNode(value, head); // O(1) -- no existing node touched
}
console.log(toArray(prepend(list, 5))); // [5, 10, 20, 30]Try it yourself
Add a fourth node (value 40) to the end of the chain by hand, then print the list with toArray.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write getAt(head, index) that returns the value at the given index by walking the chain (0-indexed), or null if the index is out of range (including a negative index or an index >= the list's length).
Checks: finds the value at index 0 · finds the value at the last index · returns null for an out-of-range index · returns null for a negative index · handles an empty list (head is null)
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write removeValue(head, target) that returns a NEW head reference for the list with the first node matching target's value removed (the list is otherwise unchanged in order). If target isn't found, return the original head unchanged. Handle removing the head node itself as a special, necessary case -- unlike removing from the middle, updating head is the ONLY way to remove the first node, since there's no 'previous' node's next to update.
Checks: removes a node from the middle of the list · removes the head node (the special case) · leaves the list unchanged when the target isn't found · handles removing from an empty list
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Using a linked list by default for a general-purpose collection -- for most real workloads (frequent indexed access, appending at the end), a dynamic array is both simpler and faster; linked lists solve a specific, narrower problem.
- Forgetting to handle removing the head node as a special case -- every other removal updates some node's .next, but removing the head requires updating the head reference itself, since no node points to it.
- Losing the reference to the rest of the list while reassigning .next during an operation -- always capture current.next in a local variable BEFORE overwriting current.next, if you still need to continue traversing afterward.
Knowledge check
Takeaway
A linked list trades an array's O(1) indexed access for O(1) front-insertion — a narrow, specific tradeoff that only pays off when frequent front-insertion (or removal at an already-known node) genuinely dominates a program's workload, which is uncommon enough that dynamic arrays remain the default choice.
Summary
A linked list is a chain of individually allocated nodes connected by next references. Prepending is O(1); indexed access and (without a tail pointer) appending are O(n), since reaching any node requires walking the chain from head. Removing the head node requires special handling, since no other node's .next points to it.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.