Độ phức tạp của LinkedList.getLast() trong Java là bao nhiêu?

Question

Tôi có một LinkedList riêng trong một lớp Java & sẽ thường xuyên cần truy xuất phần tử cuối cùng trong danh sách. Các danh sách cần phải mở rộng, vì vậy tôi đang cố gắng quyết định xem có cần tham chiếu đến phần tử cuối cùng khi tôi thực hiện thay đổi (để đạt được O (1)) hay không nếu lớp LinkedList thực hiện với lệnh getLast() .

Chi phí O-lớn của LinkedList.getLast() và là tài liệu gì? (tức là tôi có thể dựa vào câu trả lời này hoặc tôi nên không đưa ra giả định & cache ngay cả khi đó là O (1)?)

Answer 1

Đó là O (1) vì danh sách được liên kết kép. Nó giữ tham chiếu đến cả đầu và đuôi.

Từ tài liệu:

Operations rằng chỉ số vào danh sách sẽ đi qua danh sách từ đầu hoặc cuối cùng, nào là gần gũi hơn với các chỉ số cụ thể.

Answer 2

Đó là O (1) và bạn không cần phải lưu bộ nhớ cache. Phương thức getLast chỉ trả về header.previous.element, vì vậy không có tính toán và không có traversal của danh sách. Danh sách được liên kết sẽ chậm lại khi bạn cần tìm các phần tử ở giữa nó vì nó bắt đầu một đầu và di chuyển một phần tử tại một thời điểm.

Answer 3

Từ LinkedList tài liệu:

Tất cả các hoạt động thực hiện như có thể được dự kiến ​​cho một danh sách gấp đôi được liên kết. Các hoạt động mà chỉ mục trong danh sách sẽ đi qua danh sách từ đầu hoặc cuối, tùy theo điều nào gần với chỉ mục được chỉ định.

Phải là O (1) kể từ danh sách được liên kết kép sẽ có tham chiếu đến đuôi của chính nó. (Thậm chí nếu nó không rõ ràng giữ một tham chiếu đến đuôi của nó, nó sẽ là O (1) tìm đuôi của nó.)

Answer 4

Việc thực hiện LinkedList.getLast() không để lại nghi ngờ - đó là một O (1) hoạt động. Tuy nhiên, tôi không tìm thấy tài liệu ở bất cứ đâu.

Answer 5

Từ mã nguồn Java 6:

* @author Josh Bloch 
* @version 1.67, 04/21/06 
* @see  List 
* @see  ArrayList 
* @see  Vector 
* @since 1.2 
* @param <E> the type of elements held in this collection 
*/ 

public class LinkedList<E> 
    extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable 
{ 
    private transient Entry<E> header = new Entry<E>(null, null, null); 
    private transient int size = 0; 

    /** 
    * Constructs an empty list. 
    */ 
    public LinkedList() { 
     header.next = header.previous = header; 
    } 

... 

    /** 
    * Returns the first element in this list. 
    * 
    * @return the first element in this list 
    * @throws NoSuchElementException if this list is empty 
    */ 
    public E getFirst() { 
    if (size==0) 
     throw new NoSuchElementException(); 

    return header.next.element; 
    } 

    /** 
    * Returns the last element in this list. 
    * 
    * @return the last element in this list 
    * @throws NoSuchElementException if this list is empty 
    */ 
    public E getLast() { 
    if (size==0) 
     throw new NoSuchElementException(); 

    return header.previous.element; 
    } 

... 

} 

vì vậy đó là O (1) cho cả getFirst() & getLast()