Quelle est la complexité temporelle de LinkedList.getLast() en Java?

Question

J'ai une LinkedList privée dans une classe Java & aura souvent besoin de récupérer le dernier élément de la liste. Les listes doivent être redimensionnées, donc j'essaie de décider si je dois garder une référence au dernier élément quand j'apporte des changements (pour obtenir O (1)) ou si la classe LinkedList le fait déjà avec l'appel getLast() .

Quel est le coût big-O de LinkedList.getLast() et est-il documenté? (est-ce que je peux me fier à cette réponse ou devrais-je faire des hypothèses & le cacher même si c'est O (1)?)

Answer 1

C'est O (1) parce que la liste est doublement liée. Il garde des références à la fois la tête et la queue.

De la documentation:

Opérations index dans la liste traversera la liste depuis le début ou la fin, si elle est plus proche de l'index spécifié.

Answer 2

Il s'agit de O (1) et vous ne devriez pas avoir à le mettre en cache. La méthode getLast renvoie simplement header.previous.element, donc il n'y a pas de calcul et pas de traversée de la liste. Une liste liée ralentit lorsque vous devez trouver des éléments au milieu car elle commence une extrémité et déplace un élément à la fois.

Answer 3

Des LinkedList docs:

Toutes les opérations effectuent comme on pouvait s'y attendre pour une liste doublement liée. Les opérations indexées dans la liste traverseront la liste depuis le début ou la fin, selon la plus proche de l'index spécifié.

Il devrait s'agir de O (1) puisqu'une liste à double liaison aura une référence à sa propre queue. (Même si elle ne explicitement garder une référence à sa queue, il sera O (1) à trouver sa queue.)

Answer 4

La mise en œuvre de LinkedList.getLast() ne laisse aucun doute - c'est un O (1) opération. Cependant, je ne l'ai trouvé documenté nulle part.

Answer 5

À partir du code source 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; 
    } 

... 

} 

si c'est O (1) pour les deux getFirst() & getLast()