在PHP中高效插入和/或删除双向链表的元素

I need to use a doubly linked list data structure which would allow me to insert and/or remove elements arbitrarily at any position with constant time (O(1)) without reindexing any internal data structure.

I was thinking about implementing my own data structure, but then I came across SplDoublyLinkedList (http://php.net/manual/en/class.spldoublylinkedlist.php).

Instantly, two things make me doubting:

1. Its SplDoublyLinkedList::add ( mixed $index , mixed $newval ) method takes an $index parameter and it is said that it shuffles the previous value at that index (and all subsequent values) up through the list.
2. Its remove counterpart method SplDoublyLinkedList::offsetUnset also takes an index as parameter and reindexes the internal array of the doubly linked list.

These two points make me think that the SplDoublyLinkedList in PHP behaves more like a Java ArrayList, where the internal array of the data structure is reindexed again and again after every insert/remove operation.

In fact if you run the following code, you will see that there's an internal array being reindexed:

$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);

Output:

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"
  }
}

Same goes for SplDoublyLinkedList::offsetUnset.

Whereas, in a doubly linked list, there's no concept of index, just nodes with a previous and next element, allowing O(1) insertion and removal (taken from http://www.java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/).

Insertion:

Removal:

Any thoughts regarding the implementation details of the SplDoublyLinkedList in PHP? Do SplDoublyLinkedList::add and SplDoublyLinkedList::offsetUnset really allow insertion/removal with O(1) constant time or do I need to be wary because internally it uses an array which is reindexed after every insertion/removal operation?

Thank you for the attention.