Doubly linked list – implementation from scratch, SplDoublyLinkedList, comparison table

PHP array is versatile enough that we rarely need other data structures. But a doubly linked list has properties an array does not – inserting and removing elements from the middle in O(1), without shifting the remaining elements. I implement one from scratch in PHP and show when it is worth reaching for.

What is a doubly linked list?

A doubly linked list is a sequence of nodes where each node stores a value and pointers to the previous and next node. There is no contiguous memory block like an array – each node can be anywhere in memory.

<?php

class Node
{
    public ?Node $prev = null;
    public ?Node $next = null;

    public function __construct(public mixed $value) {}
}

Implementation

<?php

declare(strict_types=1);

class DoublyLinkedList
{
    private ?Node $head = null;
    private ?Node $tail = null;
    private int $size   = 0;

    // Append to end - O(1)
    public function append(mixed $value): void
    {
        $node = new Node($value);
        if ($this->tail === null) {
            $this->head = $this->tail = $node;
        } else {
            $node->prev       = $this->tail;
            $this->tail->next = $node;
            $this->tail       = $node;
        }
        $this->size++;
    }

    // Prepend to start - O(1)
    public function prepend(mixed $value): void
    {
        $node = new Node($value);
        if ($this->head === null) {
            $this->head = $this->tail = $node;
        } else {
            $node->next       = $this->head;
            $this->head->prev = $node;
            $this->head       = $node;
        }
        $this->size++;
    }

    // Remove a node - O(1) if you have the reference
    public function remove(Node $node): void
    {
        if ($node->prev !== null) {
            $node->prev->next = $node->next;
        } else {
            $this->head = $node->next;
        }
        if ($node->next !== null) {
            $node->next->prev = $node->prev;
        } else {
            $this->tail = $node->prev;
        }
        $node->prev = $node->next = null;
        $this->size--;
    }

    // Insert after a given node - O(1)
    public function insertAfter(Node $after, mixed $value): Node
    {
        $node = new Node($value);
        $node->prev  = $after;
        $node->next  = $after->next;
        if ($after->next !== null) {
            $after->next->prev = $node;
        } else {
            $this->tail = $node;
        }
        $after->next = $node;
        $this->size++;
        return $node;
    }

    public function getSize(): int   { return $this->size; }
    public function getHead(): ?Node { return $this->head; }
    public function getTail(): ?Node { return $this->tail; }

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

$list = new DoublyLinkedList();
$list->append('A'); $list->append('B'); $list->append('C'); $list->prepend('Z');
print_r($list->toArray()); // ['Z', 'A', 'B', 'C']

$nodeA = $list->getHead()->next;
$list->insertAfter($nodeA, 'X');
print_r($list->toArray()); // ['Z', 'A', 'X', 'B', 'C']

Comparison with PHP array

SplDoublyLinkedList – built-in PHP implementation

<?php

$list = new \SplDoublyLinkedList();
$list->push('A'); $list->push('B'); $list->push('C');
$list->unshift('Z'); // prepend

echo $list->bottom(); // 'Z' - first element
echo $list->top();    // 'C' - last element

$list->pop();   // removes 'C' from end
$list->shift(); // removes 'Z' from start

foreach ($list as $value) {
    echo $value . PHP_EOL;
}

When to use a list instead of an array?

• Implementing an LRU cache – move the most recently used element to the front in O(1)
• Operation queues with undo/redo support – inserting and removing from the middle
• When array_unshift() becomes a bottleneck on large collections

Summary

A doubly linked list shines for insert and delete operations in the middle. In PHP you have a ready implementation via SplDoublyLinkedList – worth knowing it exists before you start optimising code with array_splice() in a loop on large collections.