path: root/2026-05-25-singly-linked-list.php.txt

<?php

/**
 * Oops. My PHP source code is being exposed. That's scary. LOL. Actually,
 * this is a blog post that you can run with the PHP interpreter. The code
 * was tested on the latest PHP version as of writing—PHP 8.5.
 * 
 * A linked list is one of the foundational data structures, and you can
 * easily spot it everywhere. Technically, this article mainly talks about
 * the singly linked list—a sequence of nodes where each node stores a
 * value alongside a reference to its neighbour.
 * 
 * +-----+-----+    +-----+-----+    +-----+------+
 * |  A  |  o--+--->|  B  |  o--+--->|  C  | NULL |
 * +-----+-----+    +-----+-----+    +-----+------+
 * 
 * Insertion and removal at the front both have O(1) time complexity. So a
 * singly linked list is efficient for operations at the front.
 * 
 * For example, a recent history feature can store the newest action at the
 * front of the list whenever the application state changes. Then, when
 * reverting an action, we simply pop it off the front of the list. Sounds
 * like a stack, right?
 * 
 * You can also implement a FIFO queue using a variant of a singly linked
 * list with two pointers: a head pointer and a tail pointer. You push
 * events to the end of the list with the tail pointer in O(1), and pop the
 * next event off the queue with the head pointer in O(1).
 * 
 * Well, let's get started. Feel free to follow along with the code and try
 * implementing it yourself.
 */

final class Node
{
    /**
     * Create a node instance.
     *
     * Each node not only stores a value but also a reference to
     * the next node. The value is typed as a string in this example,
     * but feel free to change it to whatever type you like.
     */
    public function __construct(
        public string $value,
        public ?Node $next = null
    ) {
        //
    }
}

/**
 * The singly linked list.
 */
final class LinkedList
{
    /**
     * Find a node by the given value.
     *
     * Let's start with a simple one. We traverse the linked list one
     * node at a time. If we find a node containing the target value, we
     * immediately return the node instance. Otherwise, if the traversal
     * finishes without finding the target node, we return null.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function find(?Node $head, string $value): ?Node
    {
        $current = $head;

        while ($current) {
            if ($current->value === $value) {
                return $current;
            }

            $current = $current->next;
        }

        return null;
    }

    /**
     * Determine whether the list contains a value.
     *
     * Based on the `find` logic above, we know that if the result is a
     * node instance, the value exists in the list.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function contains(?Node $head, string $value): bool
    {
        return static::find($head, $value) instanceof Node;
    }

    /**
     * Push the `other` list to the front of the `node`.
     *
     * Let's say we have two list:
     *
     *  - A, B, C  (node)
     *  - 1, 2, 3  (other)
     *
     * If we want to place the second list in front of the first one, we
     * first traverse the `other` list to find its last node—3 in this
     * case. Then, we link that node to the head of the first list by
     * setting 3's next reference to node A. Finally, we return the head
     * of the `other` list as the new head of the concatenated list.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function pushFront(?Node $node, ?Node $other): ?Node
    {
        if ($node === null) {
            return $other;
        }

        if ($other === null) {
            return $node;
        }

        $tail = self::tail($other);
        $tail->next = $node;

        return $other;
    }

    /**
     * Append the `other` list to the current list.
     *
     * Appending B to A produces the same order as prepending A to B.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function pushBack(?Node $node, ?Node $other): ?Node
    {
        return self::pushFront($other, $node);
    }

    /**
     * Insert the `other` list after the `target` node.
     *
     * We insert the `other` list between the `target` node and its next
     * node. To do that, we need to reconnect both sides of the insertion
     * point.
     *
     * For example:
     *  - A, B, C  (target = A)
     *  - 1, 2, 3  (other)
     *
     * The result becomes:
     *  - A, 1, 2, 3, B, C
     *
     * First, we link node A to the head of the `other` list. Then, we
     * connect the last node in the `other` list back to A's original
     * next node—B in this case.
     *
     * Time complexity = O(m)
     * Space complexity = O(1)
     */
    public static function insertAfter(Node $target, Node $other): Node
    {
        $tail = self::tail($other);
        $tail->next = $target->next;

        $target->next = $other;

        return $target;
    }

    /**
     * Insert the `other` list at a specific position in the `head` list.
     *
     * After the insertion, the first node of the `other` list will be
     * located at the specified index.
     *
     * The main logic is similar to `insertAfter`, except that we first
     * need to find the node right before the target position in the
     * `head` list.
     *
     * We also need to handle a few edge cases. The index must be
     * greater than or qeual to 0. If the index is 0, we perform a
     * `pushFront` operation instead.
     *
     * If we cannot find a valid insertion point, the index is out of
     * bounds, so we return null.
     *
     * Time complexity = O(n+m)
     * Space complexity = O(1)
     */
    public static function insertAt(?Node $head, int $index, Node $other): ?Node
    {
        if ($index < 0) {
            return null;
        }

        if ($index === 0) {
            return self::pushFront($head, $other);
        }

        $target = self::get($head, $index - 1);

        if ($target === null) {
            return null;
        }

        self::insertAfter($target, $other);

        return $head;
    }

    /**
     * Pop the first node off the list.
     *
     * The logic is straightforward: we return a tuple whose first item
     * is the value of the first node, along with the new head node.
     *
     * Time complexity = O(1)
     * Space complexity = O(1)
     *
     * @return array{0: ?string, 1: ?Node}
     */
    public static function popFront(?Node $head): array
    {
        return [$head?->value, $head?->next];
    }

    /**
     * Pop the last node off the list.
     *
     * In a singly linked list, each node only stores a reference to the
     * next node. To pop the last node off the list, we need to traverse
     * the list until we reach the end.
     *
     * We continue traversing while two nodes remain ahead of the current
     * node so that we stop at the second-to-last node. We then retrieve
     * the value of the next (last) node and unlink it from the list.
     *
     * Finally, we can construct the result containing both the popped
     * value and the updated list.
     *
     * Don't forget to handle the edge cases where the given list
     * contains fewer than two nodes. If the head node is the only node
     * in the list, we can construct the result directly.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     *
     * @return array{0: ?string, 1: ?Node}
     */
    public static function popBack(?Node $head): array
    {
        $current = $head;

        if ($head === null) {
            return [null, null];
        }

        if ($head->next === null) {
            return [$head->value, null];
        }

        while ($current->next->next) {
            $current = $current->next;
        }

        $value = $current->next->value;
        $current->next = null;

        return [$value, $head];
    }

    /**
     * Reverse the list.
     *
     * Traverse the list while maintaining a reference to the previous
     * node. For each node, redirect its next reference to the previous
     * node until we reach the end of the list.
     *
     * Once the loop finishes, the current pointer will be null because
     * it continues advancing through each node's next reference. At
     * that point, the previous pointer will point to the last node of
     * the original list, which is now the new head of the reversed
     * list.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function reverse(?Node $node): ?Node
    {
        $previous = null;
        $current = $node;

        while ($current) {
            $next = $current->next;
            $current->next = $previous;
            $previous = $current;

            $current = $next;
        }

        return $previous;
    }

    /**
     * Retrieve the node at the given position.
     *
     * Traverse the list node by node until we reach the target
     * position. Meanwhile, if the current node becomes null, we can
     * stop early and return null since the position does not exist.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function get(?Node $head, int $index): ?Node
    {
        if ($index < 0) {
            return null;
        }

        $current = $head;

        for ($i = 0; $i < $index; $i++) {
            if ($current === null) {
                return null;
            }

            $current = $current->next;
        }

        return $current;
    }

    /**
     * Remove the `target` node from the list.
     *
     * This is a wrapper method that improves the developer experience.
     * Based on the type of the `target` parameter, the call is
     * forwarded to the appropriate handler.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function remove(?Node $node, Node|string|null $target): ?Node
    {
        if (is_string($target)) {
            return self::removeByValue($node, $target);
        }

        return self::removeByNode($node, $target);
    }

    /**
     * Remove the `target` node from the list.
     *
     * Traverse the list while checking one node ahead of the current
     * node until we find a node whose next reference points to the
     * `target` node.
     *
     * Otherwise, if we only stop at the `target` node itself, we cannot
     * reconnect the previous node to skip over it.
     *
     * Once found, we redirect the current node's next reference to the
     * target node's next node, effctively skipping the node we want to
     * remove.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function removeByNode(?Node $node, ?Node $target): ?Node
    {
        if ($node === null || $target === null) {
            return $node;
        }

        if ($node === $target) {
            return $node->next;
        }

        $current = $node;

        while ($current->next) {
            if ($current->next === $target) {
                $current->next = $target->next;

                return $node;
            }

            $current = $current->next;
        }

        return $node;
    }

    /**
     * Remove all nodes with the given value from the list.
     *
     * Traverse the list node by node while maintaining two pointers:
     * the previous node and the new head node. We need these pointers
     * because some nodes may be removed, so we cannot rely on the
     * original head reference.
     *
     * These two pointers are only updated when the current node does
     * not contain the value we want to remove.
     *
     * The new head pointer is initialized only once, when we find the
     * first node that should be kept.
     *
     * If the previous node exists, we link it to the current node,
     * rebuilding the list one kept node at a time. Before moving to the
     * next iteration, we store the current node as the previous node so
     * that the next kept node can be linked to it.
     *
     * After the loop finishes, we also need to cut off the previous
     * node's next reference. This handles the case where the original
     * list ends with nodes that should be removed.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function removeByValue(?Node $head, string $value): ?Node
    {
        $newHead = $previous = null;
        $current = $head;

        while ($current) {
            if ($current->value !== $value) {
                if ($newHead === null) {
                    $newHead = $current;
                }

                if ($previous) {
                    $previous->next = $current;
                }

                $previous = $current;
            }

            $current = $current->next;
        }

        if ($previous) {
            $previous->next = null;
        }

        return $newHead;
    }

    /**
     * Get the length of the list.
     *
     * Traverse the list node by node and count the number of nodes
     * until we reach the end of the list.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    public static function length(?Node $node): int
    {
        $len = 0;
        $current = $node;

        while ($current) {
            $len++;
            $current = $current->next;
        }

        return $len;
    }

    /**
     * Build a singly linked list from the given values.
     *
     * Traverse the list of values and wrap each value in a node
     * instance while maintaining two pointers: a head pointer and a
     * previous pointer.
     *
     * The head pointer is initialized only once when the first node is
     * created. Before each iteration ends, we store the current node as
     * the previous pointer so that the next node can be linked to it.
     *
     * Once the loop finishes, we return the head of the newly built list.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     *
     * @param  string[]  $values
     */
    public static function fromArray(array $values): ?Node
    {
        if ($values === []) {
            return null;
        }

        $head = $previous = null;

        foreach ($values as $value) {
            $node = new Node($value);

            if ($previous) {
                $previous->next = $node;
            }

            if ($head === null) {
                $head = $node;
            }

            $previous = $node;
        }

        return $head;
    }

    /**
     * Represent the linked list as a list of strings.
     *
     * Traverse the list node by node and build a list of strings from
     * each node's value.
     *
     * Time complexity = O(n)
     * Space complexity = O(n)
     *
     * @return string[]
     */
    public static function toArray(?Node $node): array
    {
        $result = [];

        $current = $node;
        while ($current) {
            $result[] = $current->value;
            $current = $current->next;
        }

        return $result;
    }

    /**
     * Get the tail node of the list.
     *
     * Traverse the list node by node until we reach a node without a
     * next reference.
     *
     * Time complexity = O(n)
     * Space complexity = O(1)
     */
    private static function tail(Node $node): Node
    {
        $current = $node;

        while ($current->next) {
            $current = $current->next;
        }

        return $current;
    }
}


/* Below are the basic test cases that verify the code works as expected */

class_alias('LinkedList', 'L');

assert(L::length(new Node('a')) === 1);
assert(L::length(L::fromArray(['a', 'b', 'c'])) === 3);
assert(L::length(null) === 0);

assert(L::toArray(L::fromArray(['a', 'b', 'c'])) === ['a', 'b', 'c']);
assert(L::toArray(null) === []);

assert(L::pushBack(new Node('a'), new Node('b')) |> L::toArray(...) === ['a', 'b']);
assert(L::pushBack(L::fromArray(['a', 'b']), L::fromArray(['m', 'n'])) |> L::toArray(...) === ['a', 'b', 'm', 'n']);
assert(L::pushBack(null, new Node('b')) |> L::toArray(...) === ['b']);
assert(L::pushBack(new Node('a'), null) |> L::toArray(...) === ['a']);
assert(L::pushBack(null, null) === null);

assert(L::pushFront(new Node('a'), new Node('b')) |> L::toArray(...) === ['b', 'a']);
assert(L::pushFront(L::fromArray(['a', 'b']), L::fromArray(['m', 'n'])) |> L::toArray(...) === ['m', 'n', 'a', 'b']);
assert(L::pushFront(null, new Node('b')) |> L::toArray(...) === ['b']);
assert(L::pushFront(new Node('a'), null) |> L::toArray(...) === ['a']);
assert(L::pushFront(null, null) === null);

$n = L::fromArray(['a', 'b', 'c', 'd']);
assert(L::removeByNode($n, $n->next->next) |> L::toArray(...) === ['a', 'b', 'd']);
assert(L::removeByNode($n, $n) |> L::toArray(...) === ['b', 'd']);
assert(L::removeByNode($n, null) |> L::toArray(...) === ['a', 'b', 'd']);
assert(L::removeByNode(null, $n) === null);
assert(L::removeByNode(null, null) === null);

assert(L::removeByValue(L::fromArray(['a', 'b', 'c']), 'b') |> L::toArray(...) === ['a', 'c']);
assert(L::removeByValue(L::fromArray(['a', 'b', 'b', 'c']), 'b') |> L::toArray(...) === ['a', 'c']);
assert(L::removeByValue(L::fromArray(['a', 'b']), 'a') |> L::toArray(...) === ['b']);
assert(L::removeByValue(L::fromArray(['a', 'b']), 'b') |> L::toArray(...) === ['a']);
assert(L::removeByValue(L::fromArray(['a', 'b']), 'c') |> L::toArray(...) === ['a', 'b']);
assert(L::removeByValue(null, 'a') === null);
assert(L::removeByValue(new Node('a', new Node('a')), 'a') === null);

$n = L::fromArray(['a', 'b', 'c']);
assert(L::removeByNode($n, $n->next) |> L::toArray(...) === ['a', 'c']);
assert(L::remove($n, 'c') |> L::toArray(...) === ['a']);

$n = L::fromArray(['a', 'b', 'c']);
assert(L::find($n, 'b')->next->value === 'c');
assert(L::find($n, 'd') === null);
assert(L::find(null, 'a') === null);
assert(L::contains($n, 'c') === true);
assert(L::contains($n, 'd') === false);
assert(L::contains(null, 'a') === false);

$n = L::fromArray(['a', 'b', 'c']);
assert(L::get($n, 0)->value === 'a');
assert(L::get($n, 2)->value === 'c');
assert(L::get($n, 3) === null);
assert(L::get($n, -1) === null);

assert(L::insertAfter(L::fromArray(['a', 'b']), L::fromArray(['m', 'n'])) |> L::toArray(...) === ['a', 'm', 'n', 'b']);

assert(L::insertAt(L::fromArray(['a', 'b', 'c']), 1, L::fromArray(['m', 'n'])) |> L::toArray(...) === ['a', 'm', 'n', 'b', 'c']);
assert(L::insertAt(L::fromArray(['a', 'b']), 0, L::fromArray(['m', 'n'])) |> L::toArray(...) === ['m', 'n', 'a', 'b']);
assert(L::insertAt(L::fromArray(['a', 'b']), 2, L::fromArray(['m', 'n'])) |> L::toArray(...) === ['a', 'b', 'm', 'n']);
assert(L::insertAt(L::fromArray(['a', 'b']), 3, L::fromArray(['m', 'n'])) === null);
assert(L::insertAt(L::fromArray(['a', 'b']), -1, L::fromArray(['m', 'n'])) === null);
assert(L::insertAt(null, 0, L::fromArray(['a', 'b'])) |> L::toArray(...) === ['a', 'b']);
assert(L::insertAt(null, 1, L::fromArray(['a', 'b'])) === null);

$n = L::fromArray(['a', 'b', 'c']);
[$v, $n] = L::popFront($n);
assert($v === 'a');
assert(L::toArray($n) === ['b', 'c']);

$n = new Node('a');
[$v, $n] = L::popFront($n);
assert($v === 'a');
assert($n === null);

[$v, $n] = L::popFront(null);
assert($v === null);
assert($n === null);

$n = L::fromArray(['a', 'b', 'c']);
[$v, $n] = L::popBack($n);
assert($v === 'c');
assert(L::toArray($n) === ['a', 'b']);

$n = L::fromArray(['a', 'b']);
[$v, $n] = L::popBack($n);
assert($v === 'b');
assert(L::toArray($n) === ['a']);

$n = new Node('a');
[$v, $n] = L::popBack($n);
assert($v === 'a');
assert($n === null);

[$v, $n] = L::popBack(null);
assert($v === null);
assert($n === null);

assert(L::reverse(L::fromArray(['a', 'b', 'c'])) |> L::toArray(...) === ['c', 'b', 'a']);
assert(L::reverse(L::fromArray(['a', 'b'])) |> L::toArray(...) === ['b', 'a']);
assert(L::reverse(new Node('a')) |> L::toArray(...) === ['a']);
assert(L::reverse(null) === null);

assert(L::fromArray(['a', 'b', 'c']) |> L::toArray(...) === ['a', 'b', 'c']);
assert(L::fromArray([]) |> L::toArray(...) === []);

# vim: et ts=4 sw=4 nowrap