Какова временная сложность вызова size () для LinkedList в Java?

Question

Как видно из заголовка, мне интересно, занимает ли метод size () в классе LinkedList амортизированное O (1) или O (n) время.

Answer 1

Это O (1). Вы можете поискать исходный код в Google и вы придете к такому:

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

Все классы Collection, которые я рассмотрел, хранят размер как переменную и не перебирают все, чтобы получить его.

Answer 2

O (1), как вы бы обнаружили, если бы вы смотрели на исходный код ...

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