在 perl 中创建链表中 NEXT 的含义

Question

所以我正在尝试使用Perl学习链表。我正在阅读Jon Orwant的Mastering Algorithm with Perl。在书中，他解释了如何创建一个链表。我理解了大部分内容，但我只是无法理解代码片段倒数第二行中的命令/索引/键NEXT。

$list=undef;
$tail=$list;
foreach (1..5){
  my $node = [undef, $_ * $_];
  $$tail = $node;
  $tail = ${$node->[NEXT]}; # The NEXT on this line? 
}

他在那里想做什么？

$node是存储未命名数组地址的标量吗？此外，即使我们取消引用$node，我们不应该用索引号来引用各个元素，例如 （0，1）。如果我们确实使用 NEXT 作为键，$node是对哈希的引用吗？我很困惑。

简单的

英语将不胜感激。

Answer 1

NEXT是一个常量，在脚本前面声明。 它包含一个整数值，表示引用下一个节点的当前节点的成员元素的索引。

在此方案下，每个节点都是一个小的匿名数组。 此匿名数组的一个元素包含有效负载，另一个元素包含指向下一个节点的引用。

如果您查看该章前面的一些示例，您将看到以下声明：

use constant NEXT    => 0;
use constant VAL     => 1;

所以$node->[NEXT]是$node->[0]的同义词，它包含对链表链中下一个节点的引用，而$node->[VAL]是$node->[1]的同义词;存储在当前节点中的值（或有效载荷）。

我将评论您提供的代码片段：

foreach (1..5){
  my $node = [undef, $_ * $_];    # Create a new node as an anon array.
  # Set the previous node's "next node reference" to point to this new node.
  $$tail = $node;                 
  # Remember a reference to the new node's "next node reference" element.
  # So that it can be updated when another new element is added on next iteraton.
  $tail = ${$node->[NEXT]}; # The NEXT on this line? 
}

顺便说一下，这本好书。 我有几本算法书，这么多年过去了，那本仍然是我的最爱之一。

更新：我同意这本书不是当前惯用的Perl或当前的"最佳实践"Perl的模型，但确实觉得它是了解Perl经典算法应用的好资源。 我仍然不时地回顾它。

Answer 2

NEXT是一个常量，在较早的页面上声明，包含一个数字。 使用它而不是仅仅使用常规数字来访问数组 ref $node，以便读者知道 slot 是链表中下一个元素的存储位置。

这是一种使用数组引用来存储列表以外的内容的技术。 与使用哈希引用相比，该技术旨在节省内存和 CPU 时间。 实际上，它并没有太大的性能差异，而且使用起来很尴尬。 这本书在关于如何编写Perl代码的想法上已经过时了。 请改用哈希引用。

my $list;
my $tail = $list;
foreach my $num (1..5) {
    my $node = { data => $num };
    $$tail = $node;
    $tail = $node->{next};
}