Linked Lists Explained
How a linked list stores data as nodes joined by pointers, what its operations cost compared with an array, and a simple JavaScript implementation.
· Updated · 9 min read
A linked list stores items in separate nodes. Each node holds a value and a reference to the next node. Unlike an array, the nodes do not sit next to each other in memory; the references are what hold the sequence together.
How a linked list is stored
head
↓
[ 12 | next ] → [ 45 | next ] → [ 7 | next ] → nullThe list keeps a reference to the first node, called the head. The last node points to null, which marks the end.
To reach the third item you must start at the head and follow two references. There is no way to jump straight to a position, because nothing records where each node lives.
A node and a list in JavaScript
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Add a value at the front: O(1)
prepend(value) {
this.head = new ListNode(value, this.head);
}
// Visit every value in order: O(n)
toArray() {
const values = [];
let current = this.head;
while (current !== null) {
values.push(current.value);
current = current.next;
}
return values;
}
}The loop in toArray is the standard way to walk a list: start at the head, do something with the current node, move to current.next, and stop at null.
Insert and remove, step by step
Changing a linked list never moves a node. It only changes which node each next points at.
Inserting X between A and B takes two assignments, and the order matters:
start: [A] → [B]
step 1: [A] → [B] X points at B
[X] ↗
step 2: [A] → [X] → [B] A points at XIf A were pointed at X first, the only reference to B would be gone before X could use it.
Removing the node after A takes one assignment: A skips over it.
start: [A] → [X] → [B]
after: [A] ───────→ [B] nothing points at X any moreNothing refers to X now, so JavaScript frees its memory automatically.
// Insert a value after a node you already hold: O(1)
function insertAfter(node, value) {
node.next = new ListNode(value, node.next);
}
// Remove the node after the one you hold: O(1)
function removeAfter(node) {
if (node.next !== null) {
node.next = node.next.next;
}
}insertAfter does both steps in one line: the new node is created already pointing at the old node.next, and only then is it assigned.
Notice that removal needs the node before the one being removed. In a singly linked list there is no way to step backwards from a node to its predecessor, which is why so much linked list code keeps a previous variable.
Finding a value
There is no shortcut for searching. You walk from the head until you find the value or run out of nodes.
function findNode(head, value) {
let current = head;
while (current !== null && current.value !== value) {
current = current.next;
}
return current; // the node, or null if it is not there
}Looking for 7 in the list 12 → 45 → 7:
| Step | current | Is it 7? | Action |
|---|---|---|---|
| 1 | 12 | No | Move to next |
| 2 | 45 | No | Move to next |
| 3 | 7 | Yes | Return this node |
The condition checks current !== null first. If the value is missing, current ends up as null, and reading .value of null would be an error.
What each operation costs
| Operation | Linked list | Array |
|---|---|---|
| Read the item at position i | O(n) | O(1) |
| Search for a value | O(n) | O(n) |
| Insert or remove at the front | O(1) | O(n) |
| Insert or remove after a node you already hold | O(1) | O(n) |
| Insert at the end | O(n), or O(1) if the list keeps a tail reference | O(1) |
Inserting is cheap because nothing moves. To put a new node between A and B, you point the new node at B and point A at the new node. Two references change, however long the list is.
The catch is in the phrase "a node you already hold". Finding that node in the first place is O(n).
Singly and doubly linked lists
The list above is singly linked: each node knows only the next one, so you can move forwards only.
A doubly linked list adds a prev reference to each node. That costs extra memory and more references to update, but lets you walk backwards and remove a node without first finding the one before it.
The three common shapes side by side:
| Kind | Each node points to | Can walk | Typical use |
|---|---|---|---|
| Singly linked | The next node | Forwards | Stacks, queues, simple chains |
| Doubly linked | The next and the previous node | Both ways | Caches, editors, browser history |
| Circular | The last node points back to the first | Round and round | Taking turns, repeating playlists |
Why arrays are usually faster in practice
The table above says that looping over a linked list and looping over an array are both O(n). In real programs the array is still noticeably quicker, for reasons Big O does not show.
- Memory layout. Array items sit side by side, so the processor loads a whole run of them in one go. Nodes are scattered around memory, and each step to
nextmay have to wait for a different part of memory to be fetched. - Memory per item. Every node stores a reference as well as its value, plus the overhead of being a separate object. A list of a million numbers takes several times the memory of an array of the same numbers.
- Creating nodes. Each insertion allocates a new object. Adding to the end of an array usually writes into space that is already reserved.
So the rule of thumb is: use an array unless the specific operation you need is one a linked list does better.
When a linked list is the right choice
Linked lists are used less often than arrays in everyday code, because arrays are faster to loop over and use less memory per item. They are a good fit when:
- you add and remove at the front or in the middle constantly, and rarely read by position;
- you are building a queue, where items leave from the front;
- you need a structure such as a least-recently-used cache, which combines a doubly linked list with a hash table.
They also matter for learning: trees and graphs are built from nodes and references in the same way.
A queue built from a linked list
Here is a linked list doing the job it is best at. A queue adds at the back and removes from the front. Keeping a reference to both ends makes each operation O(1), with no shifting and no wasted memory.
class LinkedQueue {
constructor() {
this.head = null; // the front: next to leave
this.tail = null; // the back: last to arrive
this.size = 0;
}
enqueue(value) {
const node = new ListNode(value);
if (this.tail === null) {
this.head = node; // first item: it is both ends
} else {
this.tail.next = node; // join it on after the old back
}
this.tail = node;
this.size += 1;
}
dequeue() {
if (this.head === null) return undefined;
const value = this.head.value;
this.head = this.head.next;
if (this.head === null) this.tail = null; // it is empty again
this.size -= 1;
return value;
}
}The two if statements handle the empty queue. They are the part most often forgotten: when the last item leaves, tail must be cleared as well as head, or the next enqueue attaches a node to one that is no longer in the queue.
Linked lists in JavaScript
JavaScript has no built-in linked list. For most everyday work an array is the right tool, and push and pop already give constant-time access to one end.
You meet linked lists in three places:
- Inside other structures. A hash table can chain the items in one bucket as a small list. A queue, as above, is a natural fit.
- In structures you build yourself, when you need constant-time removal from the middle, such as a least-recently-used cache.
- In interviews, where they test whether you can follow references and update them without losing any.
Common mistakes
- Losing the rest of the list. If you overwrite
node.nextbefore saving the old value, every node after it becomes unreachable. Save the reference first. - Reading a property of
null.current.next.valuethrows an error whencurrentis the last node. Check fornullbefore each step. - Forgetting the empty list. Code that assumes
headexists fails when the list has no nodes. Handlehead === nullfirst. - Clearing only one end. In a list that tracks both
headandtail, removing the last node must reset both. - Making a loop by accident. Pointing a node back at an earlier one means a walk never reaches
null. After rewiring, trace the list by hand to check that it ends. - Comparing values when you mean nodes. Two different nodes can hold the same value. To ask "is this the same node?", compare the nodes themselves with
===.
Practise
The linked list pointer techniques pattern covers the three moves that solve most problems: fast and slow pointers, reversing links, and a dummy head. Then try them in order:
- Reverse Linked List: the basic rewiring loop.
- Linked List Cycle II: two pointers moving at different speeds.
- Reverse Nodes in k-Group: both ideas together.
Summary
- A linked list is a chain of nodes, each holding a value and a reference to the next node.
- Reading by position and searching are O(n), because you must walk from the head.
- Inserting and removing are O(1) once you hold the right node, because only references change.
- Removing a node needs the node before it, so keep track of
previous. - Arrays are faster for looping and use less memory. Choose a linked list for constant-time changes at the front or in the middle.
- Always handle the empty list, and save a reference before you overwrite it.