Linked Lists Explained — Singly vs Doubly With Code Examples
A linked list is a chain of nodes where each node contains data and a pointer to the next node. Unlike arrays, elements aren't stored contiguously in memory — insertion and deletion are O(1) at any position if you have the node reference. This guide covers both singly and doubly linked lists with full implementations, classic interview problems, and real-world use cases.
O(1)
insert/delete with node reference
O(n)
search — no random access by index
2 types
singly and doubly linked
No resize
grows dynamically unlike arrays
The Core Concept
The treasure hunt analogy
Think of a linked list like a treasure hunt — each clue (node) tells you where to find the next one. To find clue #5, you must follow clues #1 → #2 → #3 → #4 → #5. No jumping directly to #5. This is why search is O(n) but insertion (given a node) is O(1) — you just update pointers.
| Item | Array | Linked List |
|---|---|---|
| Memory layout | Contiguous block — all elements adjacent | Scattered nodes connected by pointers |
| Access by index | O(1) — direct address calculation | O(n) — must traverse from head |
| Insert at head | O(n) — must shift all elements right | O(1) — just update head pointer |
| Insert at middle | O(n) — shift elements after insertion point | O(1) if node known, O(n) to find it |
| Delete from middle | O(n) — shift elements after deletion | O(1) if node known (doubly linked) |
| Memory overhead | Just the data — no pointer overhead | Data + 1-2 pointers (8-16 bytes) per node |
| Cache performance | Excellent — spatial locality, CPU prefetch | Poor — pointer chasing causes cache misses |
Singly Linked List Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// O(1) — insert at head (most common operation)
prepend(data) {
const node = new Node(data);
node.next = this.head;
this.head = node;
this.size++;
}
// O(n) — insert at tail (requires traversal)
append(data) {
const node = new Node(data);
if (!this.head) {
this.head = node;
this.size++;
return;
}
let curr = this.head;
while (curr.next) curr = curr.next; // traverse to end
curr.next = node;
this.size++;
}
// O(n) — insert after a specific value
insertAfter(target, data) {
let curr = this.head;
while (curr && curr.data !== target) curr = curr.next;
if (!curr) return; // target not found
const node = new Node(data);
node.next = curr.next;
curr.next = node;
this.size++;
}
// O(n) — find and delete by value
delete(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
this.size--;
return;
}
let curr = this.head;
while (curr.next && curr.next.data !== data) curr = curr.next;
if (curr.next) {
curr.next = curr.next.next; // skip over the deleted node
this.size--;
}
}
// O(n) — search by value
find(data) {
let curr = this.head;
while (curr) {
if (curr.data === data) return curr;
curr = curr.next;
}
return null; // not found
}
// Convert to array for display/debugging
toArray() {
const arr = [];
let curr = this.head;
while (curr) { arr.push(curr.data); curr = curr.next; }
return arr;
}
}
const list = new SinglyLinkedList();
list.append(1); list.append(2); list.append(3);
list.prepend(0);
console.log(list.toArray()); // [0, 1, 2, 3]
list.delete(2);
console.log(list.toArray()); // [0, 1, 3]Doubly Linked List
Each node has both a next and a prev pointer. This enables O(1) deletion when you have a node reference (no need to find the previous node) and bidirectional traversal. The cost is one extra pointer per node (8 bytes on 64-bit systems).
class DNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null; // ← the key difference from singly linked
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null; // tail pointer enables O(1) append
this.size = 0;
}
// O(1) — add to end (tail pointer makes this O(1) vs O(n) for singly)
append(data) {
const node = new DNode(data);
if (!this.tail) {
this.head = this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.size++;
}
// O(1) — prepend to front
prepend(data) {
const node = new DNode(data);
if (!this.head) {
this.head = this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.size++;
}
// O(1) — delete any node given a direct reference to it
// (Singly linked list requires O(n) to find the previous node)
deleteNode(node) {
if (node.prev) node.prev.next = node.next;
else this.head = node.next; // deleting head
if (node.next) node.next.prev = node.prev;
else this.tail = node.prev; // deleting tail
this.size--;
}
// O(1) — remove from front
removeFirst() {
if (!this.head) return null;
const data = this.head.data;
this.deleteNode(this.head);
return data;
}
// O(1) — remove from back
removeLast() {
if (!this.tail) return null;
const data = this.tail.data;
this.deleteNode(this.tail);
return data;
}
}Classic Interview Problems
// Iterative — O(n) time, O(1) space
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next; // save next before overwriting
curr.next = prev; // reverse the pointer
prev = curr; // advance prev
curr = next; // advance curr
}
return prev; // prev is the new head when curr reaches null
}
// Trace: 1→2→3→4→5
// After: 5→4→3→2→1
// prev is 5 at the end
// Recursive approach — O(n) time, O(n) space (call stack)
function reverseListRecursive(head) {
if (!head || !head.next) return head; // base case
const newHead = reverseListRecursive(head.next); // reverse rest
head.next.next = head; // point next node back to current
head.next = null; // disconnect current from next
return newHead;
}
// Find middle of linked list (fast/slow pointers)
function findMiddle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // slow is at middle when fast reaches end
}function mergeTwoLists(l1, l2) {
// Sentinel/dummy head simplifies edge cases
const dummy = { next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 || l2; // attach remaining nodes
return dummy.next;
}
// [1,2,4] + [1,3,4] → [1,1,2,3,4,4]LRU Cache — Most Important Real-World Application
LRU Cache = Doubly Linked List + HashMap
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key → node (O(1) lookup)
this.head = { key: null, val: null }; // dummy head (most recent side)
this.tail = { key: null, val: null }; // dummy tail (least recent side)
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node); // remove from current position
this._addToFront(node); // move to most recently used
return node.val;
}
put(key, val) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.val = val;
this._remove(node);
this._addToFront(node);
} else {
if (this.map.size === this.capacity) {
const lru = this.tail.prev; // remove least recently used
this._remove(lru);
this.map.delete(lru.key);
}
const node = { key, val };
this.map.set(key, node);
this._addToFront(node);
}
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
}
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // → 1, moves key 1 to front
cache.put(3, 3); // evicts key 2 (least recently used)
cache.get(2); // → -1 (evicted)When to Use a Linked List
Use Linked List
Frequent insertions/deletions at the beginning or middle. Implementing stacks, queues, or deques. When size is highly variable and memory efficiency matters. LRU cache implementation.
Avoid Linked List
Frequent index-based access (use array). Cache-sensitive performance requirements (array has 10-50x better cache hit rate). When memory overhead of pointers matters (embedded systems).
Real Use: Browser History
Back/forward navigation is a doubly linked list. Move forward (next), move backward (prev), truncate future history when navigating to a new URL. Current page is the head node.
Real Use: OS Memory Management
Free memory blocks are managed as a linked list. The allocator traverses the list to find a block of sufficient size (first-fit, best-fit). Coalescing adjacent free blocks requires pointer manipulation.