Linear

Linked List Fundamentals

A chain of nodes scattered across memory — O(1) insertion and deletion at any known position, O(n) access by index. The structure behind Java's LinkedList and every undo/redo stack.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation

What is Linked List?

7 • 12 • O(1) insert 25 • 41 ∅ nodes scattered across heap memory

A linked list stores each element in a separate node — an object that holds one value and one pointer to the next node. Nodes are allocated independently on the heap, so they sit at arbitrary memory addresses rather than in a contiguous block. To reach element k, you must start at the head and follow k pointers — that sequential walk is why random access costs O(n). The payoff is structural flexibility: when you already hold a reference to the preceding node, inserting or deleting takes O(1) because you only redirect one or two pointers — no elements shift. Java’s LinkedList<T> is a doubly-linked list (each node also points backward), giving O(1) operations at both head and tail. You encounter this structure behind undo history, LRU caches (LinkedHashMap), OS task scheduling, and any scenario that demands frequent mid-sequence modification without costly array copies.

Analogy: A treasure-hunt game where each clue card contains one item and the address of the next clue card hidden somewhere in the building. You cannot jump to clue 5 directly — you must follow the chain from clue 1. But if you want to add a new clue between clue 3 and clue 4, you simply write the new card, hand it clue 4’s address, and update clue 3 to point to the new card — nobody else moves.
02
Section Two · Mental Model

How It Thinks

Each node lives at an independent heap address
▶
No contiguous block required — memory can be fragmented
Only way to reach node k is to follow k pointers from head
▶
Random access costs O(n) — no address formula exists
Insert/delete only redirects one or two pointers
▶
O(1) modification when you already hold a reference to the target node
Nodes are scattered — CPU cannot prefetch next node
▶
Poor cache locality makes sequential iteration slower than arrays in practice
Each node stores an extra pointer (8 bytes on 64-bit JVM)
▶
Higher per-element memory overhead compared to a plain array
03
Section Three · Operations

Core Operations

Traverse
Walks from head to tail, visiting every node once by following next pointers — O(n) to process all elements.
Pseudocode
function traverse(head): current = head while current != null: process(current.value) // visit this node current = current.next // advance pointer // O(n) — one pass through entire list
Traverse — visit every node from head to null
current walks left → right 7 • ✓ 12 • ✓ 25 • current 41 ∅ → null (stop)
Always check current != null, not current.next != null:
  • Using current.next != null as the loop condition skips processing of the last node and also fails when the list is empty (head is null).
  • The correct idiom is while (current != null) with current = current.next at the end of the body.
Insert at Head
Creates a new node, points it at the current head, and updates head — O(1) because no traversal is needed.
Pseudocode
function insertAtHead(head, value): newNode = new Node(value) // allocate on heap newNode.next = head // point to old head head = newNode // update head reference return head // O(1) — no traversal
Insert at Head — prepend value 3
BEFORE head → [7] → [12] → [25] → null head 7 • 12 • 25 ∅ AFTER head → [3] → [7] → [12] → [25] → null head 3 • new node 7 • 12 • 25 ∅
Order matters — point newNode.next first:
  • If you update head before setting newNode.next, you lose the reference to the old list.
  • Always wire the new node’s next pointer to the existing head before swinging head to the new node.
Insert at Tail
Walks to the last node and appends a new node — O(n) for a singly-linked list without a tail pointer, O(1) if a tail reference is maintained.
Pseudocode
function insertAtTail(head, value): newNode = new Node(value) // allocate if head == null: return newNode // empty list edge case current = head while current.next != null: current = current.next // walk to last node current.next = newNode // append return head // O(n) traversal + O(1) link
Maintain a tail pointer for O(1) append:
  • Java’s LinkedList keeps both head and tail references internally.
  • If you only keep head, every append is O(n).
  • Adding a single tail field drops append to O(1) — a trade-off of one extra reference for a massive improvement in append-heavy workloads.
Insert at Middle
Traverses to the node before the target position, then rewires pointers to splice in a new node — O(n) to find the position, O(1) to link.
Pseudocode
function insertAt(head, index, value): if index == 0: return insertAtHead(head, value) current = head for i from 0 to index - 2: current = current.next // walk to node before target newNode = new Node(value) newNode.next = current.next // point new node to successor current.next = newNode // wire predecessor to new node return head // O(n) find + O(1) splice
Insert at Middle — insert 99 between nodes 12 and 25
BEFORE [7] → [12] → [25] → [41] → null 7 • 12 • prev 25 • 41 ∅ AFTER [7] → [12] → [99] → [25] → [41] → null 7 • 12 • 99 • new 25 • 41 ∅ ① newNode.next = prev.next ② prev.next = newNode
Wire new node first, then previous:
  • Set newNode.next = prev.next before prev.next = newNode.
  • Reversing this order disconnects the rest of the list because prev.next would already point to newNode before you capture the old successor.
Delete by Value
Finds a node with a given value and removes it by re-linking its predecessor’s next pointer to its successor — O(n) search, O(1) unlink.
Pseudocode
function deleteByValue(head, target): if head == null: return null if head.value == target: return head.next // delete head itself current = head while current.next != null: if current.next.value == target: current.next = current.next.next // bypass target node return head current = current.next return head // O(n) scan + O(1) unlink
Delete by Value — remove node with value 12
BEFORE [7] → [12] → [25] → [41] → null 7 • 12 • delete 25 • 41 ∅ AFTER [7] → [25] → [41] → null 7 • prev.next = prev.next.next 25 • 41 ∅
Handle head deletion separately:
  • If the target value is in the head node, there is no predecessor to re-link.
  • You must check the head first and return head.next directly — this is the most common edge case missed in interview solutions.
Cycle Detection (Floyd’s)
Two pointers — slow moves one step, fast moves two. If they meet, a cycle exists. O(n) time, O(1) space.
Pseudocode
function hasCycle(head): slow = head fast = head while fast != null and fast.next != null: slow = slow.next // one step fast = fast.next.next // two steps if slow == fast: return true // pointers met — cycle exists return false // fast hit null — no cycle // O(n) time, O(1) space
Floyd’s Cycle Detection — slow and fast pointers
Cycle: tail points back to node B 1 2 cycle entry 3 4 meet! 5 tail.next → cycle entry (back-edge) slow: 1 step/iter fast: 2 steps/iter If cycle exists, fast laps slow and they meet inside the loop.
Why fast catches slow inside the cycle:
  • Once both pointers are inside a loop of length L, fast closes the gap by 1 node per iteration.
  • After at most L more iterations they collide.
  • This guarantees O(n) detection without using a HashSet (which costs O(n) extra space).
Common Mistake: Losing the reference to the rest of the list during insertion. When you write prev.next = newNode before setting newNode.next = prev.next, the original successor is orphaned — the GC collects it and every node after it. Always capture or assign the successor first, then re-link the predecessor. This one-line ordering bug causes silent data loss that feels like a “random” list truncation.
04
Section Four · Variant

Doubly Linked List

A doubly linked list adds a prev pointer to each node — giving every node references to both its predecessor and successor. This single addition transforms deletion from O(n) to O(1) when you hold the node directly, because you no longer need to traverse to find the predecessor. Java’s LinkedList<T> is a doubly linked list with maintained head and tail references — that is why addFirst(), addLast(), removeFirst(), and removeLast() are all O(1).

Node anatomy — singly vs doubly linked
Singly linked node data next 2 fields per node Doubly linked node prev data next 3 fields per node — bidirectional traversal ✓ Delete with node ref: O(1) ✓ Traverse backward ✗ Extra 8 bytes per node
Insert — 4 pointer updates
Pseudocode
function insertAfter(node, value): newNode = new Node(value) newNode.prev = node // ① new → predecessor newNode.next = node.next // ② new → successor if node.next != null: node.next.prev = newNode // ③ successor ← new node.next = newNode // ④ predecessor → new // O(1) — no traversal needed
Delete — O(1) with node reference
Delete node B — two pointer updates, no traversal
BEFORE ...↔ A ↔ B ↔ C ↔... ← A → ← B → delete this node ← C → AFTER ...↔ A ↔ C ↔... ← A → ① B.prev.next = B.next ← C → ② B.next.prev = B.prev
Pseudocode
function deleteNode(node): node.prev.next = node.next // ① bypass forward if node.next != null: node.next.prev = node.prev // ② bypass backward // O(1) — no traversal, no predecessor search
This is why Java’s LinkedList has O(1) removeFirst/removeLast:
  • Because it is doubly linked with head and tail references, removing from either end requires only 2 pointer updates.
  • An iterator’s remove() is also O(1) — it holds the node directly and can unlink it without scanning.
05
Section Five · Variant

Circular Linked List

In a circular linked list, the tail node’s next pointer points back to the head instead of null — forming a ring with no terminator. Traversal cannot check for null; it must detect when it has returned to the starting node. This structure appears wherever data cycles endlessly: round-robin task schedulers in operating systems, multiplayer board game turn management, music playlist loops, and the classic Josephus elimination problem.

Circular structure — tail.next points to head
head A • B • C • tail D • tail.next → head (no null — loop forever)
Traversal — the null check breaks
Pseudocode — Singly (wrong for circular)
// ✗ WRONG for circular — runs forever (no null exists) current = head while current != null: // never triggers! process(current.value) current = current.next
Pseudocode — Circular (correct)
// ✓ CORRECT — stop when we return to head if head == null: return current = head do: process(current.value) current = current.next while current != head // O(n) — one full rotation
Traversal termination — stop when current returns to head
A start here B C D current == head → STOP do-while loop: process first, then check if we returned to start
Use do-while, not while:
  • A while (current != head) loop with current starting at head would never execute the body (the condition is false immediately).
  • The correct pattern is do { ... } while (current != head) starting from head, or start from head.next with a regular while.
  • Missing this causes either zero iterations or infinite loops — both common interview mistakes.
06
Section Six · Implementation

Build It Once

Build this from scratch once — it makes the mechanics concrete. In any real project or interview, reach for the built-in (Section 05).

Java — Linked List core mechanics
// Build once to understand the mechanics — use LinkedList in practice. public class SinglyLinkedList { private Node head; private int size; private static class Node { int value; Node next; Node(int v) { value = v; } } // O(1) — redirect one pointer, no traversal public void addFirst(int value) { Node n = new Node(value); n.next = head; // point to old head head = n; // swing head to new node size++; } // O(n) — must walk to predecessor public void addAt(int index, int value) { if (index == 0) { addFirst(value); return; } Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next; Node n = new Node(value); n.next = prev.next; // wire new → successor prev.next = n; // wire predecessor → new size++; } // O(n) — scan for target, bypass it public boolean remove(int value) { if (head == null) return false; if (head.value == value) { head = head.next; size--; return true; } Node cur = head; while (cur.next != null) { if (cur.next.value == value) { cur.next = cur.next.next; // bypass size--; return true; } cur = cur.next; } return false; } }
07
Section Seven · Java Built-in

Use It In Java

IN JAVA
Use LinkedList<T> — or ArrayDeque<T> when you only need stack/queue operations
Import import java.util.LinkedList;
Method Complexity Note
addFirst(value) O(1) Prepend — doubly-linked, no traversal
addLast(value) O(1) Append — tail pointer maintained internally
add(index, value) O(n) Walk to position, then splice — O(n) find + O(1) link
get(index) O(n) Must traverse — no address formula
removeFirst() O(1) Unlink head node
removeLast() O(1) Unlink tail — doubly-linked gives prev pointer
remove(value) O(n) Scans for first occurrence, bypasses it
contains(value) O(n) Linear scan — no fast lookup
size() O(1) Stored as a field — not counted
⚠ Gotcha: Java’s LinkedList implements both List and Deque, so it has get(index) — but calling it in a loop gives O(n²) total because each call walks from the nearest end. If you need indexed access, use ArrayList. If you need stack/queue ops, prefer ArrayDeque which has better cache locality and lower per-element overhead.
Choose Use LinkedList only when you need O(1) insertions and deletions at known iterator positions (e.g. LRU cache internals, scheduling queues with removals). For pure stack/queue behaviour, ArrayDeque is faster due to contiguous memory. For random access, use ArrayList.
08
Section Eight · Decision Guide

Pick The Right Structure

Decision Flowchart
Need frequent insert/delete at known positions? Yes No Hold reference to the node? Yes LinkedList<T> O(1) insert/delete at reference No ArrayDeque stack/queue — better cache Need fast index access? Yes ArrayList<T> O(1) random access No HashMap<K,V> key→value O(1) lookup
Comparison Table
Structure Access Insert (middle) Delete (middle) Best For
LinkedList ← this O(n) O(1)* O(1)* Iterator-based insert/delete, LRU cache
ArrayList O(1) O(n) O(n) Random access, iteration, sorting
ArrayDeque O(n) O(1) head/tail O(1) head/tail Stack, queue, BFS/DFS
HashMap O(1) avg O(1) avg O(1) avg Key→value lookup, frequency count

* O(1) when you already hold a reference/iterator to the preceding node — finding that position is O(n).

09
Section Nine · Practice

Problems To Solve

Two patterns dominate linked-list interview problems: two-pointer (fast/slow to detect cycles, find midpoints, or identify the k-th from end) and pointer manipulation (reversing sublists, merging sorted lists, or partitioning). Look for phrases like "middle node", "cycle", "reverse", "merge", or "reorder" — they signal one of these patterns.

Difficulty Pattern Problem Key Insight
Easy two-pointer Reverse Linked List Keep three pointers — prev, current, next. At each step: save next, point current back to prev, advance both. One pass, O(1) space.
Easy two-pointer Linked List Cycle Floyd’s: slow moves 1, fast moves 2. If they meet, a cycle exists. Fast reaches null means no cycle. O(n) time, O(1) space.
Easy two-pointer Merge Two Sorted Lists Dummy head + tail pointer. Compare heads of both lists, append the smaller to tail, advance that list. One pass, O(1) extra space.
Medium two-pointer Remove Nth Node From End Two pointers n+1 apart — when the leader hits null, the follower is at the node before the target. One pass instead of two.
Medium pointer-manipulation Reorder List Find middle (slow/fast), reverse second half, interleave the two halves. Three classic sub-problems composed into one.
Hard pointer-manipulation Merge k Sorted Lists Min-heap of size k — always pop the smallest head, push its next. O(n log k) total. Alternatively, divide-and-conquer pairwise merge.
Interview Pattern:
  • Fast/slow pointer solves roughly 60% of linked-list problems.
  • When you see "middle", "cycle", or "k-th from end" — deploy two pointers at different speeds.
  • For "reverse" or "reorder" problems, the pattern is always: identify a sublist, reverse it in place with prev/curr/next, and re-attach the ends.

→ See all Linked List problems with full solutions