55

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?

Alexander Farber
  • 21,519
  • 75
  • 241
  • 416
Arian
  • 7,397
  • 21
  • 89
  • 177
  • There is also `remove(int)`... – Oliver Charlesworth Jun 07 '13 at 15:28
  • 26
    `list.remove(list.size()-1)` !!! – AllTooSir Jun 07 '13 at 15:29
  • 2
    Would a stack be a better solution here? – Justin Jasmann Jun 07 '13 at 15:30
  • 6
    Removing the last element is a constant time operation since no elements needed to be shifted to the left – Zim-Zam O'Pootertoot Jun 07 '13 at 15:31
  • Continuing from @Zim-ZamO'Pootertoot comment, remember that [big-O](http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations) represents the *upper* bound, better known as the worst case. – thegrinner Jun 07 '13 at 15:35
  • 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. – John B Jun 07 '13 at 15:41
  • 2
    @TheNewIdiot You should have posted that as an answer... D: – Fritz Jun 07 '13 at 15:47
  • 1
    @thegrinner: "big-o" != "worst-case". – Oliver Charlesworth Jun 07 '13 at 16:02
  • @TheNewIdiot I know how the syntax looks like , the question (Which is answered by Wchargin), is about the time complexity ! not the syntax – Arian Jun 07 '13 at 16:03
  • 1
    @Arian 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 :) – AllTooSir Jun 07 '13 at 16:05
  • @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 :) http://stackoverflow.com/questions/6540511/time-complexity-for-java-arraylist – Arian Jun 07 '13 at 16:20
  • @thegrinner No it doesn't. It represents the average. Consider a hash lookup: *O(1)* on average, but worst case *O(N).* QuikSort: *O(N*log(N))* on average, worst case *O(N^2).* – user207421 Aug 28 '23 at 00:27
  • @JohnB He isn't using a searching `remove()`. – user207421 Aug 28 '23 at 00:29

3 Answers3

92

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;
}
Nathan Hughes
  • 94,330
  • 19
  • 181
  • 276
  • 1
    O1 for this? arraycopy entire up to, or just cutting the array loose from end ? – mjs Sep 21 '20 at 11:39
0

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.

Oleksandr Pyrohov
  • 14,685
  • 6
  • 61
  • 90
-2

Just simply use.

arraylist.remove(arraylist.size() - 1)
Deva
  • 1,851
  • 21
  • 22