Data Structure • medium

Linked List Complete Guide

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)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Introduction to Linked List

Channel: Neso Academy

Full video link:

https://www.youtube.com/watch?v=R9PTBwOzceo

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Linked List into one end-to-end execution flow.

Step 1

Node

Container with value and next pointer (and optional prev pointer).

Before

Head -> 4 -> 9 -> 2 -> null
Need node with value 9

→

After

Found node: 9
Traversal steps: 2

Transition

Move current = current.next

→Stop when current.value == 9

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

Step 2

Head

First node reference.

Before

Head -> 4 -> 9 -> 2 -> null
Insert 7 after node 9

→

After

Head -> 4 -> 9 -> 7 -> 2 -> null
Pointers rewired

Transition

newNode.next = node9.next

→node9.next = newNode

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

Step 3

Tail

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

Before

Head -> 4 -> 9 -> 7 -> 2 -> null
Delete node after 9

→

After

Head -> 4 -> 9 -> 2 -> null
Deletion complete

Transition

node9.next = node9.next.next

→Unlink removed node

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

Step 4

Sentinel node

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

Before

Head -> 1 -> 2 -> 3 -> null
Need reversed order

→

After

Head -> 3 -> 2 -> 1 -> null
List reversed in-place

Transition

Track prev/current/next

→Flip current.next to prev

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

How It Compares

vs Array

When to choose this: Choose linked list for frequent inserts/deletes in middle by node reference.

Tradeoff: Random access by index is O(n).

vs Deque

When to choose this: 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

When to choose this: Use together in LRU-like designs where order + key lookup are needed.

Tradeoff: Linked list alone cannot do fast key lookup.

Real-World Stories and Company Examples

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.

Implementation Guide

Iterative pointer rewiring with previous/current/next references.

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

Language

Reverse singly linked list

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
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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