Какова временная сложность LinkedList.getLast() в Java?

У меня есть собственный LinkedList в Java-классе и вам часто нужно будет получить последний элемент в списке. Списки должны масштабироваться, поэтому я пытаюсь решить, нужно ли мне ссылаться на последний элемент, когда я вношу изменения (для достижения O (1)), или если класс LinkedList делает это уже с вызовом getLast().

Какова стоимость Big-O LinkedList.getLast() и , она документирована? (то есть я могу полагаться на этот ответ или не делать никаких предположений и кешировать его, даже если он O (1)?)

Ответ 1

Это O (1), потому что список дважды связан. Он держит ссылки на голову и хвост.

Из документации:

Операции, которые индексируются в список, будут перемещаться по списку из начала или конца, в зависимости от того, что ближе к указанному индексу.

Ответ 2

Это O (1), и вам не нужно кэшировать его. Метод getLast просто возвращает header.previous.element, поэтому вычислений и обхода списка нет. Связанный список замедляется, когда вам нужно найти элементы в середине, так как он запускает один конец и перемещает по одному элементу за раз.

Ответ 3

Из исходного кода 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()

Ответ 4

Из LinkedList docs:

Все операции выполняются так же, как можно было бы ожидать для двусвязного списка. Операции, которые индексируются в список, будут перемещаться по списку от начала или до конца, в зависимости от того, что ближе к указанному индексу.

Это должно быть O (1), так как двусвязный список будет иметь ссылку на собственный хвост. (Даже если он явно не ссылается на свой хвост, то O (1) найдет свой хвост.)

Ответ 5

Реализация LinkedList.getLast() не оставляет сомнений - это операция O (1). Тем не менее, я нигде не нашел документально.