🔗 Linked List - Dynamic Data Structure

🟡 Intermediate Linear DS 75 min read

🎯 What is a Linked List?

A Linked List is a linear data structure where elements (called nodes) are stored in non-contiguous memory locations. Each node contains data and a pointer/reference to the next node. Unlike arrays, linked lists can grow and shrink dynamically.

🔗 Visual Structure

[Head] → [10|*] → [20|*] → [30|*] → [40|null]
          Node       Node       Node       Node
          data+next  data+next  data+next  data+next (null = end)

📂 Types of Linked Lists

Singly Linked List

Each node has data + next pointer. Traversal only forward.

[A|*]→[B|*]→[C|*]→null

Doubly Linked List

Each node has data + next + prev pointers. Bidirectional traversal.

null←[A|*|*]⇄[B|*|*]⇄[C|*|*]→null

Circular Linked List

Last node points back to first. No null references.

[A|*]→[B|*]→[C|*]→[A]↺

Circular Doubly

Combination: doubly linked + circular.

[A|*|*]⇄[B|*|*]⇄[C|*|*]⇄[A]↺

💻 PHP Implementation - Singly Linked List

<?php
class Node {
    public int $data;
    public ?Node $next;

    public function __construct(int $data) {
        $this->data = $data;
        $this->next = null;
    }
}

class LinkedList {
    private ?Node $head = null;
    private int $size = 0;

    // Insert at beginning - O(1)
    public function insertFirst(int $data): void {
        $newNode = new Node($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
        $this->size++;
    }

    // Insert at end - O(n)
    public function insertLast(int $data): void {
        $newNode = new Node($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
        $this->size++;
    }

    // Delete first node - O(1)
    public function deleteFirst(): ?int {
        if ($this->head === null) return null;
        $data = $this->head->data;
        $this->head = $this->head->next;
        $this->size--;
        return $data;
    }

    // Delete by value - O(n)
    public function delete(int $data): bool {
        if ($this->head === null) return false;
        if ($this->head->data === $data) {
            $this->head = $this->head->next; $this->size--;
            return true;
        }
        $current = $this->head;
        while ($current->next !== null && $current->next->data !== $data) {
            $current = $current->next;
        }
        if ($current->next !== null) {
            $current->next = $current->next->next;
            $this->size--; return true;
        }
        return false;
    }

    // Search - O(n)
    public function search(int $data): bool {
        $current = $this->head;
        while ($current !== null) {
            if ($current->data === $data) return true;
            $current = $current->next;
        }
        return false;
    }

    // Reverse (in-place) - O(n)
    public function reverse(): void {
        $prev = null; $current = $this->head;
        while ($current !== null) {
            $next = $current->next; // Save next
            $current->next = $prev; // Reverse link
            $prev = $current;       // Move prev forward
            $current = $next;       // Move current forward
        }
        $this->head = $prev;
    }

    // Detect cycle (Floyd's Algorithm) - O(n)
    public function hasCycle(): bool {
        $slow = $this->head; $fast = $this->head;
        while ($fast !== null && $fast->next !== null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
            if ($slow === $fast) return true;
        }
        return false;
    }

    // Find middle (Tortoise & Hare) - O(n)
    public function findMiddle(): ?int {
        $slow = $this->head; $fast = $this->head;
        while ($fast !== null && $fast->next !== null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        return $slow?->data;
    }

    // Display - O(n)
    public function display(): void {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " → ";
            $current = $current->next;
        }
        echo "null\n";
    }

    public function getSize(): int { return $this->size; }
}

// Usage
$list = new LinkedList();
$list->insertLast(10);
$list->insertLast(20);
$list->insertLast(30);
$list->insertFirst(5);
$list->display(); // 5 → 10 → 20 → 30 → null

$list->reverse();
$list->display(); // 30 → 20 → 10 → 5 → null

echo "Middle: " . $list->findMiddle(); // 20 (or 10 for even)

📊 Operations Complexity

Operation	Singly LL	Doubly LL	Array	Winner
Access by Index	O(n)	O(n)	O(1)	Array
Insert at Head	O(1)	O(1)	O(n)	LL
Insert at Tail	O(n)	O(1)*	O(1)	LL/Array
Delete at Head	O(1)	O(1)	O(n)	LL
Search	O(n)	O(n)	O(n)	Tie
Memory per element	Data + 1 ptr	Data + 2 ptrs	Data only	Array

📝 Reverse Linked List - Dry Run

Initial: 1 → 2 → 3 → null

Iter	prev	current	next	After reverse link
Start	null	1	-	-
1	1	2	2	null ← 1
2	2	3	3	null ← 1 ← 2
3	3	null	null	null ← 1 ← 2 ← 3

Result: 3 → 2 → 1 → null ✅

🐘 PHP SPL Linked List

// PHP provides SplDoublyLinkedList (doubly linked list)
$list = new SplDoublyLinkedList();
$list->push('A');          // Add to end
$list->push('B');
$list->unshift('X');       // Add to beginning
$list->add(1, 'Y');        // Insert at index 1

foreach ($list as $value) {
    echo $value . ' ';     // X, Y, A, B
}

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
foreach ($list as $value) {
    echo $value . ' ';     // B, A, Y, X (reverse/LIFO)
}

💼 Interview Questions

Array: fast random access, cache-friendly. Linked List: fast insertions/deletions at ends, dynamic size. Use array when you need random access; use LL when you do many inserts/deletes.

Floyd's Cycle Detection (Tortoise & Hare): Use two pointers - slow moves 1 step, fast moves 2 steps. If they meet, cycle exists. O(n) time, O(1) space. To find cycle start: reset one pointer to head, move both at same speed until they meet.

Use a Min Heap. Push head of each list. Pop smallest, add to result, push next of popped node. O(N log K) where N = total nodes, K = number of lists. Much better than O(N*K) pairwise merging.

📝 Quick Quiz

📋 Cheat Sheet

Insert Head	O(1)	Create node, point to old head
Insert Tail	O(n)	Traverse to end, attach (O(1) with tail pointer)
Delete Head	O(1)	Move head to next node
Reverse	O(n)	3-pointer technique (prev, curr, next)
Cycle Detection	O(n)	Floyd's Tortoise & Hare
Find Middle	O(n)	Slow/fast pointer

Previous: Recursion Next: Stack