logo标签列表

Java ArrayList如何在开头添加元素

javaarraysarrayliststack
264

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

有没有人有什么建议？

1
你是指像 remove 和 add 这样的操作吗？ - Peter Lawrey
你正在使用 arraylist stack queue whatever 做什么？因为在数组的开头添加元素是最好避免的，听起来你应该使用不同的集合。 - Peter Lawrey
首先，你应该自己动手做点什么。你到目前为止做了什么？ - Yegoshin Maxim
16个回答
419

List 提供了 add(int, E) 方法，因此您可以使用以下代码：

list.add(0, yourObject);

接下来，您可以使用以下方法删除最后一个元素：

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

然而，您可能需要重新考虑您的要求或使用不同的数据结构，例如队列。

编辑

也许可以看看Apache的CircularFifoQueue：

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

只需用您的最大大小初始化它即可：

CircularFifoQueue queue = new CircularFifoQueue(10);
10
我不会碰任何Apache库，特别是因为Guava的集合类存在。在这里，Guava的EvictingQueue可能是一个不错的选择。 - DPM
39

使用特定的数据结构

有各种优化了在第一个索引处添加元素的数据结构。但请注意，如果您将集合转换为其中一种数据结构，则转换可能需要时间和空间复杂度为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 cheatsheet。

反转链表

一种非常简单但效率较低的方法是使用 reverse：

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

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

分析

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

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

将列表反转两次。与上述已接受的解决方案相比，它会大幅增加算法的运行时间吗？ - Samyak Upadhyay
它会增加2n，所以是的，但如果你有少于50个元素的列表，你将无法在大多数现代计算机上微基准测试差异。 - Patrick
14
您可以查看add(int index, E element)方法:

将指定元素插入到列表的指定位置。 将该位置当前存在的元素（如果有）和任何后续元素向右移位（其索引加一）。

添加后，您可以检查ArrayList的大小，并删除末尾的元素。

6

您可能需要查看双端队列。它可以直接访问列表中的第一个和最后一个项目。

1
我很惊讶你是唯一一个提到Deque的答案，这显然是最优解决方案。 - Guillaume F.
4
您所描述的情况，使用队列(Queue)是合适的。
由于您想要添加(add)新元素，并删除(remove)旧元素，您可以在末尾添加并从开头删除。这不会有太大的差别。
队列有add(e)和remove()方法，它们在末尾添加新元素，并从开头移除旧元素。
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(5);
queue.add(6);
queue.remove();  // Remove 5

因此，每当您向队列中添加一个元素时，您可以使用remove方法调用进行备份。
更新： 如果您想要固定Queue的大小，则可以查看：ApacheCommons＃CircularFifoBuffer 从文档中可以看到：

CircularFifoBuffer是一个具有固定大小的先进先出缓冲区，如果已满则替换其最旧的元素。

Buffer queue = new CircularFifoBuffer(2); // Max size

queue.add(5);
queue.add(6);
queue.add(7);  // Automatically removes the first element `5`

正如您所看到的，当达到最大大小时，添加新元素会自动删除插入的第一个元素。

3

我认为实现应该很简单，但考虑到效率，您应该使用LinkedList而不是ArrayList作为容器。您可以参考以下代码：

import java.util.LinkedList;
import java.util.List;

public class DataContainer {

    private List<Integer> list;

    int length = 10;
    public void addDataToArrayList(int data){
        list.add(0, data);
        if(list.size()>10){
            list.remove(length);
        }
    }

    public static void main(String[] args) {
        DataContainer comp = new DataContainer();
        comp.list = new LinkedList<Integer>();

        int cycleCount = 100000000;

        for(int i = 0; i < cycleCount; i ++){
            comp.addDataToArrayList(i);
        }
    }
}
3
2
你可以使用列表方法，删除和添加。
list.add(lowestIndex, element);
list.remove(highestIndex, element);
2
从Java 21开始，List接口扩展了SequencedCollection接口，该接口具有以下方法：
interface SequencedCollection<E> extends Collection<E> {
  SequencedCollection<E> reversed();
  void addFirst(E);
  void addLast(E);
  E getFirst();
  E getLast();
  E removeFirst();
  E removeLast();
}

在JEP 431: Sequenced Collections中有更多详细信息。

因此，与第一个/最后一个元素一起工作变得更简单：

list.addFirst(new Object());

...

if (list.size() > 10) {
  list.removeLast();
}

注意事项：

  • 请记住，从ArrayList中删除最后一个元素的时间复杂度为O(1)，而在ArrayList的开头添加一个元素的时间复杂度为O(n)，因为这将需要将所有现有元素向后移动一个位置。所以，建议考虑其他人提到的ArrayDeque。
  • 如果列表为空，List.removeLast会抛出NoSuchElementException。
1

你可以使用这段代码

private List myList = new ArrayList();
private void addItemToList(Object obj){
    if(myList.size()<10){
      myList.add(0,obj);
    }else{
      myList.add(0,obj);
      myList.remove(10);
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接