La LinkedList di Java è ottimizzata per ottenere (indice) al contrario quando necessario?

Question

Ho lavorato su alcuni modi per ottimizzare LinkedList. Qualcuno sa se la classe LinkedList con doppia connessione predefinita Java è ottimizzata per fare operazioni get() al contrario? Per esempio:

// Some LinkedList list that exists with n elements; 
int half = list.size()/2; 
list.get(half + 1); 

sarebbe la chiamata al list.get(half + 1) ottimizzare la ricerca e andare in senso inverso in quanto si tratta di una lista doppiamente legata? Avrebbe più senso fare la ricerca dalla fine e andare verso il centro se si sa che l'elemento è nella seconda metà della lista.

So che l'utilizzo di get(index) è O(n) e che è necessario utilizzare un iteratore quando si attraversa una LinkedList, ma sono solo curioso.

Answer 1

Sì, lo è. È possibile esaminare il codice sorgente da soli: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29

LinkedList#get(int) è implementato come solo

return entry(index).element; 

dove entry è un metodo privato. Definizione entry s' è:

private Entry<E> entry(int index) { 
    if (index < 0 || index >= size) 
     throw new IndexOutOfBoundsException("Index: "+index+ 
              ", Size: "+size); 
    Entry<E> e = header; 
    if (index < (size >> 1)) { 
     for (int i = 0; i <= index; i++) 
      e = e.next; 
    } else { 
     for (int i = size; i > index; i--) 
      e = e.previous; 
    } 
    return e; 
} 

Come si può vedere, il conto alla rovescia a partire dalla fine se index è maggiore del punto medio della lista.