data structures - 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?

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