Rimozione dell'ultimo oggetto di ArrayList in Java

Question

Desidero rimuovere rapidamente l'ultimo oggetto da un ArrayList.

So che remove(Object O) prende O(n) in un ArrayList, ma mi chiedo se è possibile farlo in un tempo costante da quando voglio solo rimuovere l'ultimo oggetto ?

Answer 1

Vedi the documentation for ArrayList#remove(int), come nel seguente sintassi:

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

Ecco come è implementato. elementData esegue una ricerca sull'array di supporto (in modo che possa essere rimosso dall'array), che dovrebbe essere costante (poiché la JVM conosce le dimensioni di un riferimento a un oggetto e il numero di voci che può calcolare l'offset) e numMoved è 0 per questo caso:

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