为什么节点链在算法中？

Question

我正在阅读数据结构和算法。我在那里发现了诺德和诺德的锁链。为什么我们必须使用节点链(我的意思是为什么我们真的需要存储下一个节点的指针)？

Answer 1

这给了我们很多功能，我只是列举了其中的几个：

• 它使您能够在任何需要的地方使用插入。
  • 假设我们有两个节点A和B，就像A->next = B，我的意思是，它是A->B，如果您想在A和B的中间插入C，您可以简单地使用A->next = C和C->next = B，它就是A->C->B。

​

• 它使您可以使用删除，并使用O(1)进行任何操作。
  • 在前面的示例中，如果您想要删除C，您可以执行这个A->next = B，所以它将是A->C。

​

• 它让你有能力用它的脑袋传递你的名单。
  • 假设您有一个链接列表，如：A->B->C-> ....，而不是将所有节点传递给另一个函数，您只需传递A。

​

数据结构有很多种，每一种都有其优缺点。此外，在链接列表中可能有很多我没有提到的功能。

Answer 2

你可以在你走的时候动态地增长链子，而不是像你在一个数组中那样的预先所有。您需要存储下一个节点的指针，以便可以访问它。您不能像数组一样按索引访问它。