Java'da LinkedList'te bir boyutlu() çağrının zaman karmaşıklığı nedir?

Question

Başlığın soracağı gibi, LinkedList sınıfındaki size() yönteminin amortize edilmiş O (1) zaman veya O (n) zamanını alıp almadığını merak ediyorum.

Answer 1

O var O (1). Kaynak kodu için google olabilir ve böyle gelecek: http://www.docjar.com/html/api/java/util/LinkedList.java.html

itibaren

Ben bir değişken olarak boyutta bir mağazada baktım Koleksiyon sınıfların tamamı ve bunu elde etmek için her şeyi yinelemenize yok .

Answer 2

O (1) bulurdum gibi LinkedList itibaren ... kaynak koduna

baktım vardı:

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