Linked List Complete Guide

Data Structure • medium

Linked lists chain nodes via pointers instead of storing values in contiguous memory.

They shine for local insert/delete operations once node references are known.

Most linked-list problems test pointer movement discipline rather than raw complexity memorization.

Typical Complexity Baseline

Metric	Value
Traversal	`O(n)`
insert/delete at node	`O(1)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Linked list node insertion in O(1)

Each node points to the next. Inserting between two nodes only rewires two pointers.

Step 1/13Linked list: 3 → 7 → 9 → 5 → 2. Each node holds a value and a next pointer.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Introduction to Linked List

Channel: Neso Academy

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Node

What it is Container with value and next pointer (and optional prev pointer).

Why it matters Node is a required building block for understanding how Linked List stays correct and performant on large inputs.

Head

What it is First node reference.

Why it matters Head is a required building block for understanding how Linked List stays correct and performant on large inputs.

Tail

What it is Last node reference for O(1) append in doubly-linked variants.

Why it matters Tail is a required building block for understanding how Linked List stays correct and performant on large inputs.

Sentinel node

What it is Dummy node used to simplify edge cases at head/tail.

Why it matters Sentinel node is a required building block for understanding how Linked List stays correct and performant on large inputs.

Pointer rewiring

What it is Updating next/prev pointers safely during operations.

Why it matters Pointer rewiring is a required building block for understanding how Linked List stays correct and performant on large inputs.

Singly linked

What it is Each node points only to next node.

Why it matters Each node points only to next node. In Linked List, this definition helps you reason about correctness and complexity when inputs scale.

Doubly linked

What it is Each node points to both prev and next nodes.

Why it matters Each node points to both prev and next nodes. In Linked List, this definition helps you reason about correctness and complexity when inputs scale.

Cycle

What it is Node pointers eventually loop back to an earlier node.

Why it matters Node pointers eventually loop back to an earlier node. In Linked List, this definition helps you reason about correctness and complexity when inputs scale.

Fast/slow pointers

What it is Two-speed traversal trick for cycle/middle detection.

Why it matters Two-speed traversal trick for cycle/middle detection. In Linked List, this definition helps you reason about correctness and complexity when inputs scale.

In-place reversal

What it is Reverse list by pointer rewiring without extra list allocation.

Why it matters Reverse list by pointer rewiring without extra list allocation. In Linked List, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/13

Linked list: 3 → 7 → 9 → 5 → 2. Each node holds a value and a next pointer.

Step 2/13

Traversal step 1: start at head, cursor on node(3).

Step 3/13

cursor = cursor.next → node(7).

Step 4/13

cursor.next → node(9).

Step 5/13

cursor.next → node(5). Each pointer hop is one cache miss that's why traversal is O(n) but slower than an array of equal length.

Step 6/13

Insert 8 after node(9). First find the predecessor we already have it: node(9) at index 2.

Step 7/13

Allocate a new node(8) somewhere in the heap (drawn separately).

Step 8/13

new.next = predecessor.next = node(5).

Step 9/13

predecessor.next = new. Splice complete in O(1).

Step 10/13

Logical view: 3 → 7 → 9 → 8 → 5 → 2.

Step 11/13

Now delete node(8). Find its predecessor node(9) at index 2.

Step 12/13

predecessor.next = node(8).next = node(5). node(8) is now unreachable.

Step 13/13

List restored: 3 → 7 → 9 → 5 → 2. Insert and delete are both O(1) once the predecessor is held.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Array

Choose this when Choose linked list for frequent inserts/deletes in middle by node reference.

Tradeoff Random access by index is O(n).

vs. Deque

Choose this when Choose linked list when you need custom node-level operations.

Tradeoff Deque is simpler and often faster for plain queue/stack usage.

vs. Hash Map

Choose this when Use together in LRU-like designs where order + key lookup are needed.

Tradeoff Linked list alone cannot do fast key lookup.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Linux kernel

Kernel subsystems use intrusive linked lists for flexible insertion/removal in scheduling and memory metadata.

Takeaway Pointer-based structures are practical in systems-level code.

Redis

Earlier list internals and some modules rely on linked-node structures for efficient local edits.

Takeaway Linked lists remain relevant in core infrastructure components.

Database engines

Buffer and lock manager internals often chain metadata objects via linked pointers.

Takeaway Node-level updates are useful when topology changes frequently.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Iterative pointer rewiring with previous/current/next references.

Complexity: Time O(n), Space O(1)

Reverse singly linked list

Language

type ListNode = { value: number; next: ListNode | null }

function reverseList(headNode: ListNode | null): ListNode | null {
  let previousNode: ListNode | null = null
  let currentNode = headNode

  while (currentNode) {
    const nextNode = currentNode.next
    currentNode.next = previousNode
    previousNode = currentNode
    currentNode = nextNode
  }

  return previousNode
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Losing references while rewiring pointers during reverse/delete.
Missing edge cases for empty list or single-node list.
Infinite loops from accidental cycle creation.
Not using dummy head causing complex branch-heavy code.
Forgetting to update tail in append/remove flows.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Draw pointers on paper before coding to avoid losing references during rewiring.
Use dummy head nodes to remove special-case branches at list start.
Fast/slow pointers solve cycle and middle-node problems elegantly.
Always test null head and single-node list before larger examples.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Stable insert/delete without shifting entire tail elements.
Useful in queues, LRU caches, and free-list allocators.
Helps build pointer intuition needed for trees and graphs.

LeetCode-specific tips (pattern-identification signals)

Identification signal: input is node-pointer based and operations emphasize rewiring next references.
Identification signal: random index access is unavailable but insertion/deletion at known node is cheap.
Cycle detection, middle node, and in-place reversal cues strongly suggest linked-list pointer techniques.
For Linked List questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Reverse Linked List	Easy	`O(n)`
2	Merge Two Sorted Lists	Easy	`O(n+m)`
3	Linked List Cycle	Easy	`O(n)`
4	Remove Nth Node From End	Medium	`O(n)`
5	Reorder List	Medium	`O(n)`
6	Sort List	Medium	`O(n log n)`
7	Copy List with Random Pointer	Medium	`O(n)`
8	Reverse Nodes in k-Group	Hard	`O(n)`
9	Merge k Sorted Lists	Hard	`O(n log k)`
10	LRU Cache	Hard	`O(1)` ops