Qual è la complessità temporale di una chiamata size() su una LinkedList in Java?

Question

Come chiede il titolo, mi chiedo se il metodo size() nella classe LinkedList impiega tempo O (1) o O (n) ammortizzato.

Answer 1

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 .

Answer 2

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