java - JavaのLinkedListでのsize()呼び出しの時間の複雑さは?

Question

タイトルの通り、LinkedList クラスの size() メソッドの償却にかかる時間は O(1) 時間なのか O(n) 時間なのか気になります。

Answer 1

O(1)です。ソースコードをグーグルで検索すると、次のようになります。

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