哪个数据结构？链表或Java中的任何其他？

我对Java程序中使用的数据结构有特殊的要求。它（数据结构）应该能够保存大量的数据（不是固定的），我的主要操作是在最后添加，并从头开始删除/读取（LinkedLists看起来不错）。但偶尔，我需要从中间删除，这是LinkedLists非常痛苦的地方。任何人都可以建议我解决这个问题吗？或者我可以通过哪些优化来减少LinkedList中的删除操作？哪个数据结构？链表或Java中的任何其他？

感谢您的帮助！

来源

2010-02-28 Superman16885

你可以尝试使用带有指针的链表之后的第10000个元素，这样你就可以减少找到你想要删除的中间的时间。这里有一些链接列表的一些不同变化： http://experimentgarden.blogspot.com/2009/08/performance-analysis-of-thirty-eight.html

来源

2010-02-28 06:36:52

思考一个跳过列表？ http://en.wikipedia.org/wiki/Skip_list 原因添加和删除是O（日志n） – 2010-02-28 09:26:52

是啊我研究了pugh等人的skiplists，他们似乎是一个可行的解决方案 – 2010-02-28 19:19:11

LinkedList落在随机访问。没有随机访问查找的删除是不变的，对于长列表来说真的不算太坏。

ArrayList一般很快。从中间插入和移除的速度比您预期的要快，因为阻止内存移动的速度惊人地快。在开始附近移除和插入以使所有以下数据向下或向上移动。

ArrayDeque就像ArrayList只有它使用循环缓冲区和有一个奇怪的接口。

通常的建议：尝试一下。

来源

2010-02-28 06:37:16

@Spedge好点。 – 2010-02-28 07:07:16

LinkedHashMap中可能适合你的目的你会用一个迭代器从正面拉的东西，并通过查找关键的条目时，你需要访问列表

来源

2010-02-28 07:12:14 objects

LinkedHashMap中间大概是办法走。伟大的迭代，deque操作，并寻找到中间。但是，在内存中需要额外的成本，因为您需要在基本集合上管理一组密钥。另外，我认为它会在你删除的空间中留下'空白'，导致非连续的一组键（尽管不应该影响迭代）。

编辑：啊哈！我知道你需要什么：A LinkedMultiSet！一个LinkedHashMap的所有好处，但没有多余的密钥集。不过，这只是一个更复杂的使用。

来源

2010-02-28 09:17:32

首先您需要考虑您是否会从列表中心删除经常与列表的长度相比较。如果您的清单有N项目，但删除次数比1/N少得多，请不要担心。根据您的喜好使用LinkedList或ArrayDeque。（如果你的列表偶尔很大，然后缩小，但大多很小，LinkedList更好，因为它很容易恢复内存;否则，ArrayDeque不需要额外的对象，所以它更快一点，也更紧凑 - 除了底层阵列永远不会收缩）

如果，另一方面，你删除相当多的往往比1/N，那么你应该考虑一个LinkedHashSet，它保持在一个哈希集合的顶部链表队列 - 但它是一套，所以请记住，您不能存储重复的元素。这会将开销LinkedList和ArrayDeque放在一起，但如果您经常执行中央删除操作，则可能会值得。然而，如果你真的需要最后一盎司的速度并且愿意花费编码时间来获得它，那么最优结构将会是一个“可调整大小”的数组（即在它太小时重新分配），这个数组与一个循环缓冲区，您可以通过将元素设置为null来清空中间的元素。（如果你有一个不正当的用例，那么你也可以重新分配缓冲区。）我不建议编码，除非你真的喜欢编码高性能数据结构，或者有充分的证据表明这是一个代码中的关键瓶颈，因此您真的需要它。

来源

2010-03-01 06:55:51

哪个数据结构？链表或Java中的任何其他？

回答

相关问题