我最近参加了微软面试。
我被要求实现具有100万个节点的链表？您将如何访问第999999个节点？
对于这样一个问题，最佳的设计策略和实现是什么？
链表几乎没有变化，因为变化很大意味着它不是链表。
你可以通过单链接或双链接来改变它。单链接是指你有一个指向头部的指针（比如说第一个节点），它指向B，指向C，等等。要将其变成双链接列表，你还需要添加一个从C到B和B到a的链接。
如果你有一个双链接列表，那么保留一个指向列表尾部（最后一个节点）和头部的指针是有意义的，这意味着访问最后一个元素很便宜，而接近末尾的元素更便宜，因为你可以向后或向前工作。。。但是。。。你需要知道你想要什么在清单的末尾。。。最终，链表仍然是这样，如果它将变得非常大，并且由于其用例的性质，这是一个问题，那么可能应该选择链表以外的存储结构。
当然，你可以混合你的链表，这样你就可以对它或其他东西进行索引，理论上这没有什么错，但如果你对所有节点进行索引，那么链表的性质就没有多大价值，如果你只对一些节点进行索引，那么索引节点之间的节点必须进行排序，这样你才能找到一个接近的节点并朝着目标节点工作。。。这可能永远不会是最佳的，应该选择更好的数据结构。
实际上，当您不想做诸如获取特定节点之类的事情，但无论如何都想迭代节点时，应该使用链表。
我不知道我要说什么，但是，下面是：
您可以conceptually在sqrt(1000000)块中拆分列表，这样每1000个元素就有一个"引用指针"。
把它想象成1000 linked lists和1000 elements分别代表你的列表和1000000 elements。
这就是我想到的！
正如Michael所说，您应该首先介绍链表的两个经典变体。接下来您应该询问插入、搜索和删除模式。
这些模式将引导您获得更适合的数据结构，因为没有人想要一个包含一百万个节点的简单或双链接列表。
在这种情况下，带有静态计数器来指向索引的双循环链表可能非常有用。我的建议是创建一个循环双链表，它有一个计数器变量来跟踪每个节点的索引，还有一个静态变量来保持列表中节点的总数。
现在，当索引的搜索项大于总节点数的50%时，即搜索下半部分的元素时，可以从相反的方向开始遍历列表。
假设你的循环链表中有10个节点，你想搜索第8个节点，这样你就可以快速开始在相反的方向遍历列表2次。
这种方法减少了搜索极端索引列表项的迭代次数，但在最坏的情况下，您必须遍历列表的一半以查找中间的项。
这种方法唯一的缺点是内存限制，我认为这不是设计问题。