perl - 在 Perl 中创建链表结构

Question

在 C 中，您可以创建自己的结构，并从那里创建一个链表，其中结构中的记录将指向下一条记录以及上一条记录。

Perl 肯定有办法做到这一点吗？很想知道如何。

谢谢

标签： perldata-structures

Answer 1

您可以按照在 C 中执行此操作的方式基本相同，但使用引用而不是指针和散列而不是结构。

但是在 Perl 中通常你不必这样做，因为 Perl 的内置数组非常聪明和快速。它们自动增长，并且已经完成了链表可以做的大部分事情，比如用 、 、 和 来添加和删除任意元素，以及从splice数组的前面和后面添加和删除。而且，与链表不同，您获得 O(1) 随机访问。有关更多信息，请参见perlfunc。poppushshiftunshift

您也不要这样做，因为在 Perl 中编写自己的数据结构往往很慢。Perl 数组是用 C 编写的，但是您的链表将用慢得多的 Perl 编写并消耗更多的内存。虽然该算法可能更有效，但实现会很慢。在计算机科学术语中，常数将非常大。最终结果是像链表和树这样的专用数据结构只有在您开始处理数十万或数百万个元素时才有意义。

您的另一个选择是使用用 C 编写的链表库。您可以使用称为 XS 的东西来利用 C 库，它充当 C 代码和 Perl 代码之间的桥梁。但这不是最容易使用的东西。