java - 吝啬的链接结构和节点？

Question

我对编程相当陌生，不熟悉 Java 中的某些术语和参考。虽然我相信我已经有效地利用了 google，但我发现让你们为我简化它会更有效地帮助我。

我的问题是，节点具体是什么？它们是用来做什么的？此外，Stingy Linked Structures 用于什么？

Answer 1

链接结构是一种数据结构，由一堆较小的元素（称为单元或节点）组成，这些元素链接在一起形成一个更大的结构。这类似于分子的形成方式——你有一堆较小的原子，然后它们连接在一起形成一个分子。许多重要的数据结构，例如链表或二叉搜索树 - 都是链接结构。

链接结构通常与基于数组的结构形成对比。数组具有固定的大小并且是“刚性的”——您无法有效地将它们分成更小的部分——因此通常增长或缩小基于数组的结构需要时间。由较小的部分组成的链接结构可以很容易地分成较小的部分或由新部分组成。例如，要将元素附加到数组，您可能必须分配一个巨大的新数组，复制所有旧元素，然后附加新元素。使用链接列表或链接结构，您可以在末尾添加另一部分，这可以提高效率。同样，如果您有一个排序数组并且需要插入一个元素，您可能必须将数组中的所有其他元素打乱，因为没有办法“拼接” 放入数组中的东西。如果排序后的序列存储在二叉搜索树中，则可以将新元素添加到适当的位置，而无需移动任何其他元素，从而使插入更有效率。

我不相信有什么叫做“吝啬的链表”的东西。我认为您的意思是单链表，它是一个链表，其中每个单元（片段）仅存储一个链接，通常指向序列中的下一个元素。这使得在列表中从一个元素向前扫描到下一个元素变得容易，但很难备份列表中的一个位置。

老实说，没有简单的方法来枚举您想要使用链接结构的所有情况，因为很多结构都是链接结构。我建议拿起一本关于基本数据类型（列表、堆栈、队列、树等）的书来了解更多关于这方面的信息。我刚刚完成了专门针对该主题的四分之一编程课程的教授，我怀疑是否有可能浓缩成一个 SO 答案。:-)

希望这可以帮助！