2

我正在实现一种算法，该算法将在集合的末尾添加字符串并在开头删除字符串。在极少数情况下，我将执行随机访问删除以将其推送到最后。我主要是 C++ 开发人员，我不确定在 java 的关键循环中使用什么会有好处。我认为 java 列表不太适合这项任务。当然它会起作用，但我已经在努力解决性能问题。

链表？向量？建议？

4

6 回答 6

4

我建议使用ArrayDeque，它实现Queue和Deque接口但不实现List（您可能不需要）：

接口的可调整大小的数组实现Deque。数组双端队列没有容量限制；它们会根据需要增长以支持使用。它们不是线程安全的；在没有外部同步的情况下，它们不支持多线程并发访问。禁止使用空元素。此类可能比Stack用作堆栈时更快，并且比LinkedList 用作队列时更快。

您还提到了删除：

该接口提供了两种移除内部元素的方法， removeFirstOccurrence以及removeLastOccurrence.

ArrayDeque提供您需要的所有方法 - addFirst(E e), addLast(E e), removeFirst().

另请参阅此问题以了解更多信息ArrayDeque。

PS这里是上面链接中的一些集合基准ArrayDeque，其他LinkedList人ArrayList提到过；）

于 2012-08-30T18:00:29.190 回答
1

您似乎正在尝试实现队列（LIFO）。 http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html。您可以查看源代码及其实现方式以获得更多想法。

于 2012-08-30T17:51:27.723 回答
1

听起来你想要一个队列，是吗？查看Queue界面。

Queue<String> strQueue = new LinkedList<String>();
strQueue.offer("Hello");
strQueue.offer("World");
System.out.println(strQueue.poll());
System.out.println(strQueue.poll());

印刷：

Hello
World
于 2012-08-30T17:52:40.170 回答
1

在 ArrayList 上使用 Vector 是没有意义的，除非您需要所有单独的操作都是synchronized，而这通常不需要。

如果您只打算进行头部和尾部插入/删除，那么 LinkedList 最有意义。但是，如果列表很大并且您需要进行随机访问检索，那么必须遍历列表可能会很痛苦。

另一方面，ArrayList 提供了非常便宜的随机访问，但是从列表头部插入或删除元素需要移动后备数组的其余部分。JDK 实现通过调用System.arraycopy()来做到这一点，它能够非常便宜地做到这一点。

在这种情况下，最好的办法是使用两种实现进行基准测试并比较结果。编写有问题的算法以仅使用 a ，您可以轻松地为您的基准List交换不同的实现。List

我看不出在 ArrayList 上使用常规数组的目的是什么，因为您必须自己编写头/尾移除/插入代码，并在大小超过容量时调整数组大小，所有这些ArrayList 已经为你做了。

于 2012-08-30T17:56:08.957 回答
1

java.util.ArrayDeque支持使用循环缓冲区的队列操作，这可能是在末尾添加和在开头删除的最有效方法，但它不支持按索引进行随机访问 - 除了索引n之外，您不能删除索引处的条目通过遍历迭代器。有一些方法可以删除特定值的第一次/最后一次出现，但这些方法在内部进行线性搜索。

于 2012-08-30T18:00:04.557 回答
1

不知道你所说的java列表是什么意思。您描述的问题听起来像是 LinkedList 的经典案例。该文档指定“所有操作都按照双向链表的预期执行”。这意味着在末尾插入一个对象以及从开头删除一个对象都是在 O(1) 中完成的，这意味着无论列表中有多少元素都需要相同的时间。然而，随机访问更加困难，应该在 O(N) 内完成，这意味着时间与列表中的实际元素数量成正比。

当然，根据您拥有的元素数量，具有 O(1) 的链表可能不会给出最佳时间。例如，如果您只期望列表中的几个元素，那么可能具有 O(N) 添加/删除时间但访问器更快的数据结构实际上可能会执行得更好。但对于较大的结构，LinkedList 类可能是开始的地方。

于 2012-08-30T18:03:32.820 回答