Master Linked Lists Data Structure — Complete Guide

1. Introduction to Linked Lists

A Linked List is a fundamental linear data structure consisting of a sequence of Nodes. Unlike an array, where elements are packed sequentially in contiguous memory, linked list nodes are allocated dynamically at arbitrary locations on the memory heap.

Each individual node contains two vital components:

1. Data: The value or payload stored within the node (e.g. integer, string, object).
2. Next Pointer / Reference: A memory address pointer pointing directly to the subsequent node in the sequence.

+─────────────────────────────────────────────────────────────────────────────+
|                     SINGLY LINKED LIST MEMORY ARCHITECTURE                  |
+─────────────────────────────────────────────────────────────────────────────+

  Head Pointer (Address: 0x10A0)
      │
      ▼
 ┌──────────────┐      ┌──────────────┐      ┌──────────────┐
 │ Node 1       │      │ Node 2       │      │ Node 3       │
 ├──────────────┤      ├──────────────┤      ├──────────────┤
 │ Val: 10      │      │ Val: 20      │      │ Val: 30      │
 │ Next: 0x3F20 ┼─────>│ Next: 0x8C40 ┼─────>│ Next: NULL   │
 └──────────────┘      └──────────────┘      └──────────────┘
  (Heap: 0x10A0)        (Heap: 0x3F20)        (Heap: 0x8C40)

The first node in the sequence is termed the Head, and the terminal node points to NULL (or None), designating the end of the list.

2. Linked List vs Array: Deep Memory Comparison

Understanding the engineering trade-offs between arrays and linked lists is a staple of technical interviews.

+─────────────────────────────────────────────────────────────────────────────+
|                         ARRAY VS LINKED LIST IN RAM                         |
+─────────────────────────────────────────────────────────────────────────────+

 Array Memory (Contiguous):
 ┌─────────┬─────────┬─────────┬─────────┐
 │ [ 10 ]  │ [ 20 ]  │ [ 30 ]  │ [ 40 ]  │  <-- CPU pre-fetches entire block
 └─────────┴─────────┴─────────┴─────────┘      into L1/L2 cache (Fast!)
  Addr:1000 Addr:1004 Addr:1008 Addr:1012

 Linked List Memory (Scattered across Heap):
 ┌─────────┐             ┌─────────┐             ┌─────────┐
 │ 10|0x9B ┼────────────>│ 20|0x3C ┼────────────>│ 30|NULL │  <-- Pointer chasing
 └─────────┘             └─────────┘             └─────────┘      Cache misses!
  Addr:0x12               Addr:0x9B               Addr:0x3C

Direct Engineering Comparison:

3. Types of Linked Lists

1. Singly Linked List

Nodes contain a single next pointer. Traversal is unidirectional from head to tail.

2. Doubly Linked List (DLL)

Each node contains both a next and a prev pointer. Enables bidirectional traversal and O(1) deletion when given a direct reference to any internal node.

+─────────────────────────────────────────────────────────────────────────────+
|                         DOUBLY LINKED LIST (DLL)                            |
+─────────────────────────────────────────────────────────────────────────────+

 NULL <─── ┌───────┐ ⇄ ┌───────┐ ⇄ ┌───────┐ ⇄ ┌───────┐ ───> NULL
           │ Prev  │   │ Prev  │   │ Prev  │   │ Prev  │
           │ Val:1 │   │ Val:2 │   │ Val:3 │   │ Val:4 │
           │ Next  │   │ Next  │   │ Next  │   │ Next  │
           └───────┘   └───────┘   └───────┘   └───────┘
             Head                                Tail

3. Circular Linked List

The next pointer of the final node references the head node instead of NULL, creating a continuous ring. Ideal for round-robin CPU schedulers and circular media playlists.

4. Fundamental Pointer Operations

1. Insertion at the Head (O(1))

Step 1: Create newNode with value V.
Step 2: newNode.next = head
Step 3: head = newNode

2. Deletion of a Target Node (O(1) given prev pointer)

prev.next = targetNode.next
targetNode.next = null // Avoid memory leaks

3. The Dummy Head (Sentinel Node) Technique

In coding interviews, manipulating head nodes often requires edge-case logic (e.g. deleting the first node or merging into an empty list). A Dummy Head (a placeholder node whose next points to the real head) completely eliminates edge-case checks!

5. Multi-Language Implementations & Syntax

C++ (ListNode Definition & Reversal)

cpp
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

Java (ListNode Definition & Helper)

java
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}

Python (ListNode Definition)

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

JavaScript (ListNode Class)

javascript
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

6. Classic Interview Problems with Mathematical Proofs

Problem 1: Detect Cycle & Find Cycle Start (Floyd’s Tortoise & Hare)

Problem Statement: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

+─────────────────────────────────────────────────────────────────────────────+
|                     FLOYD'S CYCLE DETECTION MATHEMATICAL PROOF              |
+─────────────────────────────────────────────────────────────────────────────+

                  L (Distance from Head to Start)
         Head ─────────────────────────────────┐
                                               ▼
                                            [Node S] <── Cycle Entry
                                           /        \
                                     C - K           K (Meeting Point M)
                                           \        /
                                            [Node M]

 Let:
 - L = Distance from Head to Cycle entry point (Node S)
 - C = Total circumference / length of the cycle
 - K = Distance from cycle entry (S) to meeting point (M)

 When Slow and Fast meet at M:
   Distance traveled by Slow = L + K
   Distance traveled by Fast = L + K + n*C (where n >= 1 complete laps)

 Since Fast moves at 2x the speed of Slow:
   2 * (Distance of Slow) = Distance of Fast
   2 * (L + K) = L + K + n*C
   L + K = n*C
   L = n*C - K = (n - 1)*C + (C - K)

 Conclusion:
 Moving one pointer from Head and one pointer from Meeting Point (M) at
 identical 1x speed will cause them to meet EXACTLY at Cycle Entry (S)!

javascript
function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;
    let hasCycle = false;

    // Phase 1: Determine if cycle exists
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null;

    // Phase 2: Find cycle start node
    let ptr1 = head;
    let ptr2 = slow;

    while (ptr1 !== ptr2) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }

    return ptr1;
}

• Time Complexity: O(N) — Linear traversal.
• Space Complexity: O(1) — No extra memory or hash sets required!

Problem 2: Merge Two Sorted Lists

Problem Statement: Merge two sorted linked lists list1 and list2 into one sorted list and return its head.

python
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(-1)
    current = dummy
    
    p1, p2 = list1, list2
    while p1 and p2:
        if p1.val <= p2.val:
            current.next = p1
            p1 = p1.next
        else:
            current.next = p2
            p2 = p2.next
        current = current.next
        
    # Append any remaining elements
    current.next = p1 if p1 else p2
    
    return dummy.next

• Time Complexity: O(N + M) where N and M are lengths of the lists.
• Space Complexity: O(1) — In-place pointer rewiring.

7. Common Pitfalls & Interview Traps

1. Losing Pointer References Before Update: Writing curr = curr.next before preserving curr.next causes orphaned unreachable nodes and memory leaks in C/C++.
2. Infinite Loops on Cycles: Always check for fast !== null && fast.next !== null before accessing fast.next.next.
3. Null Pointer Exceptions on Empty Lists: Always validate head === null or use a Sentinel/Dummy node.
4. Modifying Head Directly: Unless intending to reassign the list start, always create an auxiliary traversal pointer (curr = head).

8. Frequently Asked Questions (FAQ)

Q1: Why use a Linked List over an Array if arrays provide O(1) lookups?

A: Linked lists provide O(1) insertions and deletions at arbitrary positions once a pointer to the node is held, without requiring element shifting or capacity reallocations.

Q2: How does Floyd's Tortoise and Hare algorithm guarantee detection?

A: In each step, the fast pointer closes the distance gap to the slow pointer by exactly 1 node (2 - 1 = 1). In a circular loop of length C, the fast pointer is mathematically guaranteed to meet the slow pointer within at most C iterations.

Q3: What is the purpose of a Sentinel / Dummy Head node?

A: A Dummy Head standardizes list operations by ensuring that every node (even the original first node) always has a valid preceding node (prev), eliminating special-case conditional branches.

Q4: Can we perform Binary Search on a Singly Linked List?

A: No. Binary Search requires O(1) random access to calculate the middle element (mid = (lo + hi)/2). In a linked list, finding the middle requires O(N) traversal, making binary search O(N log N), which is slower than simple linear search (O(N)).

Q5: How is an LRU Cache implemented using Linked Lists?

A: An LRU (Least Recently Used) cache uses a Doubly Linked List combined with a Hash Map. The hash map provides O(1) key-to-node lookup, while the doubly linked list enables O(1) node detachment and relocation to the head when accessed.

Q6: What is the space complexity of reversing a linked list recursively?

A: The recursive approach takes O(N) auxiliary space on the call stack due to recursion frames. The iterative 3-pointer method takes strictly O(1) space and is preferred in production code.