Efficient insertion and/or removal of an element of a doubly linked list in PHP

Question

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?

Answer 1

The wording in the documentation is confusing. "shuffling up" suggests that this is not a constant time operation.

However, the C source code for the add method is essentially following this algorithm:

• If the given index is equal to the size of the list (which is maintained), call push instead.
• Create the node
• Get the node at the given index
• Insert the new node before it, setting the four involved links

For getting the node at the given index, this routine is used, and mainly loops through the list to stop at the given index, and then returns the node at that index. This is a linear operation on average.

This clearly shows that even though this API can output an array like structure, the structure itself does not store indexes with the nodes, and no re-indexing takes place. There is no O(1) access to the node whose index you provide -- it must be found by following the links in the linked list.

So checking these sources, the implementation really is like we should expect, and corresponds to the images you added to your question.

var_dump

The output of var_dump should also be taken with a grain of salt: it is not (always) presenting the actual internal structure. This is because it relies on the magic method __debugInfo which can completely control what exactly var_dump will output.

And indeed the sources for this SplDoublyLinkedList::__debugInfo method show that an array is created on the spot. It relies on a method that iterates through the linked list via the next chain, populating an array that is returned to var_dump.