Removing last object of ArrayList in Java

Question

I want to remove the last object from an ArrayList quickly.

I know that remove(Object O) takes O(n) in an ArrayList, but I wonder if it is possible to do this in constant time since I just want to remove the last object?

Gavette

There is also remove(int)... – Camass

list.remove(list.size()-1) !!! – Desdamona

Would a stack be a better solution here? – Kingofarms

Removing the last element is a constant time operation since no elements needed to be shifted to the left – Teflon

Continuing from @Zim-ZamO'Pootertoot comment, remember that big-O represents the upper bound, better known as the worst case. – Earthwork

First things first, if you are attempting to remove an element based on position (last) do not use the remove element that searches the list and might remove from any position. – Mercy

@TheNewIdiot You should have posted that as an answer... D: – Grime

@thegrinner: "big-o" != "worst-case". – Camass

@TheNewIdiot I know how the syntax looks like , the question (Which is answered by Wchargin), is about the time complexity ! not the syntax – Gavette

@Gavette Hosseinzadeh , Ok if you knew the syntax then probably I assume that you would have gone through its implementation code-wise before asking this here , if not , then it is a bad question showing no effort on your part :) – Desdamona

@TheNewIdiot : if you look at the answer , you see that they say remove(int index) takes O(n) time , this was the effort I made :) #6541011 – Gavette

@Earthwork No it doesn't. It represents the average. Consider a hash lookup: O(1) on average, but worst case O(N). QuikSort: O(Nlog(N))* on average, worst case O(N^2). – Fluorosis

@JohnB He isn't using a searching remove(). – Fluorosis

Answer 1

See the documentation for ArrayList#remove(int), as in the following syntax:

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

Here is how it's implemented. elementData does a lookup on the backing array (so it can cut it loose from the array), which should be constant time (since the JVM knows the size of an object reference and the number of entries it can calculate the offset), and numMoved is 0 for this case:

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;
}

Milne

O1 for this? arraycopy entire up to, or just cutting the array loose from end ? – Ted

Answer 2

Since Java 21, simply using List.removeLast, for example:

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

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

Note: if the list is not empty, the implementation of List.removeLast returns the result of calling remove(size() - 1). Otherwise, it throws NoSuchElementException.

The time complexity of removing the last element from ArrayList is O(1) - it is just decrementing the size of the list by 1 under the hood.

Loehr

Answer 3

Just simply use.

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

Nickels

that was answered already (I promise I wasn't the one who downvoted you, but that's probably why somebody did). – Spartan

The question is whether it is possible to do it in constant time, and you haven't answered that. – Fluorosis