21

在寻求扩展我的编程能力的过程中，我对标准 PHP 库进行了深入研究。这导致我发现了这个SplDoublyLinkedList类。从那里我阅读了维基百科上链接列表和双向链接列表的描述。

我理解它们是如何工作的……但我无法想出为什么我们需要它的原因——或者更好的是一个实际的例子，SplDoublyLinkedList因为我们在 PHP 中已经建立了索引和关联数组。

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

4

7 回答 7

9

SPL 数据结构可减少内存消耗并提高性能。很好的解释：

数据结构本质上与语言无关，并且作为一组基于数学的逻辑概念存在。这些容器酌情使用不同的算法来最大化效率。

例如，如果您不需要关联数组的哈希映射功能——也就是说，如果您没有将数组键用于特定目的而只需要一个枚举数组——SplFixedArray（以前称为 SplFastArray，目前未记录) 可能是合适的替代品。唯一需要注意的是数组的大小是固定的，这意味着您必须在实例化类时指定大小，如果您尝试存储超过该数量的元素，则会发生错误。这就是平均而言它比标准 PHP 数组执行得更好的原因。

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

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

这种哈希映射实现使数组能够存储任意数量的元素，并使用数字或字符串键同时提供对所有这些元素的访问。数组提供的功能非常快，并且是一种出色的通用数据结构。

在计算机科学中，列表被定义为值的有序集合。链表是一种数据结构，其中列表中的每个元素都包含对列表中其任一侧的一个或两个元素的引用。术语“双向链表”用于指后一种情况。在 SPL 中，这采用类 SplDoublyLinkedList.... 的形式。当预先不知道要存储的元素数量并且只需要按顺序位置访问元素时，使用列表是有意义的。

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

于 2011-09-22T20:22:41.177 回答
4

根据维基百科，

与传统数组相比，链表的主要优点是链接项的顺序可能与数据项存储在内存或磁盘中的顺序不同。出于这个原因，链表允许在列表中的任何点插入和删除节点，操作数是恒定的。

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

所以回答你的问题，我不知道。:)

于 2010-10-18T20:58:19.750 回答
4

首先，SplDoublyLinkedList是对象，因此

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

其次，SplDoublyLinkedList接受迭代模式，因此您可以随时删除项目并切换方向，而无需重新排序数组或使代码复杂化：

SplDoublyLinkedList:: IT_MODE_LIFO（堆栈样式）

SplDoublyLinkedList:: IT_MODE_FIFO (Queue style) 迭代器的行为（一个或另一个）

SplDoublyLinkedList:: IT_MODE_DELETE（元素被迭代器删除）

SplDoublyLinkedList:: IT_MODE_KEEP（元素被迭代器遍历）

以上引用来自http://simpletechinfo.com/SplDoublyLinkedList，其中包含一些代码示例。

还有其他好处（例如 foreach 不必在内存中复制所有数据等）

于 2014-01-22T02:37:31.140 回答
1

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

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

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

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

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

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

于 2015-03-21T10:06:19.133 回答
0

它们在那里是因为许多来自其他语言的程序员已经习惯了它们，其中数组具有固定大小并且您必须注意内存管理。
所以对于 PHP，它们只是另一个工具。它们的实现是因为许多算法和模式在列表上中继，因此不需要将它们更改为 php-arrays。

于 2010-10-18T21:05:28.920 回答
0

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

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

于 2012-08-26T07:58:12.443 回答
0

也许您正在编写一个 Web 应用程序，以使网站看起来和行为像一本书（如 epub online）。可折叠的 TOC（目录）将提供随机访问。链表将提供一种方便的方式来实现“下一页”和“上一页”按钮。Next 和 Previous 可以以其他方式实现。链表会让它变得轻而易举。

于 2020-05-09T14:10:36.290 回答