¿Cuál es la complejidad de tiempo de LinkedList.getLast() en Java?

Question

Tengo un LinkedList privado en una clase Java & con frecuencia necesitará recuperar el último elemento en la lista. Las listas necesitan escalar, así que estoy tratando de decidir si necesito mantener una referencia al último elemento cuando realizo cambios (para lograr O (1)) o si la clase LinkedList hace eso con la llamada getLast() .

¿Cuál es el costo de O de LinkedList.getLast() y está documentado? (es decir, ¿puedo confiar en esta respuesta o no debo hacer ninguna suposición & almacenarla en caché aunque sea O (1)?)

Answer 1

O (1) porque la lista está doblemente vinculada. Mantiene referencias tanto a la cabeza como a la cola.

De la documentación:

Las operaciones que índice en la lista será recorrer la lista desde el principio o el final, el que está más cerca del índice especificado.

Answer 2

Es O (1) y no debería tener que almacenarlo en caché. El método getLast simplemente devuelve header.previous.element, por lo que no hay cómputo ni recorrido de la lista. Una lista vinculada se ralentiza cuando necesita encontrar elementos en el medio, ya que comienza un extremo y mueve un elemento a la vez.

Answer 3

De los documentos LinkedList:

Todas las operaciones realizan como podría esperarse de una lista doblemente enlazada. Las operaciones que indizan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca del índice especificado.

Debería ser O (1) ya que una lista doblemente enlazada tendrá una referencia a su propia cola. (Incluso si no lo hace de forma explícita mantener una referencia a su cola, será O (1) para encontrar su cola.)

Answer 4

La implementación de LinkedList.getLast() no deja dudas - es una O (1) operación. Sin embargo, no encontré documentado en ninguna parte.

Answer 5

A partir del código fuente de 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; 
    } 

... 

} 

así que es O (1) tanto para getFirst() & getLast()