Java ArrayList如何在开头添加元素

Question

我需要将元素添加到 ArrayList 队列中，但是当我调用函数添加元素时，我希望它在数组的开头添加元素（因此它具有最低索引）并且如果数组有 10 个元素，则添加一个新元素会导致删除最旧的元素（索引最高的元素）。

有没有人有什么建议？

原文由 ZeDonDino 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

List 有方法 add(int, E) ，所以你可以使用：

 list.add(0, yourObject);

之后你可以删除最后一个元素：

 if(list.size() > 10)
    list.remove(list.size() - 1);

但是，您可能需要重新考虑您的要求或使用不同的数据结构，例如 Queue

编辑

也许看看 Apache 的 CircularFifoQueue ：

CircularFifoQueue 是一个具有固定大小的先进先出队列，如果已满则替换其最旧的元素。

只需用最大尺寸初始化它：

 CircularFifoQueue queue = new CircularFifoQueue(10);

原文由 Baz 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

使用特定的数据结构

有多种数据结构针对在第一个索引处添加元素进行了优化。不过请注意，如果您将集合转换为其中之一，对话可能需要时间和空间复杂度 O(n)

双端队列

JDK 包括 Deque 结构，它提供类似 addFirst(e) 和 offerFirst(e) 的方法

Deque<String> deque = new LinkedList<>();
deque.add("two");
deque.add("one");
deque.addFirst("three");
//prints "three", "two", "one"

分析

插入的空间和时间复杂度为 LinkedList 常量 ( O(1) )。请参阅 Big-O 备忘单。

反转列表

一个非常简单但效率低下的方法是使用反向：

  Collections.reverse(list);
 list.add(elementForTop);
 Collections.reverse(list);

如果您使用 Java 8 流，您可能会对这个答案感兴趣。

分析

• 时间复杂度： O(n)
• 空间复杂度： O(1)

查看 JDK 实现，它具有 O(n) 时间复杂度，因此仅适用于非常小的列表。

原文由 Patrick 发布，翻译遵循 CC BY-SA 3.0 许可协议