Java中LinkedList.getLast（）的时间复杂度是多少？

问题描述：

我有一个Java类中的私人LinkedList &将经常需要检索列表中的最后一个元素。列表需要扩展，所以我试图决定是否需要保留对最后一个元素的引用（当实现O（1））时，或者LinkedList类已经使用getLast（）调用。Java中LinkedList.getLast（）的时间复杂度是多少？

什么是LinkedList.getLast（）和的大O成本是否记录在案？（即我可以靠这个答案，或者我应该做任何假设&缓存，即使它是O（1）？）

答

是O（1），因为名单双向链接。它保持对头部和尾部的引用。

从技术文档：

编索引的操作列表将遍历从一开始或结束时，取其更接近指定索引列表。

它不仅双向链表O（1），这也是循环。 – helpermethod 2010-05-04 13:42:22

+1引用规范 – 2010-05-04 17:15:40

helpermethod的“循环”评论清楚地回答了这个问题。 – 2016-01-23 03:13:26

答

这是O（1），你不应该缓存它。 getLast方法只返回header.previous.element，所以没有计算和列表的遍历。当您需要在中间找到元素时，链表会变慢，因为它从一端开始并一次移动一个元素。

答

从LinkedList文档：

所有操作的执行是可以预期的双向链表。索引到列表中的操作将从开始或结束遍历列表，以哪个更接近指定的索引为准。

它应该是O（1），因为一个双向链表将引用它自己的尾部。（即使它不明确保持其尾部的参考，这将是O（1）找到它的尾巴。）

答

LinkedList.getLast（）的实施，不留怀疑 - 这是一个O（1）操作。但是，我没有在任何地方找到它。

您可能需要查看Java源代码以了解像Yaneeve那样的实现细节。您可以将Java核心lib源代码附加到IDE。 – AKh 2011-03-13 21:38:19

答

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

... 

}

所以这两个getFirst() & getLast()

Java中LinkedList.getLast（）的时间复杂度是多少？

相关推荐