Lista dwukierunkowa – implementacja od zera, SplDoublyLinkedList, tabela porównawcza

PHP array jest na tyle wszechstronna, że rzadko potrzebujemy innych struktur danych. Ale lista dwukierunkowa (doubly linked list) ma właściwości, których tablica nie oferuje – wstawianie i usuwanie elementów ze środka w O(1), bez przesuwania pozostałych elementów. Implementuję ją od zera w PHP i pokazuję kiedy warto po nią sięgnąć.

Czym jest lista dwukierunkowa?

Lista dwukierunkowa to sekwencja węzłów, gdzie każdy węzeł przechowuje wartość oraz wskaźniki na poprzedni i następny węzeł. Nie ma ciągłego obszaru pamięci jak tablica – każdy węzeł może być w dowolnym miejscu.

<?php

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

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

Implementacja listy dwukierunkowej

<?php

declare(strict_types=1);

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

    // Dodaj na koniec - O(1)
    public function append(mixed $value): void
    {
        $node = new Node($value);

        if ($this->tail === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $node->prev      = $this->tail;
            $this->tail->next = $node;
            $this->tail      = $node;
        }

        $this->size++;
    }

    // Dodaj na początek - O(1)
    public function prepend(mixed $value): void
    {
        $node = new Node($value);

        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $node->next       = $this->head;
            $this->head->prev = $node;
            $this->head       = $node;
        }

        $this->size++;
    }

    // Usuń węzeł - O(1) jeśli masz referencję do węzła
    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 = null;
        $node->next = null;
        $this->size--;
    }

    // Wstaw za podanym węzłem - 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; }

    // Iteracja od przodu
    public function toArray(): array
    {
        $result  = [];
        $current = $this->head;

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

        return $result;
    }
}

Użycie

<?php

$list = new DoublyLinkedList();
$list->append('A');
$list->append('B');
$list->append('C');
$list->prepend('Z');

print_r($list->toArray());
// ['Z', 'A', 'B', 'C']

// Wstaw 'X' po 'A' - O(1)
$nodeA = $list->getHead()->next; // węzeł 'A'
$list->insertAfter($nodeA, 'X');

print_r($list->toArray());
// ['Z', 'A', 'X', 'B', 'C']

// Usuń 'B' - O(1)
$nodeB = $nodeA->next->next; // węzeł 'B'
$list->remove($nodeB);

print_r($list->toArray());
// ['Z', 'A', 'X', 'C']

Porównanie z tablicą PHP

SplDoublyLinkedList – gotowa implementacja w PHP

PHP ma wbudowaną listę dwukierunkową w bibliotece SPL:

<?php

$list = new \SplDoublyLinkedList();

$list->push('A');
$list->push('B');
$list->push('C');
$list->unshift('Z'); // dodaj na początku

echo $list->bottom(); // 'Z' - pierwszy element
echo $list->top();    // 'C' - ostatni element

$list->pop();   // usuwa 'C' z końca
$list->shift(); // usuwa 'Z' z początku

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

Kiedy używać listy zamiast tablicy?

W praktyce PHP lista dwukierunkowa ma sens w kilku konkretnych sytuacjach:

• Implementacja LRU cache – najczęściej używane elementy przemieszczasz na początek listy w O(1)
• Kolejki operacji z możliwością cofania (undo/redo) – wstawianie i usuwanie ze środka
• Przetwarzanie strumieniowe danych gdzie często wstawiasz elementy na początku
• Kiedy array_unshift() staje się wąskim gardłem przy dużych kolekcjach

Podsumowanie

Lista dwukierunkowa to struktura danych, która błyszczy w operacjach wstawiania i usuwania ze środka. W PHP masz gotową implementację przez SplDoublyLinkedList – warto wiedzieć że istnieje, zanim zaczniesz optymalizować kod z array_splice() w pętli na dużych kolekcjach.