Java中的LIKEDList.GETLAST()的时间复杂度是多少?

它是O(1),因为列表是双重链接的。它保持对头部和尾部的引用。

来自文档:

索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。

它是O(1),您不必缓存它。getlast方法只返回 header.previous.element ,所以没有计算,也没有遍历列表。当需要在中间查找元素时,链接列表会变慢,因为它从一端开始,一次移动一个元素。

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

...

}

所以这两个都是O(1) getFirst() 和; getLast()

从 LinkedList 文档:

对于双重链接列表,所有操作都按预期执行。索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。

它应该是O(1),因为一个双重链接的列表将有一个对它自己的尾部的引用。(即使没有 明确地 参照它的尾巴,它将是o(1)到 找到 它的尾巴)

linkedlist.getlast()的实现毫无疑问—它是一个O(1)操作。 但是,我没有发现它记录在任何地方。