Linear
Linked List Fundamentals
A linked list stores elements as a chain of nodes, where each node holds a value and a pointer to the next node. Unlike arrays, elements are scattered across memory — but any node can be inserted or removed in O(1) time once you have a reference to its neighbour, making linked lists the natural complement to arrays.
01
Section One · Foundation
What is Linked List?
A linked list is a collection of nodes allocated anywhere in memory, each holding two things — a data value and a pointer (reference) to the next node. Because nodes are not contiguous, there is no address formula for direct access: reaching element i requires following pointers from the head node, one hop at a time. This makes access O(n) but makes insertion and deletion at a known position O(1) — no shifting required, just pointer rewiring.
Linked lists come in two main flavours:
Singly Linked
One Direction
Each node stores one pointer — next. Traversal is forward-only. Memory-efficient: one pointer overhead per node.
- Simple to implement
- Efficient for stack and queue internals
- Can only traverse forward
Doubly Linked
Bidirectional
Each node stores two pointers — next and prev. Enables backward traversal and O(1) deletion without needing the predecessor.
- O(1) delete with just a node reference
- Enables deque (double-ended queue)
- 2× pointer memory overhead per node
Analogy: A treasure hunt where each clue tells you only where the next clue is hidden. You cannot jump to clue number 7 — you must start at clue 1 and follow every step in sequence. But adding a new clue anywhere in the chain is instant: rewrite two clues to point through the new one.
Key Characteristics
Nodes scattered in heap memory
▶
No O(1) index access — must traverse
Each node holds a next pointer
▶
Insert/delete O(1) with a reference in hand
No pre-allocation needed
▶
Size grows/shrinks dynamically with zero waste
No contiguous layout
▶
Cache-unfriendly — slower iteration than arrays
Doubly linked adds prev pointer
▶
O(1) delete & backward traversal
02
Section Two · Operations
Core Operations
Traverse
Visits every node from head to tail by following next pointers, accumulating or searching as it goes.
Pseudocode
function traverse(head):
current = head
while current is not null:
visit(current.data) // O(1) per node
current = current.next // advance pointer // total: O(n)
Always check for null before accessing
.next. The most common linked list crash is dereferencing a null pointer at the tail. Every loop condition should be current != null — not current.next != null — unless you specifically need to stop one node before the end.Insert Node
Wires a new node into the chain at the head, tail, or a given position by updating exactly two pointers.
Pseudocode
function insertAfter(prevNode, value):
newNode = Node(value)
newNode.next = prevNode.next // step 1: point new → successor
prevNode.next = newNode // step 2: point prev → new // O(1) — only two pointer updates function insertAtHead(head, value):
newNode = Node(value)
newNode.next = head // new node points to old head
head = newNode // head now points to new node return head
Order the pointer updates carefully. When inserting, always set
newNode.next first, then update the predecessor's pointer. Reversing this order loses the reference to the rest of the list — a very common bug.Delete Node
Removes a node from the chain by bypassing it — redirecting the predecessor's next pointer to skip over the target node.
Pseudocode
function deleteAfter(prevNode):
if prevNode.next is null:
return // nothing to delete
prevNode.next = prevNode.next.next // bypass target // O(1) with prevNode in hand function deleteByValue(head, target):
if head.data == target:
return head.next // delete head — O(1)
current = head
while current.next is not null:
if current.next.data == target:
current.next = current.next.next // bypass return head
current = current.next
return head // not found — O(n) search
Finding the node to delete is O(n); the deletion itself is O(1). In a doubly linked list, deletion given only the node reference (no predecessor) is O(1) because
node.prev gives you the predecessor directly. In a singly linked list, you must traverse to find it — O(n).Cycle Detection — Floyd's Algorithm
Uses a slow pointer advancing one step and a fast pointer advancing two steps to detect whether the list contains a cycle in O(n) time and O(1) space.
Pseudocode
function hasCycle(head):
slow = head
fast = head
while fast is not null and fast.next is not null:
slow = slow.next // advance 1 step
fast = fast.next.next // advance 2 steps if slow == fast:
return true // pointers met — cycle exists return false // fast hit null — no cycle
If there is a cycle, slow and fast will always meet. Fast gains one step on slow per iteration. The gap between them decreases by 1 each time, so they are guaranteed to converge inside the cycle — never to "jump over" each other. This is also the basis of finding the cycle entry point (LeetCode 142).
Common Mistake: Losing the head reference. When you write
head = head.next to advance, the original head is gone forever — the entire list behind it is orphaned. Always use a separate current pointer for traversal and leave head pointing to the first node at all times.
03
Section Three · Visuals
Diagrams & Memory Layout
Singly vs Doubly Linked List Structure
Node anatomy — value compartment + pointer compartment(s)
Insert After Node — Pointer Rewiring
Inserting node 99 after node 20 — two pointer updates
Floyd's Cycle Detection — Slow & Fast Pointers
Slow pointer (1 step) and fast pointer (2 steps) converge inside the cycle
04
Section Four · Code
Java Quick Reference
The most common linked list operations using Java's built-in LinkedList — a doubly linked list you'll use in real code and interviews.
Java — LinkedList Core Operations
import java.util.*;
LinkedList<Integer> list = new LinkedList<>();
// O(1) — insert at head and tail
list.addFirst(10); // [10]
list.addLast(30); // [10, 30]
list.add(1, 20); // O(n) insert at index → [10, 20, 30] // O(n) — access by index (must traverse) int val = list.get(1); // 20 int head = list.getFirst(); // 10 — O(1) int tail = list.getLast(); // 30 — O(1) // O(1) — remove from head
list.removeFirst(); // removes 10 → [20, 30] // O(n) — remove by index
list.remove(1); // removes 30 → [20] // O(n) — search boolean has = list.contains(20); // true int idx = list.indexOf(20); // 0
Linked List — Full Implementation
Java — SinglyLinkedList<T> from scratch
public class SinglyLinkedList<T> {
static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
private Node<T> head, tail;
private int size;
// ── O(1) — add at head ─────────────────────────── public void addFirst(T val) {
Node<T> n = new Node<>(val);
n.next = head;
head = n;
if (tail == null) tail = n;
size++;
}
// ── O(1) — add at tail ─────────────────────────── public void addLast(T val) {
Node<T> n = new Node<>(val);
if (tail != null) tail.next = n;
tail = n;
if (head == null) head = n;
size++;
}
// ── O(n) — add at index ────────────────────────── public void addAt(int index, T val) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
if (index == 0) { addFirst(val); return; }
if (index == size) { addLast(val); return; }
Node<T> prev = head;
for (int i = 0; i < index - 1; i++) prev = prev.next;
Node<T> n = new Node<>(val);
n.next = prev.next;
prev.next = n;
size++;
}
// ── O(1) — remove head ────────────────────────── public T removeFirst() {
if (head == null) throw new NoSuchElementException();
T val = head.data;
head = head.next;
if (head == null) tail = null;
size--;
return val;
}
// ── O(n) — remove tail (singly: must find second-to-last) ── public T removeLast() {
if (head == null) throw new NoSuchElementException();
if (head == tail) return removeFirst();
Node<T> cur = head;
while (cur.next != tail) cur = cur.next;
T val = tail.data;
tail = cur;
tail.next = null;
size--;
return val;
}
// ── O(n) — remove at index ─────────────────────── public T removeAt(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
if (index == 0) return removeFirst();
Node<T> prev = head;
for (int i = 0; i < index - 1; i++) prev = prev.next;
T val = prev.next.data;
prev.next = prev.next.next;
if (index == size - 1) tail = prev;
size--;
return val;
}
// ── O(n) — get by index ───────────────────────── public T get(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
Node<T> cur = head;
for (int i = 0; i < index; i++) cur = cur.next;
return cur.data;
}
// ── O(n) — search ─────────────────────────────── public int indexOf(T val) {
Node<T> cur = head;
for (int i = 0; i < size; i++) {
if (cur.data.equals(val)) return i;
cur = cur.next;
}
return -1;
}
// ── O(n) — iterative reverse (3-pointer) ──────── public void reverse() {
tail = head;
Node<T> prev = null, cur = head, next;
while (cur != null) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
head = prev;
}
// ── O(n) — Floyd's cycle detection ────────────── public boolean hasCycle() {
Node<T> slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
public int size() { return size; }
public String toString() {
StringBuilder sb = new StringBuilder();
Node<T> cur = head;
while (cur != null) {
sb.append(cur.data);
if (cur.next != null) sb.append(" → ");
cur = cur.next;
}
sb.append(" → null");
return sb.toString();
}
public static void main(String[] args) {
SinglyLinkedList<Integer> ll = new SinglyLinkedList<>();
ll.addLast(10); ll.addLast(20);
ll.addLast(30); ll.addFirst(5);
System.out.println(ll); // 5 → 10 → 20 → 30 → null
ll.addAt(2, 15);
System.out.println(ll); // 5 → 10 → 15 → 20 → 30 → null
ll.removeFirst();
ll.removeLast();
System.out.println(ll); // 10 → 15 → 20 → null
ll.reverse();
System.out.println(ll); // 20 → 15 → 10 → null System.out.println(ll.indexOf(15)); // 1 System.out.println(ll.hasCycle()); // false
}
}
Python — deque operations & manual Node class
from collections import deque
# ─── 1. Built-in deque (doubly linked under the hood) ─────────
d = deque([10, 20, 30])
d.appendleft(5) # O(1) — [5, 10, 20, 30]
d.append(40) # O(1) — [5, 10, 20, 30, 40]
d.popleft() # O(1) — removes 5
d.pop() # O(1) — removes 40
d.rotate(1) # O(k) — move last to front # ─── 2. Manual singly linked list ───────────────────────────── class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next class LinkedList:
def __init__(self):
self.head = None
self.size = 0 def prepend(self, val): # O(1)
self.head = Node(val, self.head)
self.size += 1 def append(self, val): # O(n) without tail if not self.head:
self.head = Node(val)
else:
cur = self.head
while cur.next: cur = cur.next
cur.next = Node(val)
self.size += 1 def delete_value(self, val): # O(n) if not self.head: return if self.head.data == val:
self.head = self.head.next
self.size -= 1; return
cur = self.head
while cur.next:
if cur.next.data == val:
cur.next = cur.next.next
self.size -= 1; return
cur = cur.next
# ─── 3. Iterative reversal ──────────────────────────────────── def reverse(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev # new head # ─── 4. Floyd's cycle detection ─────────────────────────────── def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True return False
JavaScript — LinkedList class (ES6)
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// O(1) — add to front prepend(val) {
const n = new Node(val);
n.next = this.head;
this.head = n;
if (!this.tail) this.tail = n;
this.size++;
}
// O(1) — add to back append(val) {
const n = new Node(val);
if (this.tail) this.tail.next = n;
this.tail = n;
if (!this.head) this.head = n;
this.size++;
}
// O(n) — insert at index insertAt(index, val) {
if (index === 0) return this.prepend(val);
if (index === this.size) return this.append(val);
let prev = this.head;
for (let i = 0; i < index - 1; i++) prev = prev.next;
const n = new Node(val);
n.next = prev.next;
prev.next = n;
this.size++;
}
// O(1) — remove head removeHead() {
if (!this.head) return null;
const val = this.head.val;
this.head = this.head.next;
if (!this.head) this.tail = null;
this.size--;
return val;
}
// O(n) — remove tail removeTail() {
if (!this.head) return null;
if (this.head === this.tail) return this.removeHead();
let cur = this.head;
while (cur.next !== this.tail) cur = cur.next;
const val = this.tail.val;
this.tail = cur;
this.tail.next = null;
this.size--;
return val;
}
// O(n) — find by value find(val) {
let cur = this.head;
while (cur) {
if (cur.val === val) return cur;
cur = cur.next;
}
return null;
}
// O(n) — iterative reverse reverse() {
this.tail = this.head;
let prev = null, cur = this.head;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
this.head = prev;
}
// O(n) — Floyd's cycle detection hasCycle() {
let slow = this.head, fast = this.head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
toString() {
const parts = [];
let cur = this.head;
while (cur) { parts.push(cur.val); cur = cur.next; }
return parts.join(' -> ') + ' -> null';
}
}
C# — Built-in LinkedList<T> & manual implementation
using System;
using System.Collections.Generic;
// ─── 1. Built-in LinkedList<T> (doubly linked) ────────────── var list = new LinkedList<int>();
list.AddFirst(10); // O(1)
list.AddLast(30); // O(1) var node20 = list.AddAfter(list.First, 20); // O(1) with node ref
list.Remove(node20); // O(1) — direct node removal
list.RemoveFirst(); // O(1) bool has = list.Contains(30); // O(n) var found = list.Find(30); // O(n) — returns LinkedListNode // ─── 2. Manual singly linked list ──────────────────────────── public class SinglyLinkedList<T> {
class Node {
public T Data;
public Node Next;
public Node(T data) { Data = data; }
}
private Node _head, _tail;
private int _size;
public void AddFirst(T val) { // O(1) var n = new Node(val) { Next = _head };
_head = n;
_tail ??= n;
_size++;
}
public void AddLast(T val) { // O(1) var n = new Node(val);
if (_tail != null) _tail.Next = n;
_tail = n;
_head ??= n;
_size++;
}
public T RemoveFirst() { // O(1) if (_head == null) throw new InvalidOperationException();
T val = _head.Data;
_head = _head.Next;
if (_head == null) _tail = null;
_size--;
return val;
}
public void Reverse() { // O(n)
_tail = _head;
Node prev = null, cur = _head;
while (cur != null) {
var next = cur.Next;
cur.Next = prev;
prev = cur;
cur = next;
}
_head = prev;
}
public Node Find(T val) { // O(n) var cur = _head;
while (cur != null) {
if (cur.Data.Equals(val)) return cur;
cur = cur.Next;
}
return null;
}
public int Count => _size;
}
05
Section Five · Complexity
Time & Space Complexity
| Operation | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Access by index | O(1) at head | O(n) | O(n) | O(1) |
| Insert at head / tail | O(1) | O(1) | O(1) | O(1) |
| Insert at index | O(1) | O(n) | O(n) | O(1) |
| Delete at head | O(1) | O(1) | O(1) | O(1) |
| Delete at index / tail (singly) | O(1) | O(n) | O(n) | O(1) |
Why these complexities? There is no address formula — reaching index i requires following i pointers from the head. But once you hold a reference to a node's predecessor, the insert or delete is just two pointer assignments — truly O(1) regardless of list length. Tail insertion is O(1) only when a tail pointer is maintained; without it, you must traverse the entire list to find the last node.
Space Complexity Note
A linked list of n nodes uses O(n) space for data, plus O(n) for pointers — one per node for singly linked, two per node for doubly linked. This pointer overhead is the primary memory disadvantage versus arrays. However, there is no wasted capacity: a linked list of size n uses exactly n nodes, with no over-allocation. Auxiliary space for all operations is O(1) except recursion-based reversal which uses O(n) call-stack space.
06
Section Six · Decision Guide
When to Use Linked List
Use This When
- Frequent insertions / deletions at known positions — O(1) pointer rewiring beats O(n) array shifts every time.
- You're building a stack or queue — addFirst / removeFirst (stack) and addLast / removeFirst (queue) are both O(1).
- Size changes constantly — no resizing, no capacity waste, memory is allocated and freed per node.
Avoid When
- Random access is frequent — every
get(i)is O(n); an array reaches the same element in O(1). - Cache performance matters — nodes scattered in heap memory miss the CPU cache heavily; arrays iterate 3–5× faster in practice.
Comparison vs Alternatives
| Structure | Access | Insert | Delete | Best For |
|---|---|---|---|---|
| Linked List ← this one | O(n) | O(1) | O(1) | Frequent inserts/deletes, stack/queue internals |
| Array | O(1) | O(n) | O(n) | Random access, cache-friendly iteration |
| Doubly Linked List | O(n) | O(1) | O(1) no traversal | Deque, LRU cache, browser history |
07
Section Seven · Interview Practice
LeetCode Problems
Linked list interview problems almost always involve one of four patterns: two pointers (fast/slow for cycle detection and midpoint finding), dummy head node (simplifies edge cases at the list head), in-place reversal (rewiring pointers without extra memory), or merge patterns (combining two sorted lists by pointer comparison).
- Easy Reverse Linked List —
Three-pointer iterative approach:
prev,curr,next— then swapcurr.next = preveach step. - Easy Merge Two Sorted Lists — Use a dummy head node; compare heads and attach the smaller one each step — clean O(n+m) merge.
- Medium Linked List Cycle II — Floyd's detection finds the meeting point; then reset one pointer to head and advance both one step — they meet at the cycle entry.
- Medium Remove Nth Node From End — Two-pointer gap trick: advance the fast pointer n steps first, then move both — fast hitting null means slow is at the target.
- Hard LRU Cache — Combine a HashMap with a doubly linked list — O(1) get and put by using the map for lookup and the list for O(1) move-to-front.
Interview Pattern: When a linked list problem feels complicated, always ask two questions first: "Would a dummy head node eliminate my edge cases?" and "Can slow/fast pointers replace a two-pass traversal?" These two moves handle the majority of medium linked list problems without needing extra data structures.