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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 4

Из LinkedList документов:

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

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

Answer 5

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