CODEWITHSUNDEEP
javaperformancecollectionsbig-o
Mark McDonald
Mark McDonald

Reputation: 8180

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

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)?)

Upvotes: 18

Views: 15178

Answers (5)

Yaneeve
Yaneeve

Reputation: 4779

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()

Upvotes: 2

Bill the Lizard
Bill the Lizard

Reputation: 405735

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.)

Upvotes: 1

Eyal Schneider
Eyal Schneider

Reputation: 22446

The implementation of LinkedList.getLast() leaves no doubts - it's an O(1) operation. However, I didn't find it documented anywhere.

Upvotes: 0

user319799
user319799

Reputation:

It is O(1) because the list is doubly-linked. It keeps references to both head and tail.

From documentation:

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Upvotes: 33

Jeff Storey
Jeff Storey

Reputation: 57192

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.

Upvotes: 5

Related Questions