What is the time complexity of LinkedList.getLast() in Java?

12,567

Solution 1

It is O(1) and you should not have to cache it. The getLast method simply returns header.previous.element, so there is no computation and no traversal of the list. A linked list slows down when you need to find elements in the middle it since it starts one end and moves one element at a time.

Solution 2

From the Java 6 source code:

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

...

}

so that's O(1) for both getFirst() & getLast()

Solution 3

From the LinkedList docs:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

It should be O(1) since a doubly-linked list will have a reference to its own tail. (Even if it doesn't explicitly keep a reference to its tail, it will be O(1) to find its tail.)

Share:
12,567
Mark McDonald
Author by

Mark McDonald

Developer Relations at Google. Home brewer.

Updated on June 13, 2022

Comments

  • Mark McDonald
    Mark McDonald over 1 year

    I have a private LinkedList in a Java class & will frequently need to retrieve the last element in the list. The lists need to scale, so I'm trying to decide whether I need to keep a reference to the last element when I make changes (to achieve O(1)) or if the LinkedList class does that already with the getLast() call.

    What is the big-O cost of LinkedList.getLast() and is it documented? (i.e. can I rely on this answer or should I make no assumptions & cache it even if it's O(1)?)

  • Akh
    Akh over 12 years
    You might have to look into the Java Source Code for implementation details like Yaneeve did. You can attach java core lib source code to IDE.