Какова временная сложность LinkedList.getLast () в Java?
Я имею частный LinkedList в классе Java и должен буду часто получать последний элемент в списке. Списки должны масштабироваться, таким образом, я пытаюсь решить, должен ли я сохранить ссылку на последний элемент, когда я вношу изменения (для достижения O (1)) или если класс LinkedList уже делает это с getLast () вызов.
Какова большая-O стоимость LinkedList.getLast (), и это документируется? (т.е. я могу полагаться на этот ответ, или я не должен делать предположения и кэшировать его, даже если это - O (1)?)
5 ответов
Это 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.getLast () не оставляет сомнений - это операция O (1). Однако я не нашел это задокументировано где угодно.
Из документов LinkedList :
Все операции выполняются так, как и следовало ожидать от двусвязного списка. Операции, которые индексируют список, будут перемещаться по списку от начала или до конца, в зависимости от того, что ближе к указанному индексу.
Это должно быть O (1), поскольку двусвязный список будет иметь ссылку на свой собственный хвост. (Даже если он не явно сохраняет ссылку на свой хвост, он будет от O (1) до найти свой хвост.)