3

配列リストがリンクリストよりも高速である理由についての私の理解は、配列リストでは基本的に1つのアクションしか必要ないということです。つまり、配列要素の最後の参照を更新しますが、リンクリストでは、新しいノードを作成し、2を更新するなど、さらに多くのことを行う必要があります。参照、リンクされたリストを調べて、最後のノードを更新して新しいノードを指すようにします。

ただし、Javaがこれらをどのように実装するかはわかりません。配列リストはどのようにして「最後の」要素がどこにあるかを知るのですか?それは最後の要素の値を保存しますか?それとも配列を走査して最後の要素の後に新しい要素を追加しますか?

また、リンクされたリストは、リストの最後のノードへの参照を保存しますか?それとも、リスト全体をトラバースして最後に到達しますか?

4

3 に答える 3

2

ソースを見てください：

配列リスト:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

LinkedList :

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
于 2013-01-24T08:18:59.370 に答える
1

配列リストは、特定の操作でのみ高速です。配列の途中に要素を追加する場合、arraylist は基本的にすべてのデータを新しい配列にコピーする必要があります。arraylist が新しいデータ用のスペースを既に割り当てている場合にのみ、空のデータを挿入するときに高速になります (通常は最終的に)。インデックスによる読み取り/更新は非常に高速です。

LinkedList は、配列全体をコピーする必要がないため、挿入時に高速です。ただし、検索したい要素に到達するまですべての要素を「ウォーク」する必要があるため、リンクされたリスト内のデータへのアクセスは遅くなります。

于 2013-01-24T08:33:06.437 に答える
0

java.*クラスのソースはいつでも見ることができます。

ただし、特定の質問に答えると、クラスには、埋められた内部配列領域の現在のサイズを含むintフィールドがあります。ArrayListオブジェクトに新しい値を追加するArrayListと、このフィールドがインクリメントされ、内部配列のその要素に直接アドレス指定されます。

于 2013-01-24T08:18:34.563 に答える