5

私は、LinkedList を最適化するいくつかの方法に取り組んできました。get()Javaのデフォルトの二重リンクされたLinkedListクラスが逆の操作を行うように最適化されているかどうかは誰にもわかりませんか? 例えば：

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

list.get(half + 1)二重にリンクされたリストであるため、検索を最適化して逆に呼び出す呼び出しはありますか? 要素がリストの後半にあることがわかっている場合は、最後から検索して中央に向かって検索する方が理にかなっています。

get(index)使用するのはO(n)時間であり、LinkedList をトラバースするときにイテレータを使用する必要があることは知っていますが、ちょっと興味があります。

4

1 に答える 1

5

はい、そうです。ソースコードを自分で調べることができます: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int% 29

LinkedList#get(int)として実装されています

return entry(index).element;

はentryプライベート メソッドです。entryの定義は次のとおりです。

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

ご覧のとおり、インデックスがリストの中間点よりも大きい場合、最後からカウントダウンします。

于 2013-10-03T06:02:23.543 に答える