PHP 的 SplDoublyLinkedList 类（更重要的是，链接列表）有什么意义？

Question

为了扩展我的编程能力，我稍微深入研究了 标准 PHP 库. 。这导致我发现 SplDoublyLinkedList 班级。从那里我读到的描述 链表 和 双向链表 在维基百科上。

我明白他们是如何工作的...但我无法想象我们为什么需要它——或者更好的是一个实际的例子 SplDoublyLinkedList 因为我们在 PHP 中有索引数组和关联数组。

链接列表通常如何在 PHP 内外使用？

Answer 1

SPL数据结构减少了记忆消耗并提高性能。很好的解释：

数据结构固有地独立于语言，并且作为基于数学的一组逻辑概念存在。这些容器使用不同的算法适合提高效率。

例如，如果您不需要关联阵列的哈希地图功能 - 也就是说，如果您不是为特定目的使用阵列键，并且只需要枚举的数组-SplfixedArray（以前是SplfastAray） ）可能是合适的替代品。唯一的警告是固定数组的大小是固定的，这意味着当您实例化类时，必须指定大小，并且如果您尝试存储超过该数量的元素，则会发生错误。这就是平均而言，其性能要比标准PHP阵列更好。

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

在构成PHP解释器的C代码中，数组被实现为称为Hash表或哈希映射的数据结构。当数组中包含的值由其索引引用时，PHP使用哈希函数将索引转换为代表数组中相应值的位置的唯一哈希。

此哈希地图实现使数组可以存储任意数量的元素，并使用数字键或字符串键同时访问所有这些元素。对于它们提供的功能，阵列非常快，并且是出色的通用数据结构。

在计算机科学中，列表定义为有序的值集合。链接列表是一个数据结构，其中列表中的每个元素都包括对列表中任一侧的一个或两个元素的引用。 “双关联列表”一词用于参考后一种情况。在SPL中，这采用类SplDoublyLinkedList的类形式。...在未提前存储的元素数量时使用列表是有意义的，并且仅需要通过顺序位置访问元素。

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/

Answer 2

根据 维基百科,

链接列表比常规数组的主要好处是，链接项目的顺序可能与数据项存储在内存或磁盘上的顺序不同。因此，链接列表允许在列表中的任何点插入和删除节点，并具有恒定的操作数量。

另一方面，链接列表本身不允许随机访问数据或任何形式的有效索引。因此，许多基本操作（例如获得列表的最后一个节点，或找到包含给定基准的节点，或找到应插入新节点的位置的节点 - 可能需要扫描大多数列表元素。

因此，要回答您的问题，我不知道。 :)

Answer 3

首先， spldoublylinkedlist 是对象

• 它们可以扩展，因此您可以覆盖其方法（例如，您可以返回所有字符串，等等）
• 他们实现的接口可以像在 myfunc( SplDoublyLinkedList $var ) ...
• 它们默认为参考
• 等等

第二， spldoublylinkedlist 接受迭代模式，因此您可以在旅途中删除项目，并切换方向而无需重新排序或使您的代码复杂化：

spldoublylinkedlist ::it_mode_lifo （堆栈样式）

spldoublylinkedlist ::it_mode_fifo （队列样式）迭代器的行为（一个或另一个）

spldoublylinkedlist ::it_mode_delete （元素由迭代器删除）

spldoublylinkedlist ::it_mode_keep （元素由迭代器遍历）

以上引号来自 http://simpletechinfo.com/spldoublylinkedlist 其中包含一些代码样本。

还有其他特权（例如，不必在记忆所有数据等方面进行副本等）

Answer 4

他们在那里，因为许多从其他语言开始的程序员都习惯了阵列固定尺寸，并且您必须照顾记忆管理。
因此，对于PHP，它们只是另一个工具。它们之所以实现，是因为列表上的许多算法和模式继电器，因此不需要更改为PHP阵列。

Answer 5

正如其他人提到的那样，列表是其他语言中常见的固定数组的替代方法。但是，经常被忽略的一个重要方面 - 您可以非常有效地从列表中的任何位置插入或删除元素。

为什么这很重要？假设您有几个要维护在数组中的项目，也许您不必以后对它们进行分类或仅仅以最大程度地减少搜索时间。在这种情况下，列表可以是一个非常强大的工具。特别是对于非常大的数据集。

Answer 6

你可能是对的，但它并不是很有用。

理论上链表有很多用途（尤其是跳舞链接）。但其中大多数涉及在其他地方存储和克隆其迭代器、以两个以上的方向访问内容，或者拆分和合并列表。SplDoublyLinkedList 似乎没有这些。

如果不是用于算法，一种用途是允许对象在恒定时间内删除某个列表中自身的引用，释放其内存，并且在插入或删除后不打乱列表（通过散列或与最后一项交换）。但这需要在这些对象中存储列表的迭代器。

如果没有这些功能，它们的行为就像两个双端队列。如果您只需要使用迭代器访问项目，那么它们就像两个堆栈。在单线程简单情况下，一种更好的方法是使用两个堆栈（可能是固定数组，或者同一数组的两端），除非尚未包装在类中。每当您希望迭代器移动时，从一个堆栈中弹出并将其推入另一个堆栈，并且一个堆栈的顶部是当前项。如果您还需要访问头部和尾部，则需要将堆栈替换为双端队列。

但是，如果您想在不知道最大大小的情况下实现堆栈或双端队列本身，或者甚至要分配普通链表的节点（使用没有这些库的语言，例如 PHP），那么最好的方法是将一些固定数组链接在一起，使用 doublely没有这些功能的链表。不知怎的，你仍然需要它。

PHP 文档本身，就像 Java 文档一样，表明它们应该只是一个支持一些额外奇怪功能的双端队列，甚至不是两个双端队列（我认为）。如果您确实需要双向链表，请不要使用它们。