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