algorithm - 100万节点的链表如何实现？

Question

我最近参加了微软面试。

我被问到要实现一百万个节点的链表？你将如何访问第 999999 个节点？

这样一个问题的最佳设计策略和实现是什么？

Answer 1

链表的变体相当少，因为变体多意味着它不是链表。

您可以通过单链接或双链接来改变它。单链接是你有一个指向头的指针(第一个节点，A 说)指向 B 指向 C，等等。要将其转换为双链表，你还可以添加从 C 到 B 和 B 的链接给 A.

如果你有一个双链表，那么保留一个指向链表尾部(最后一个节点)和头部的指针是有意义的，这意味着访问最后一个元素的成本很低，靠近末尾的元素更便宜，因为你可以向后或向前工作......但是......你需要知道你想要的是在列表的末尾......并且在一天结束时链表仍然只是那个，如果它是会变得非常大，这是一个问题，因为它的用例的性质，那么可能应该选择链表以外的存储结构。

当然你可以混合你的链表，所以你可以索引它或其他东西，理论上这没有错，但如果你索引所有节点然后链表性质不再有多大值(value)，如果你只索引一些，那么 inode 之间的节点必须排序或其他东西，这样你就可以找到一个接近的节点并朝着目标节点工作......可能这永远不会是最佳的并且应该选择更好的数据结构.

当您不想做诸如获取特定节点之类的事情，但无论如何都想迭代节点时，确实应该使用链表。