Come chiede il titolo, mi chiedo se il metodo size() nella classe LinkedList impiega tempo O (1) o O (n) ammortizzato.Qual è la complessità temporale di una chiamata size() su una LinkedList in Java?
risposta
E 'O (1). È possibile google per il codice sorgente e si arriva a tale:
Da http://www.docjar.com/html/api/java/util/LinkedList.java.html
Tutte le classi collezione che ho guardato un negozio di dimensioni come una variabile e non scorrere tutto per ottenerlo .
ctrl-clic in NetBeans lo troverà ancora più veloce di google;) – Superole
O (1) come si sarebbe trovato aveva guardato il codice sorgente ...
Da LinkedList:
private transient int size = 0;
...
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
E se non stai usando l'implementazione di Sun? http://en.wikipedia.org/wiki/Java_Class_Library#Alternative_implementations Penso che la sua domanda sia se è garantito che sia O (1), piuttosto che se sia O (1) in qualsiasi specifica implementazione/versione. – jalf
L'implementazione è stata la stessa da 1.2 quando è stato introdotto LinkedList, quindi sarà sempre O (1) –
Questo è da Java 1.6. Questo non dipende dalla VM ma (in teoria) potrebbe essere diverso nelle versioni precedenti della libreria standard. Controlla la sorgente della tua versione se vuoi essere sicuro al 100%, ma nessuno sviluppatore sano calcolerebbe le dimensioni su richiesta per qualcosa di simile in cui tutto è in memoria e puoi calcolarlo mentre la struttura viene creata. – Kris
Nota: per le strutture concorrenti, le dimensioni di calcolo possono essere lente e comunque inutili. –