我有一个关于数据结构基础的问题。
我知道数组的访问时间比链表快。 O(1)- 数组 与 O(N) - 链表
但是链表在删除元素方面优于数组，因为不需要 O(N)- array vs O(1) -linked list
所以我的理解是，如果对数据的大部分操作是删除，那么使用链表是更可取的。
但是如果用例是:
- 删除元素但不要太频繁
- 访问所有元素
有明显的赢家吗？在一般情况下，我知道使用列表的缺点是我访问可能位于单独页面上的每个节点，而数组具有更好的局部性。
但这是我应该有的理论或实际问题吗？
混合类型，即从数组创建链表(使用额外字段)是个好主意吗？
我的问题也取决于语言吗？我假设在所有语言中移动数组中的元素具有相同的成本(至少渐近地)
最佳答案
与纯引用相比，如果您要进行大量插入/删除操作，单链表非常有用，并且相对于数组而言性能更好。
几十年来，我一直没有看到双向链表的良好用途。 我想有一些。
就绩效而言，永远不要在不了解您的特定情况的相对绩效的情况下做出决定。 比较常见的是，人们会问一些类似于理发减肥的问题。
在编写应用程序之前，我首先会问它应该是计算密集型还是 IO 密集型。 如果受 IO 限制，我会尝试通过避免 IO 效率低下并保持处理简单明了来确保它确实受限制。 如果它应该是受计算限制的，那么我会查看它的内部循环可能是什么，并尝试使其快速。
无论如何，无论我尝试多少，都会有(有时是很大的)机会让它走得更快，为了找到它们，我使用 this technique . 无论你做什么，都不要只是试图想想 或回到你的类笔记。 您的问题与其他人的不同，解决方案也不同。
关于performance - 链表(也包括双重链表)的适当应用是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22541836/