Java'nın LinkedList, gerektiğinde geri (dizin) almak için optimize edilmiş mi?

Question

LinkedList'leri optimize etmenin bazı yolları üzerinde çalışıyorum. Java varsayılan çift bağlantılı LinkedList sınıfının tersine get() işlemlerini yapmak için optimize edilmiş olup olmadığını bilen var mı? Örneğin :

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

list.get(half + 1) çağrı arama optimize etmek ve onu doubly bağlı liste olduğundan tersten gitmek istiyorsunuz? Sonundan arama yapmak ve öğenin listenin ikinci yarısında olduğunu biliyorsanız merkeze doğru gitmek daha mantıklı olacaktır.

get(index)'un O(n) saatini kullandığını biliyorum ve bir LinkedList'i kullanırken bir yineleyici kullanmalısınız, ancak sadece merak ediyorum.

Answer 1

Evet öyle. Kaynak kodu kendiniz inceleyebilirsiniz:

LinkedList#get(int)http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29entry özel bir yöntemdir sadece

return entry(index).element; 

olarak uygulanmaktadır. entry 'ın tanımı şöyledir: endeksi listesinin orta büyükse Gördüğünüz gibi

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

, bu ucundan aşağı sayar.