summaryrefslogtreecommitdiff
path: root/2026-05-25-singly-linked-list.php.txt
diff options
context:
space:
mode:
Diffstat (limited to '2026-05-25-singly-linked-list.php.txt')
-rw-r--r--2026-05-25-singly-linked-list.php.txt669
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
generated by cgit v1.2.3 (git 2.46.0) at 2026-05-31 11:00:48 +0000