add post

1 files changed, 669 insertions, 0 deletions

diff --git a/2026-05-25-singly-linked-list.php.txt b/2026-05-25-singly-linked-list.php.txt
new file mode 100644
index 0000000..66222db
--- /dev/null
+++ b/2026-05-25-singly-linked-list.php.txt
@@ -0,0 +1,669 @@
+<?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