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:
- Its
SplDoublyLinkedList::add ( mixed $index , mixed $newval )
method takes an$index
parameter and it is said that itshuffles the previous value at that index (and all subsequent values) up through the list
. - 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/).
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.