Linked Lists — Complete DSA Linked List Theory

Learning Progress. Work top to bottom: theory & fundamentals → operations → the interactive visualizer → pointer patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a Linked List?

A Linked List is a linear data structure where elements (nodes) are stored at scattered memory locations and connected by pointers. Each node holds data plus a reference to the next node.

Unlike arrays, nodes are not contiguous. There is no index arithmetic: to reach the k-th node you must walk the chain from the head, making access O(n). The payoff is O(1) insert/delete once you hold the node, with no shifting.

Node layout

// Singly linked node
struct Node {
int data;
Node* next;
};

// head → [10|•]→[20|•]→[30|/]
// each • is a pointer, / is nullptr

Why Linked Lists? When you insert/delete constantly and rarely index randomly, linked lists win: no reallocation, no bulk shifting, O(1) splice. They underpin adjacency lists, LRU caches, the free lists in allocators, and undo/redo history.

Linked list structure — nodes, pointers, and traversal

1Head pointer: the only entry point. Lose it and the whole list leaks. Always keep head safe before mutating.

2Non-contiguous memory: nodes live anywhere on the heap; the next pointer stitches them together. No cache locality, so traversal is slower than arrays.

3O(1) insert/delete: once you hold the predecessor, rewiring two pointers inserts or removes a node. No shifting like arrays.

4O(n) access & search: no index math. To reach position k, walk k links from the head.

5Extra memory: every node pays for a pointer (8 bytes on 64-bit). Doubly linked lists pay for two.

Types of Linked List

→

Singly Linked

Each node points only to the next. One-way traversal from head to tail.

Use: stacks, simple queues, adjacency lists.

insert/delete O(1)* · access O(n)

⇄

Doubly Linked

Each node has prev and next. Traverse both directions, delete a node in O(1) given only that node.

Use: LRU cache, deque, browser history.

extra pointer per node

↺

Circular

Tail's next points back to head (singly or doubly). No null terminator.

Use: round-robin scheduling, ring buffers.

watch for infinite loops

Terminology

Node

The unit of storage: data plus one or more pointers to neighbouring nodes.

Head

Pointer to the first node. The single handle to the whole list.

Tail

The last node; its next is nullptr (or head, if circular).

Next / Prev

Pointers linking a node to its successor (and predecessor in doubly lists).

Dummy / Sentinel

A placeholder node before the head that removes edge cases when inserting/deleting at the front.

Fast / Slow Pointers

Two traversal speeds used to find the middle, detect cycles, or find the k-th from end.

Cycle

When some node's next points to an earlier node, forming a loop. Detected with Floyd's algorithm.

In-place Reversal

Reversing link directions using three pointers (prev, curr, next) in O(1) space.

Splice

Rewiring pointers to insert or remove nodes without moving data.

Complexity Summary

Access / Search

O(n)

Walk from the head; no random access.

Insert at Head

O(1)

Point new node at head, move head.

Insert at Tail

O(1)†

O(1) with a tail pointer, else O(n).

Insert at Index

O(n)

O(n) to reach the spot, O(1) to splice.

Delete (given node)

O(1)

Doubly linked, or with the predecessor.

Reverse

O(n)

Single pass, O(1) extra space.

Traverse

O(n)

Visit each node once, cache-unfriendly.

Space

O(n)

n nodes plus one pointer each.

Cycle Detect

O(n)

Floyd's tortoise & hare, O(1) space.

Array vs Linked List

Aspect	Array	Linked List
Memory	Contiguous	Scattered (heap)
Random access	O(1)	O(n)
Insert/delete at front	O(n)	O(1)
Cache locality	Excellent	Poor
Memory overhead	None	Pointer per node
Resizing	Reallocate + copy	Grow node by node
Use case	Indexing, scanning	Frequent splice, unknown size

Advantages & Disadvantages

Advantages

O(1) insertion/deletion at the front (and anywhere given the node).
Grows and shrinks one node at a time — no reallocation.
No wasted capacity; size is exactly the node count.
Splicing/merging lists is pointer rewiring, not copying.
Foundation for stacks, queues, deques, adjacency lists, LRU caches.

Disadvantages

No random access — reaching index k is O(n).
Poor cache locality; traversal is slower than arrays.
Extra memory for pointers (8+ bytes per node).
Reverse traversal impossible in singly linked lists.
Pointer bugs: dangling pointers, leaks, lost heads.

C++ STL Implementation

linked_list.cpp · Singly linked list operations

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

// Insert at head — O(1)
Node* insertHead(Node* head, int v) {
    Node* node = new Node(v);
    node->next = head;
    return node; // new head
}

// Insert at index — O(n)
Node* insertAt(Node* head, int idx, int v) {
    if (idx == 0) return insertHead(head, v);
    Node* cur = head;
    for (int i = 0; i < idx - 1 && cur; i++) cur = cur->next;
    Node* node = new Node(v);
    node->next = cur->next;
    cur->next = node;
    return head;
}

// Delete first node with value — O(n)
Node* deleteVal(Node* head, int v) {
    if (!head) return head;
    if (head->data == v) { Node* t = head->next; delete head; return t; }
    Node* cur = head;
    while (cur->next && cur->next->data != v) cur = cur->next;
    if (cur->next) { Node* t = cur->next; cur->next = t->next; delete t; }
    return head;
}

// Traverse — O(n)
void print(Node* head) {
    for (Node* c = head; c; c = c->next) cout << c->data << " -> ";
    cout << "null\n";
}

list_stl.cpp · std::list & std::forward_list

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> dll = {10, 20, 30};   // doubly linked
    dll.push_front(5);              // O(1)
    dll.push_back(40);              // O(1)
    auto it = dll.begin(); ++it;
    dll.insert(it, 15);            // O(1) given iterator
    dll.erase(dll.begin());        // O(1)

    forward_list<int> sll = {1, 2, 3}; // singly linked
    sll.push_front(0);              // O(1)
    sll.reverse();                  // O(n)

    for (int x : dll) cout << x << " ";
    return 0;
}

Interactive Linked List Visualization

Node Current Processing Visited / Done Target / Slow Fast

Idle

Current operation details

Operation

—

Current node

—

Pointer moves

Steps

taken

Comparisons

checks

Pointer ops

rewires

Length

nodes

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — build your own operation

List: Value/Index:

✓ Done

Speed

Step-by-step operation log

Step	Current	Value	Action	List State	Ptr ops
Run a scenario to populate the log.

Pointer Patterns

Fast & Slow Pointers (Floyd). Advance slow one node and fast two per step. If they meet, there's a cycle. When fast hits the end, slow sits on the middle. Also finds the k-th node from the end by offsetting the pointers.

patterns.cpp · Reverse, middle, cycle

// Reverse in-place — O(n) time, O(1) space
Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* nxt = head->next;
        head->next = prev;   // flip link
        prev = head;
        head = nxt;
    }
    return prev;            // new head
}

// Middle node (slow/fast) — O(n)
Node* middle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    return slow;
}

// Detect cycle (Floyd) — O(n) time, O(1) space
bool hasCycle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Common mistakes. Losing the head before you finish rewiring, forgetting to save next before flipping a link (you'll orphan the rest of the list), off-by-one when finding the middle of an even-length list, and not handling the empty/single-node list in every operation.

Cheat Sheet

Operation	Time	Space	Notes
Access k-th	O(n)	O(1)	Walk from head, no index math
Search	O(n)	O(1)	Linear scan of the chain
Insert head	O(1)	O(1)	Rewire two pointers
Insert tail	O(1)†	O(1)	O(1) with tail pointer
Insert at index	O(n)	O(1)	Reach spot, then splice
Delete node	O(1)	O(1)	Given node (doubly) / predecessor
Reverse	O(n)	O(1)	Three-pointer flip
Detect cycle	O(n)	O(1)	Floyd's tortoise & hare
Merge two sorted	O(n+m)	O(1)	Splice with dummy head

Learning Roadmap

Node & Pointer Basics

Build a node struct, link three nodes by hand, traverse and print. Understand head vs tail.

~2 hours

Core Operations

Insert head/tail/index, delete by value/index, search. Handle empty and single-node cases.

~3 hours

Reversal & Dummy Nodes

In-place iterative reversal, recursive reversal, and using a sentinel to kill edge cases.

~3 hours

Fast/Slow Pointers

Middle node, cycle detection, cycle start, k-th from end, palindrome check.

~4 hours

Doubly & Circular

Bidirectional traversal, O(1) delete, circular buffers, and the LRU cache pattern.

~3 hours

Hard Problems

Merge k sorted lists, reverse in groups of k, copy list with random pointer, flatten multilevel.

~4 hours

Revision Notes

Always save next first. Before flipping any link, store next = curr->next, or you lose the rest of the list.

Dummy head kills edge cases. A sentinel before the head means front-insert/delete uses the same code as the middle. Return dummy.next at the end.

Two pointers, one pass. Most "k-th from end", "middle", "cycle", and "palindrome" problems reduce to fast/slow pointers with O(1) space.

Cycle detection. If fast and slow meet, reset one pointer to head and advance both one step; they meet at the cycle's start.

Interview Preparation

Reverse a Linked List

Iterative three-pointer flip (prev, curr, next) in O(n)/O(1). Recursive version returns the new head from the tail up.

Pointers

Detect & Find Cycle Start

Floyd's algorithm. After meeting, reset one pointer to head; both advance one step and meet at the entry node.

Fast/Slow

Merge Two Sorted Lists

Dummy head, compare fronts, splice the smaller each time. O(n+m), O(1).

Dummy Node

Remove N-th Node From End

Advance fast pointer n steps, then move both until fast hits the end. Delete slow's next.

Fast/Slow

Linked List Palindrome

Find the middle, reverse the second half, compare halves. O(n)/O(1).

Reverse

Reverse in Groups of K

Reverse each k-block iteratively, wiring group tails to the next group's new head.

Hard

Practice Problems

EasyReverse Linked ListPointers

EasyMerge Two Sorted ListsDummy Node

EasyLinked List CycleFast/Slow

EasyMiddle of the Linked ListFast/Slow

EasyPalindrome Linked ListReverse

MediumRemove Nth Node From EndFast/Slow

MediumAdd Two NumbersCarry

MediumOdd Even Linked ListRewire

MediumCopy List with Random PointerHash / Interleave

MediumLRU CacheDoubly + Hash

HardMerge k Sorted ListsHeap

HardReverse Nodes in k-GroupReverse

Key Takeaways

🔗Fundamentals: nodes scattered in memory, linked by pointers. O(1) splice, O(n) access. The mirror image of arrays.

🏃Fast/slow pointers: the single most reused pattern — middle, cycle, cycle start, k-th from end, palindrome, all in one pass with O(1) space.

↩️Reversal: three pointers, save next before flipping. Recursion returns the new head from the tail.

🛡️Dummy nodes: a sentinel before the head erases front-of-list edge cases in insert, delete, and merge.

💼Interview reality: linked lists test pointer discipline more than cleverness. Draw the boxes, move one pointer at a time, verify empty/single-node cases.