Linear Data Structures
Singly Linked Lists
A chain of nodes where each node stores a value and a pointer to the next node.
1Introduction
Linked lists solve the array's biggest weakness: inserting or removing in the middle without shifting elements. The price is losing O(1) random access.
2What is it?
A singly linked list is a sequence of nodes. Each node holds a value and a `next` reference to the following node; the last node's next is null. The list is accessed through a `head` reference to the first node.
3Why do we use it?
- O(1) insertion and deletion once you have a reference to the right node.
- Grows and shrinks one node at a time — no resizing or copying.
- Building block for stacks, queues, adjacency lists and LRU caches.
4Real-world examples
- A train: each coach is coupled only to the next coach.
- A treasure hunt where every clue tells you where the next clue is.
- Music playlist 'next song' links; browser history chains.
5Internal working
Nodes are allocated separately and can live anywhere in memory; only the next pointers connect them.
To reach the k-th node you must start at head and follow k links — there is no address arithmetic.
Insertion re-wires two pointers: newNode.next = prev.next, then prev.next = newNode. The order matters.
6Memory representation
Nodes are scattered in memory; arrows are stored addresses:
head | v +----+------+ +----+------+ +----+------+ | 10 | 2040-+--->| 20 | 1300-+--->| 30 | null | +----+------+ +----+------+ +----+------+ @1500 @2040 @1300
7Operations
| Operation | How it works |
|---|---|
| Access k-th element | Walk k links from head. |
| Insert at head | newNode.next = head; head = newNode. |
| Insert after a known node | Re-wire two pointers. |
| Insert at position p | Walk p − 1 links, then re-wire. |
| Delete head | head = head.next. |
| Search for a value | Traverse until found. |
| Insert at tail | O(1) with a tail pointer, otherwise O(n). |
8Visual explanation
Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
function insertAt(head, value, position) {
const newNode = new Node(value);
if (position === 0) {
newNode.next = head;
return newNode;
}
let current = head;
for (let i = 0; i < position - 1 && current !== null; i++) {
current = current.next;
}
if (current === null) {
return head;
}
newNode.next = current.next;
current.next = newNode;
return head;
}
function buildList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function printList(head) {
const parts = [];
for (let node = head; node !== null; node = node.next) parts.push(node.value);
parts.push("null");
console.log(parts.join(" -> "));
}
let head = buildList([10, 20, 30, 40]);
head = insertAt(head, 25, 2);
printList(head);
10Time complexity
| Operation | Time |
|---|---|
| Access k-th element | O(k) / O(n) |
| Insert at head | O(1) |
| Insert after a known node | O(1) |
| Insert at position p | O(p) |
| Delete head | O(1) |
| Search for a value | O(n) |
| Insert at tail | O(1) / O(n) |
11Space complexity
n nodes need O(n) space, and every node also stores a pointer, so a linked list uses more memory than an array with the same values. Most list algorithms (reverse, insert, delete, cycle detection) use O(1) extra space.
12Advantages
- Cheap insertion/deletion at known positions.
- No need to know the size in advance.
- No reallocation or copying when growing.
13Disadvantages
- No random access — reaching an index is O(n).
- Extra memory for every pointer.
- Poor cache locality (nodes are scattered).
- Easy to lose the rest of the list with a wrong pointer update.
14Common mistakes
- Updating prev.next before newNode.next — the rest of the list is lost.
- Forgetting the special case of inserting/deleting at the head (use a dummy node).
- Dereferencing null at the end of the list.
- Losing the head reference while traversing (use a separate `current`).
- Not updating the tail pointer when inserting at the end.
15Interview questions
16Practice exercises
- Find the middle node with slow/fast pointers.
- Detect a cycle (Floyd's tortoise and hare).
- Remove the n-th node from the end in one pass.
- Check whether a linked list is a palindrome.
- Delete all nodes with a given value.
Try them in the Coding Playground.