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

Question

我最近参加了微软面试.

我被要求用100万个节点实现链表？你将如何访问999999th节点？

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

Answer 1

链表的变化相当少,因为很多变化意味着它不是链表.

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

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

你当然可以杂交你的链接列表,所以你可以索引它或者某些东西,例如,理论上没有任何问题,但如果你索引所有节点,那么链表性质不再有太大价值,如果你索引只有一些,那么索引节点之间的节点必须进行排序或者某种东西,这样你就可以找到一个关闭节点并朝向目标节点工作......这可能永远不会是最优的,应该选择更好的数据结构.

当您不想执行某些特定节点但想要迭代节点时,应该使用链接列表.

Answer 2

我不知道我要说什么，但是，这里是：

您可以conceptually将列表拆分为sqrt(1000000) 块，这样每 1000 个元素就有一个“引用指针”。

把它想象成让1000 linked lists每个 用1000 elements代表你的列表1000000 elements。

想到的就是这个！