Linked lists — implementing in PHP, when to use

Intermediate5 min read·eng-07-002

compare

Concept

Linked list: A sequence of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory.

Singly linked list: Each node has value and next. Traversal is forward-only. Doubly linked list: Each node has value, next, AND prev. Bidirectional traversal. Supports efficient O(1) removal when you have a reference to the node.

Operations:

prepend (insert at head): O(1) — just update the head pointer.
append (insert at tail): O(1) if you keep a tail pointer, O(n) otherwise.
search: O(n) — must traverse from head.
delete with reference to node: O(1) for doubly linked list.
delete by value: O(n) — must search first.

Linked list vs array:

Array: O(1) random access by index. O(n) insert/delete in the middle (must shift elements).
Linked list: O(n) to reach position k. O(1) insert/delete once you have the reference.
PHP arrays are hash tables — they don't need shifting on insert. Linked lists only win for very specific patterns.

When to use in PHP: Rarely need a linked list in PHP — the array is usually better. Use cases:

Undo/redo history (doubly linked, O(1) step forward/back).
LRU Cache (doubly linked list + hash map — O(1) access and eviction).
Task scheduler with frequent queue manipulation.
SplDoublyLinkedList if you need it.

PHP built-in: SplDoublyLinkedList, SplQueue (FIFO operations on a doubly linked list), SplStack (LIFO).

Code Example

php

<?php
// Manual singly linked list implementation
class ListNode
{
    public function __construct(
        public int       $value,
        public ?ListNode $next = null,
    ) {}
}

class SinglyLinkedList
{
    private ?ListNode $head = null;
    private int       $size = 0;

    public function prepend(int $value): void
    {
        $this->head = new ListNode($value, $this->head);
        $this->size++;
    }

    public function append(int $value): void
    {
        $node = new ListNode($value);
        if ($this->head === null) { $this->head = $node; $this->size++; return; }
        $current = $this->head;
        while ($current->next !== null) { $current = $current->next; }
        $current->next = $node;
        $this->size++;
    }

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

    public function toArray(): array
    {
        $result  = [];
        $current = $this->head;
        while ($current !== null) { $result[] = $current->value; $current = $current->next; }
        return $result;
    }
}

// LRU Cache — doubly linked list + hash map = O(1) get and put
class LRUCache
{
    private array $map = [];
    private \SplDoublyLinkedList $list;

    public function __construct(private int $capacity)
    {
        $this->list = new \SplDoublyLinkedList();
    }

    public function get(string $key): mixed
    {
        if (!isset($this->map[$key])) return null;
        $this->moveToFront($key);
        return $this->map[$key]['value'];
    }

    public function put(string $key, mixed $value): void
    {
        if (isset($this->map[$key])) { $this->map[$key]['value'] = $value; $this->moveToFront($key); return; }
        if (count($this->map) >= $this->capacity) { $this->evict(); }
        $this->list->push($key);
        $this->map[$key] = ['value' => $value];
    }

    private function moveToFront(string $key): void
    {
        // Remove and re-add at end (SplDoublyLinkedList push = end)
        foreach ($this->list as $index => $k) {
            if ($k === $key) { unset($this->list[$index]); break; }
        }
        $this->list->push($key);
    }

    private function evict(): void
    {
        $key = $this->list->shift(); // remove oldest (front)
        unset($this->map[$key]);
    }
}

PreviousArrays as hash maps — O(1) lookup, collision handlingData Structures in PHP NextStacks and queues — SplStack, SplQueue, array implementationsData Structures in PHP