Quelle est la complexité temporelle d'une taille () sur un appel LinkedList en Java?

Question

Comme le titre demande, je me demande si la méthode taille () dans la classe LinkedList prend amorti O (1) ou le temps O (n).

Answer 1

Il est O (1). Vous pouvez google pour le code source et vous arriverez à tel:

De http://www.docjar.com/html /api/java/util/LinkedList.java.html

Toutes les classes de la collection J'ai regardé au magasin une taille en tant que variable et n'itérer pas par tout pour l'obtenir.

Answer 2

O (1) que vous auriez trouvé aviez-vous regardé le code source ...

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