Modo efficiente per ottenere/rimuovere il primo elemento dall'elenco?

Question

Voglio rimuovere e rimuovere il primo elemento dall'elenco. Posso vedere, ho due opzioni:

Primo approccio:

LinkedList<String> servers = new LinkedList<String>(); 
.... 
String firstServerName = servers.removeFirst(); 

Secondo approccio

ArrayList<String> servers = new ArrayList<String>(); 
.... 
String firstServerName = servers.remove(0); 

ho molti elementi nella mia lista.

• C'è qualche preferenza che dovremmo usare?
• E qual è la differenza tra i due precedenti? Sono tecnicamente la stessa cosa in termini di prestazioni? Qual è la complessità coinvolgere qui se abbiamo molti elementi?

Qual è il modo più efficiente per farlo.

Answer 1

L'utilizzo di un elenco collegato è di gran lunga più veloce.

ListaLinkata

Sarà solo fare riferimento ai nodi in modo che il primo scompare.

ArrayList

Con una lista di array deve spostare tutti gli elementi indietro di un posto per mantenere la matrice sottostante corretta.

Answer 2

La rimozione del primo elemento di ArrayList è O (n). Per l'elenco collegato è O (1), quindi vado con quello.

Controllare l'ArrayList documentation

Le dimensioni, le operazioni EVuota, ottenere, set, iteratore, e ListIterator eseguito in tempo costante. L'operazione di aggiunta viene eseguita in tempo costante ammortizzato, ovvero , l'aggiunta di n elementi richiede tempo O (n). Tutte le altre operazioni vengono eseguite in tempo lineare (approssimativamente). Il fattore costante è basso rispetto a quello dell'implementazione di LinkedList.

questi ragazzi in realtà ottenuto la fonte OpenJDK link

Answer 3

Se il confronto per "rimuovere prima" è tra il ArrayList ei LinkedList classi, i LinkedList vince nettamente.

La rimozione di un elemento da un elenco collegato costa O(1), mentre lo fa per un array (elenco di array) costa O(n).

Answer 4

Assicurarsi di aver compreso la differenza tra LinkedList e ArrayList. ArrayList è implementato usando Array.

LinkedList richiede un tempo costante per rimuovere un elemento. ArrayList potrebbe richiedere tempo lineare per rimuovere il primo elemento (per confermare ho bisogno di controllare l'implementazione, non esperto java qui).

Inoltre penso che LinkedList sia più efficiente in termini di spazio. Poiché ArrayList non dovrebbe (e non dovrebbe) ridimensionare l'array ogni volta che viene rimosso un elemento, occupa più spazio del necessario.

Answer 5

Come altri hanno giustamente sottolineato, LinkedList è più veloce di ArrayList per la rimozione del primo elemento da qualcosa di diverso da una lista molto breve.

Tuttavia, per fare la vostra scelta tra di loro è necessario considerare il mix completo di operazioni. Ad esempio, se il tuo carico di lavoro fa milioni di accessi indicizzati a un elenco di cento elementi per ogni rimozione del primo elemento, ArrayList sarà complessivamente migliore.

Answer 6

In termini pratici, LinkedList#removeFirst è più efficiente poiché funziona su una lista doppiamente collegata e la rimozione del primo elemento consiste essenzialmente nel solo scollegarlo dal capo dell'elenco e aggiornare l'elemento successivo in modo che sia il primo:

private E unlinkFirst(Node<E> f) { 
    // assert f == first && f != null; 
    final E element = f.item; 
    final Node<E> next = f.next; 
    f.item = null; 
    f.next = null; // help GC 
    first = next; 
    if (next == null) 
     last = null; 
    else 
     next.prev = null; 
    size--; 
    modCount++; 
    return element; 
} 

ArrayList#remove sta operando su una matrice interna che richiede shiftting tutti subsequents elementi di una posizione a sinistra copiando il subarray:

public E remove(int index) { 
    rangeCheck(index); 

    modCount++; 
    E oldValue = elementData(index); 

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

    return oldValue; 
} 

altra hand, LinkedList#get operazione richiede attraversando la metà dell'intero elenco per il recupero di un elemento in un indice specificato - nel peggiore dei casi. ArrayList#get accede direttamente all'elemento all'indice specificato poiché opera su un array.

La mia regola di pollice per l'efficienza qui sarebbe:

• Usa LinkedList se si fa un sacco di add/remove in confronto con operazioni di recupero (ad es .: get);
• Utilizzare ArrayList se si esegue un lotto di operazioni di recupero rispetto a add/remove.

Answer 7

Terzo Avvocato.

Viene esposto dall'interfaccia java.util.Queue. LinkedList è un'implementazione di questa interfaccia.

L'interfaccia della coda espone il metodo E poll() che rimuove efficacemente la testa dell'elenco (coda).

In termini di prestazioni il metodo poll() è paragonabile a removeFirst(). In realtà sta usando sotto il cappuccio il metodo removeFirst().

Answer 8

Penso che quello che ti serve sia un ArrayDeque (una classe trascurata ingiustamente in java.util). Il suo metodo removeFirst funziona in O (1) come per LinkedList, mentre generalmente mostra le migliori caratteristiche di spazio e tempo di ArrayList. È implementato come una coda circolare in un array.

Molto raramente si deve usare LinkedList. Ho fatto una volta nei miei 17 anni come programmatore Java e mi sono pentito in retrospettiva.

Answer 9

In caso di ArrayList rimuovere il primo elemento ha complessità O (n), in modo tale alternativa è possibile ottenere il primo elemento e invece di rimuoverlo basta chiamare List.subList(int fromIndex, int toIndex):

final String firstServerName = servers.get(0); 
servers = servers.subList(1, servers.size());