在 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. 它的 remove 对应方法SplDoublyLinkedList::offsetUnset也将索引作为参数，并重新索引双向链表的内部数组。

这两点让我觉得SplDoublyLinkedListin 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-列表/双向链接列表/）。

插入：

移动：

关于SplDoublyLinkedListPHP 中的实现细节的任何想法？不要SplDoublyLinkedList::add和SplDoublyLinkedList::offsetUnset真正允许与插入/移除O(1)固定的时间还是需要警惕，因为在内部它使用每插入/删除操作后重建索引的数组？

感谢您的关注。

Answer 1

文档中的措辞令人困惑。“洗牌”表明这不是一个恒定时间的操作。

然而， add方法的 C 源代码本质上遵循以下算法：

• 如果给定索引等于列表的大小（已维护），则push改为调用。
• 创建节点
• 获取给定索引处的节点
• 在其前面插入新节点，设置涉及的四个链接

为了获取给定索引处的节点，使用此例程，主要是循环遍历列表以在给定索引处停止，然后返回该索引处的节点。平均而言，这是一个线性运算。

这清楚地表明，尽管该 API 可以输出类似数组的结构，但该结构本身并不存储节点索引，并且不会发生重新索引。对您提供索引的节点没有 O(1) 访问权限——必须通过链表中的链接找到它。

因此，检查这些来源，实现确实如我们所期望的那样，并且与您添加到问题中的图像相对应。

变量转储

的输出var_dump也应该持保留态度：它并不（总是）呈现实际的内部结构。这是因为它依赖于魔法方法__debugInfo，可以完全控制到底var_dump输出什么。

事实上，这个SplDoublyLinkedList::__debugInfo方法的来源表明，一个数组是当场创建的。它依赖于一种通过链迭代链表的方法next，填充返回到的数组var_dump。