language-agnostic - 链表在什么情况下有用？

Question

大多数时候我看到人们尝试使用链接列表，在我看来这是一个糟糕(或非常糟糕)的选择。也许探索链表在什么情况下是或不是一个好的数据结构选择会很有用。

理想情况下，答案将详细说明选择数据结构时使用的标准，以及哪些数据结构在特定情况下可能效果最好。

编辑:我必须说，我不仅对答案的数量印象深刻，而且对答案的质量印象深刻。我只能接受一个，但如果没有更好的东西的话，我不得不说还有两三个是值得接受的。只有一对夫妇(尤其是我最终接受的那一个)指出了链表提供真正优势的情况。我确实认为史蒂夫·杰索普值得某种荣誉奖，因为他不仅提出了一个答案，而且提出了三个不同的答案，所有这些答案都令我印象深刻。当然，尽管它只是作为评论而不是答案发布，但我认为 Neil 的博客文章也非常值得一读 - 不仅内容丰富，而且非常有趣。

Answer 1

当您需要在任意(编译时未知)长度的列表上进行大量插入和删除操作，但不需要进行太多搜索时，链接列表非常有用。

拆分和连接(双向链接)列表非常有效。

您还可以组合链接列表 - 例如树结构可以实现为将水平链接列表(兄弟)连接在一起的“垂直”链接列表(父/子关系)。

将基于数组的列表用于这些目的有严重的限制:

• 添加新项目意味着必须重新分配数组(或者您必须分配比所需空间更多的空间，以适应 future 的增长并减少重新分配的次数)
• 删除项目会造成空间浪费或需要重新分配
• 在除末尾之外的任何位置插入项目都涉及(可能重新分配和)将大量数据复制到一个位置