Độ phức tạp thời gian của một kích thước() gọi trên một LinkedList trong Java là gì?

Question

Khi tiêu đề hỏi, tôi tự hỏi liệu phương thức size() trong lớp LinkedList có phân bổ thời gian O (1) hoặc O (n) không.

Answer 1

Đó là O (1). Bạn có thể google cho mã nguồn và bạn sẽ đến như vậy:

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

Tất cả các lớp học Bộ sưu tập Tôi đã xem xét tại cửa hàng một kích thước như là một biến và không lặp qua tất cả mọi thứ để có được nó .

Answer 2

O (1) như bạn sẽ nhận thấy có bạn nhìn vào mã nguồn ...

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