在Java中删除ArrayList的最后一个对象

Question

我想快速地从一个 ArrayList 中移除最后一个对象。

我知道在 ArrayList 中使用 remove(Object O) 的时间复杂度为 O(n)，但我想知道是否可以在常数时间内完成操作，因为我只需要移除 最后一个 对象？

- Arian

---

list.remove(list.size()-1) 的意思是从列表中删除最后一个元素。 - AllTooSir

这里使用栈会更好吗？ - Justin Jasmann

删除最后一个元素是一个常数时间操作，因为不需要将任何元素向左移动。 - Zim-Zam O'Pootertoot

@TheNewIdiot 你应该把那个发表为答案... D: - Fritz

@thegrinner：“大O” != “最坏情况”。 - Oliver Charlesworth

Answer 1

请参阅ArrayList#remove(int)的文档，如下所示：

list.remove(list.size() - 1)

实现方式如下。 elementData 在后备数组上进行查找（因此可以从数组中将其削除），这应该是常数时间（因为JVM知道对象引用的大小和它可以计算偏移量的条目数），而且对于这种情况，numMoved 是0：

public E remove(int index) {
    rangeCheck(index); // throws an exception if out of bounds

    modCount++;        // each time a structural change happens
                       // used for ConcurrentModificationExceptions

    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

- Nathan Hughes

---

这个问题是关于O1的吗？是复制整个数组还是仅截取数组末尾？ - mjs

Answer 2

自从Java 21以来，只需简单地使用List.removeLast，例如：

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));

System.out.println(list.removeLast()); // 3 - removes and returns the last element

注意：如果列表不为空，则List.removeLast的实现返回调用remove(size() - 1)的结果。否则，它会抛出NoSuchElementException。

从ArrayList中删除最后一个元素的时间复杂度为O(1)，它只是在底层将列表的大小减少1。

- Oleksandr Pyrohov

Answer 3

只需要简单地使用。

arraylist.remove(arraylist.size() - 1)

- Deva

---

那个问题已经得到回答了。（我保证我不是给你点踩的那个人，但可能正因为如此才有人这么做）。 - Sapphire_Brick

问题是是否有可能在恒定的时间内完成，而你还没有回答这个问题。 - user207421