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

Question

我是编程新手，不熟悉 Java 中的某些术语和引用资料。虽然我相信我已经有效地利用了谷歌，但我发现让你们为我简化它会帮助我更有效。

我的问题是，节点具体是什么？它们的用途是什么？另外，Stingy Linked Structures 有什么用？

Answer 1

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

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

我不相信有所谓的“吝啬链表”。我认为您的意思是单链表，这是一个链表，其中每个单元格(片段)仅存储一个链接，通常指向序列中的下一个元素。这使得在列表中从一个元素向前扫描到下一个元素变得容易，但很难在列表中后退一个位置。

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

希望这对您有所帮助!