Linked List

A linked list is a linear data structure made of nodes, where each node holds a value and a reference (pointer) to the next node. Unlike arrays, elements aren't stored contiguously in memory, which makes insertion and deletion at arbitrary positions much cheaper — at the cost of O(n) random access.

Singly vs Doubly Linked Lists

Singly Linked List — each node points only to the next node. Simple and memory-efficient, but traversal is one-directional.
Doubly Linked List — each node has both next and prev pointers, allowing traversal in both directions at the cost of extra memory per node.
Circular Linked List — the last node points back to the head instead of null, useful for round-robin scheduling and buffering.

Common Techniques

Fast & Slow Pointers — one pointer moves twice as fast as the other. Used for cycle detection (Floyd's algorithm) and finding the middle node.
Dummy Head Node — an auxiliary node placed before the real head simplifies edge cases when inserting/removing at the start of the list.
In-Place Reversal — reverse pointer directions iteratively using three pointers (prev, curr, next) without extra space.
Recursion — many linked list problems (reversal, merging) have elegant recursive solutions, trading O(n) stack space for simplicity.

Time & Space Complexity

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at head	O(n)	O(1)
Insert/delete at known node	O(n)	O(1)
Space overhead	O(n)	O(n) + pointer per node

Illustration: Node Chain with Pointers

C++ Example: Reverse a Singly Linked List

reverse_linked_list.cpp

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;
}

Python Example: Common Linked List Patterns

linked_list_patterns.py

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


# 1. Detect a cycle using fast & slow pointers (Floyd's algorithm)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False


# 2. Find the middle node using fast & slow pointers
def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


# 3. Merge two sorted linked lists using a dummy head
def merge_two_lists(l1, l2):
    dummy = ListNode()
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

Quiz

You want to detect whether a linked list contains a cycle without using extra space. Which technique is best suited?

A. Binary Search
B. Fast & Slow Pointers
C. Hash Map of visited nodes
D. Sorting

Practice on LeetCode

Once you're comfortable with the concepts above, try solving these problems to reinforce your understanding:

Easy 206. Reverse Linked List — classic in-place reversal with three pointers.
Easy 21. Merge Two Sorted Lists — dummy head node technique.
Medium 142. Linked List Cycle II — fast & slow pointers to find the cycle's start.
Medium 19. Remove Nth Node From End of List — two pointers with a gap of n, plus a dummy head.
Medium 2. Add Two Numbers — simulate digit-by-digit addition across two lists.

← Back to DSA