PHP SPL: Verkettete Listen

Eine nützliche Klasse die durch SPL ihren Einzug in PHP gefunden hat, ist die SplDoublyLinkedList, die Implementierung einer doppelt verketteten Liste.
Eine verkettete Liste ist eine dynamisch erweiterbare Datenstruktur, die beliebig viele Elemente speichern und enumerieren kann. In vielen Sprachen, in denen die Größe von Arrays bereits statisch beim Erstellen festgelegt wird, sind Listen deshalb ein wichtiger Grundbaustein um wachsende Datenstrukturen zu Implementieren. Da Arrays in PHP diese Einschränkungen nicht haben und damit generell bereits alle Möglichkeiten einer Liste bieten, gab es lange Zeit keine Implementierung in der PHP-Standardbibliothek.
Das verwenden einer SplDoubleLinkedList macht aber in vielen Bereich dennoch Sinn, da diese das Einfügen von Elementen an bestimmten Positionen einfacher und performanter macht. Wenn wir in einem normalen Array ein Element an einem bestimmten Index einfügen wollen ohne ein Element zu überschreiben, können wir array_splice verwenden.

$N = 10000;
$arr = array('foo', 'bar', 'baz');
for ($i = 0; $i < $N; $i++) {
    array_splice($arr, 1, 0, $item);
}

Wie wir feststellen ist diese Implementierung nicht sonderlich performant und das Einfügen von 10000 Elementen dauert bereits fast 10 Sekunden.

time php -f ./insert_at_array.php
real 0m10.116s
user 0m10.077s
sys 0m0.024s

Die SplDoublyLinkedList beherrscht seit Version 5.5 die Funktion SplDoublyLinkedList::add, die ein Element an eine bestimmte Position in die Liste einfügen kann.

$N = 10000;
$list = new SplDoublyLinkedList();
$list->push('foo');
$list->push('bar');
$list->push('baz');
for ($i = 0; $i < $N; $i++) {
    $list->add(1, $i);
}

Time verrät uns, dass diese Implementierung mit 47ms mehr als 200 mal schneller durchläuft als die mit regulären Arrays.

time php -f ./insert_at_list.php
real 0m0.047s
user 0m0.036s
sys 0m0.008s

Erklären lässt sich dieser Unterschied mit der internen Implementierung von Arrays in PHP. Diese sind in PHP eigentlich Hash-Tabellen, weshalb beim Aufruf von array_splice, alle nachfolgenden Elemente mit einem neuen Index versehen werden müssen. In einer verketteten Liste wird der Index eines Elements nicht gespeichert, sondern nur anhand der Position in der Kette aus Elementen definiert. Hier genügt es die Referenzen des Vorgängers und des Nachfolgers zu ändern um alle Nachfolger einen Index nach hinten zu verschieben.