Эффективная вставка и / или удаление элемента двусвязного списка в PHP

Question

Мне нужно использовать структуру данных двусвязного списка, которая позволила бы мне произвольно вставлять и / или удалять элементы в любой позиции с постоянным временем (O(1)) без переиндексации любой внутренней структуры данных.

Я думал о реализации своей собственной структуры данных, но потом наткнулся на SplDoublyLinkedList (http://php.net/manual/en/class.spldoublylinkedlist.php).

Мгновенно две вещи заставляют меня сомневаться:

1. Его метод SplDoublyLinkedList::add ( mixed $index , mixed $newval ) принимает параметр $index, и говорят, что он shuffles the previous value at that index (and all subsequent values) up through the list.
2. Метод удаления аналога SplDoublyLinkedList::offsetUnset также принимает индекс в качестве параметра и переиндексирует внутренний массив двусвязного списка.

Эти два момента заставляют меня думать, что SplDoublyLinkedList в PHP ведет себя больше как Java ArrayList, где внутренний массив структуры данных переиндексируется снова и снова после каждой операции вставки / удаления.

Фактически, если вы запустите следующий код, вы увидите, что внутренний массив переиндексируется:

$dlist = new SplDoublyLinkedList();  
$dlist->push('A'); 
$dlist->push('B'); 
$dlist->push('C');

var_dump($dlist);

$dlist->add(1, 'Z');

echo "After insertion in the middle of the list:";

var_dump($dlist);

Выход:

class SplDoublyLinkedList#1 (2) {
  private $flags =>
  int(0)
  private $dllist =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
}

After insertion in the middle of the list:

class SplDoublyLinkedList#1 (2) {
  private $flags =>
  int(0)
  private $dllist =>
  array(4) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "Z"
    [2] =>
    string(1) "B"
    [3] =>
    string(1) "C"
  }
}

То же самое относится к SplDoublyLinkedList::offsetUnset.

Принимая во внимание, что в двусвязном списке нет понятия индекса, только узлы с предыдущим и следующим элементом, позволяющие вставлять и удалять O(1) (взято из http://www.java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/).

Вставка:

Удаление:

Есть какие-нибудь мысли о деталях реализации SplDoublyLinkedList в PHP? SplDoublyLinkedList::add и SplDoublyLinkedList::offsetUnset действительно разрешают вставку / удаление с O(1) постоянным временем, или мне нужно быть осторожным, потому что внутри он использует массив, который переиндексируется после каждой операции вставки / удаления?

Спасибо за внимание.