🔗 PHP Linked List Basics

Node Structure

In PHP we implement a linked list manually using a class:

class ListNode {
    public int $val;
    public ?ListNode $next;

    public function __construct(int $val = 0, ?ListNode $next = null) {
        $this->val  = $val;
        $this->next = $next;
    }
}

Singly Linked List (SLL)

Each node has val + next. Traversal is one direction only.

// Build: 1 → 2 → 3 → null
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);

// Traverse
$curr = $head;
while ($curr !== null) {
    echo $curr->val . ' ';
    $curr = $curr->next;
}
// Output: 1 2 3

Time: O(n) traversal | Space: O(n) storage

---

Doubly Linked List (DLL)

Each node has val, next, and prev.

class DListNode {
    public int $val;
    public ?DListNode $next;
    public ?DListNode $prev;

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

---

Key Operations

Insert at Head — O(1)

function insertAtHead(?ListNode $head, int $val): ListNode {
    $node = new ListNode($val);
    $node->next = $head;
    return $node; // new head
}

Insert at Tail — O(n)

function insertAtTail(?ListNode $head, int $val): ListNode {
    $node = new ListNode($val);
    if ($head === null) return $node;
    $curr = $head;
    while ($curr->next !== null) $curr = $curr->next;
    $curr->next = $node;
    return $head;
}

Delete by Value — O(n)

function deleteVal(?ListNode $head, int $val): ?ListNode {
    $dummy = new ListNode(0, $head);
    $prev  = $dummy;
    $curr  = $head;
    while ($curr !== null) {
        if ($curr->val === $val) {
            $prev->next = $curr->next;
            break;
        }
        $prev = $curr;
        $curr = $curr->next;
    }
    return $dummy->next;
}

Time: O(n) | Space: O(1)

---

Q1 — Count Nodes

🧠 How to Approach This

Step 1 — Recognize the pattern: Simple traversal counting each node.

Step 2 — Brute force (what NOT to do): Convert to array first — O(n) extra space.

Step 3 — Optimal insight: Single pointer walk, count as you go.

Step 4 — Algorithm:

1. Start count = 0, curr = head

2. While curr != null: count++, curr = curr->next

3. Return count

Step 5 — Edge cases: Empty list → return 0.

function countNodes(?ListNode $head): int {
    $count = 0;
    $curr  = $head;
    while ($curr !== null) {
        $count++;
        $curr = $curr->next;
    }
    return $count;
}

Time: O(n) | Space: O(1)

---

Q2 — Get Nth Node from Start

🧠 How to Approach This

Step 1 — Recognize the pattern: Index-based traversal.

Step 2 — Brute force (what NOT to do): Collect all into array then index — extra space.

Step 3 — Optimal insight: Walk n steps from head.

Step 4 — Algorithm:

1. Walk n steps from head

2. Return current node's value (or null if out of bounds)

Step 5 — Edge cases: n >= list length → return null.

function getNth(?ListNode $head, int $n): ?int {
    $curr = $head;
    for ($i = 0; $i < $n && $curr !== null; $i++) {
        $curr = $curr->next;
    }
    return $curr?->val;
}

Time: O(n) | Space: O(1)

---

Comparison: Array vs Linked List

---

The Dummy Head Trick

Adding a dummy node before the real head eliminates null-checks at the head position:

$dummy = new ListNode(0);
$dummy->next = $head;
// ... modifications ...
return $dummy->next; // real head

This pattern is used in 70%+ of linked list problems — master it!