Czy lista powiązań Java jest zoptymalizowana, aby w razie potrzeby uzyskać (indeks) odwrotność?

Question

Pracuję nad sposobami optymalizacji LinkedList's. Czy ktoś wie, czy domyślnie podwójnie połączona Java klasy LinkedList jest zoptymalizowana do wykonywania operacji odwrotnej? Na przykład:

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

Czy wezwanie do list.get(half + 1) zoptymalizować szukanie i pójść w odwrotnym kierunku, ponieważ jest to podwójnie połączonej listy? Bardziej sensowne byłoby wykonanie wyszukiwania od końca i przejście do środka, jeśli wiesz, że element znajduje się na drugiej połowie listy.

Wiem, że używanie get(index) jest O(n) czasu i że powinieneś używać iteratora podczas przechodzenia przez LinkedList, ale jestem po prostu ciekawy.

Answer 1

Tak jest. Można skontrolować kod źródłowy siebie: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29

LinkedList#get(int) jest zaimplementowany jako tylko

return entry(index).element; 

gdzie entry to prywatna metoda. Definicja entry „s jest:

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; 
} 

Jak widać, jest odliczany od końca jeśli indeks jest większy od środkowego listy.