SplDoublyLinkedList — Klasse · PHP-Referenz

Signatur

class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable, Serializable

Beschreibung

SplDoublyLinkedList stellt eine doppelt verkettete Liste bereit, bei der Einfüge- und Löschoperationen am Anfang (prepend) und am Ende (append) in konstanter Zeit O(1) ablaufen. Die Klasse unterstützt sowohl Stack- (LIFO) als auch Queue-Semantik (FIFO) und kann als Basis für SplStack und SplQueue dienen.

Da SplDoublyLinkedList das Iterator-Interface implementiert, kann sie direkt in foreach-Schleifen verwendet werden. Über setIteratorMode() lässt sich steuern, ob die Liste vorwärts oder rückwärts durchlaufen wird und ob beim Iterieren Elemente automatisch entfernt werden (DELETE-Modus) oder nicht (KEEP-Modus).

Im Gegensatz zu gewöhnlichen PHP-Arrays bietet die doppelt verkettete Liste Vorteile, wenn häufige Einfügungen oder Löschungen am Listenanfang oder -ende nötig sind und auf wahlfreien Index-Zugriff verzichtet werden kann. Über das ArrayAccess-Interface sind jedoch auch Index-basierte Zugriffe möglich, allerdings mit O(n) Aufwand.

Typische Einsatzgebiete sind Aufgaben-Warteschlangen, Undo/Redo-Stacks, Browser-History-Simulationen und alle Szenarien, bei denen eine geordnete, dynamisch wachsende und schrumpfende Datenstruktur benötigt wird.

Beispiele

Grundlegende Stack-Nutzung (LIFO)

<?php
$list = new SplDoublyLinkedList();
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP);

$list->push('Erster');
$list->push('Zweiter');
$list->push('Dritter');

echo 'Anzahl Elemente: ' . count($list) . PHP_EOL;

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

// Letztes Element entfernen
$letztes = $list->pop();
echo 'Entfernt: ' . $letztes . PHP_EOL;
echo 'Anzahl nach pop: ' . count($list) . PHP_EOL;

Anzahl Elemente: 3 Dritter Zweiter Erster Entfernt: Dritter Anzahl nach pop: 2

Queue-Nutzung (FIFO) mit unshift und shift

<?php
$queue = new SplDoublyLinkedList();
$queue->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);

$queue->enqueue('Aufgabe A');
$queue->enqueue('Aufgabe B');
$queue->enqueue('Aufgabe C');

echo 'Nächste Aufgabe: ' . $queue->bottom() . PHP_EOL;

while (!$queue->isEmpty()) {
    $aufgabe = $queue->dequeue();
    echo 'Verarbeite: ' . $aufgabe . PHP_EOL;
}

echo 'Queue leer: ' . ($queue->isEmpty() ? 'Ja' : 'Nein') . PHP_EOL;

Nächste Aufgabe: Aufgabe A Verarbeite: Aufgabe A Verarbeite: Aufgabe B Verarbeite: Aufgabe C Queue leer: Ja

Index-basierter Zugriff und Serialisierung

<?php
$list = new SplDoublyLinkedList();
$list->push('Alpha');
$list->push('Beta');
$list->push('Gamma');

// ArrayAccess-Zugriff (O(n)!)
echo $list[0] . PHP_EOL; // Alpha
echo $list[1] . PHP_EOL; // Beta

$list[1] = 'Delta';
echo $list[1] . PHP_EOL; // Delta

// Serialisierung
$serialized = serialize($list);
$restored = unserialize($serialized);
echo $restored[2] . PHP_EOL; // Gamma

Alpha Beta Delta Gamma

// Wichtig · Fallstricke

Iterator-Modi: Die Konstanten für setIteratorMode() müssen kombiniert werden: Richtung (IT_MODE_FIFO oder IT_MODE_LIFO) und Verhalten (IT_MODE_KEEP oder IT_MODE_DELETE). Im DELETE-Modus werden Elemente beim Iterieren unwiderruflich aus der Liste entfernt.

Performance: Index-basierte Zugriffe über ArrayAccess (z. B. $list[5]) traversieren die Liste intern und haben O(n)-Komplexität — bei sehr großen Listen oder häufigem wahlfreiem Zugriff ist ein normales PHP-Array performanter.

Serialisierung: Seit PHP 8.1 ist die Serializable-Schnittstelle als veraltet markiert. Die Klasse nutzt intern __serialize()/__unserialize(); serialize()/unserialize() funktionieren jedoch weiterhin.

Grenzen: Beim Zugriff auf Elemente mit ungültigem Index wird eine RuntimeException geworfen. Ebenso werfen pop(), shift(), top() und bottom() eine RuntimeException, wenn die Liste leer ist.

Siehe auch

SplStack SplQueue SplFixedArray SplMinHeap Iterator ArrayAccess Countable