什么时候链表是最好的数据结构
When is a linked list the best data structure to use
真的很喜欢这个标题。我的问题是你能举一个例子，其中链表是最好的数据结构。我一直在努力想出任何真的，在我的代码中我几乎总是只使用哈希图或列表等。
http://bigocheatsheet.com/这里可以看到大O的各种操作秘籍sheet。就复杂性而言，链表并不比堆栈或 queue 好。所以我想知道什么时候有人可能会在这些上使用链表？一个完美的答案会说 "Imagine I was trying to do XYZ, if I did it with an array it would look like this {enter some code}, however, if I do it with a linked list, it will look like this {enter more code}. The complexities or space are substantially better for the linked list." 等
我不想要有人告诉我链表是什么的答案。我知道链表是什么以及它们是如何实现的。
谢谢
考虑一下你是否有一个人的队列，并且你想在中间的某个地方添加很多人。如果您使用传统的 ArrayList，则需要在它之后移动所有元素，因此 O(N) 因为每个人都有索引！在 LinkedList 中，每个人的时间复杂度为 O(1)，到中间的时间复杂度为 O(N)。链表在中间添加元素非常快，因为你不需要重新索引任何东西，只需调整本地指针。
有人dd调查了C++标准模板库，发现链表是所有常见的基本结构中用得最少的。所以你是对的，他们用得不多。当您不需要随机访问数组时，当您不知道 N 或对 N 有一个相当严格的上限时，以及当插入和删除很常见且时间紧迫时，它们很有用。中间的插入是 O(N)，与数组一样，但实际操作要便宜很多（指针解引用而不是内存移位），开头的插入是 O(1)，最后如果你保持结束指针。
真的很喜欢这个标题。我的问题是你能举一个例子，其中链表是最好的数据结构。我一直在努力想出任何真的，在我的代码中我几乎总是只使用哈希图或列表等。
http://bigocheatsheet.com/这里可以看到大O的各种操作秘籍sheet。就复杂性而言，链表并不比堆栈或 queue 好。所以我想知道什么时候有人可能会在这些上使用链表？一个完美的答案会说 "Imagine I was trying to do XYZ, if I did it with an array it would look like this {enter some code}, however, if I do it with a linked list, it will look like this {enter more code}. The complexities or space are substantially better for the linked list." 等
我不想要有人告诉我链表是什么的答案。我知道链表是什么以及它们是如何实现的。
谢谢
考虑一下你是否有一个人的队列，并且你想在中间的某个地方添加很多人。如果您使用传统的 ArrayList，则需要在它之后移动所有元素，因此 O(N) 因为每个人都有索引！在 LinkedList 中，每个人的时间复杂度为 O(1)，到中间的时间复杂度为 O(N)。链表在中间添加元素非常快，因为你不需要重新索引任何东西，只需调整本地指针。
有人dd调查了C++标准模板库，发现链表是所有常见的基本结构中用得最少的。所以你是对的，他们用得不多。当您不需要随机访问数组时，当您不知道 N 或对 N 有一个相当严格的上限时，以及当插入和删除很常见且时间紧迫时，它们很有用。中间的插入是 O(N)，与数组一样，但实际操作要便宜很多（指针解引用而不是内存移位），开头的插入是 O(1)，最后如果你保持结束指针。