-1

誰かが理由をはっきりと教えてもらえますか?

読み取りは ArrayList では簡単です (配列インデックスを介してアクセスできます)。

arrayList に要素を挿入するのは難しい理由を聞いたことがありますか? linkedList で簡単に

arraylist の要素を削除するのが難しいのはなぜですか? linkedList で簡単に

配列についてはある程度知っていますが、linkedXXX ではど​​うなるでしょうか

ありがとうございました。

4

2 に答える 2

3

ArrayList では、メモリ内に参照の配列を保持します。つまり、メモリ位置があります。ArrayList の最初の要素を要求すると、メモリ位置にアクセスするだけです。10 番目の要素にアクセスすると、メモリ位置 + 参照のサイズの 10 倍にアクセスします。

LinkedList には、次の要素への参照を持つ1 つの要素があります。次のものは次のものを参照します。ご覧のとおり、次の要素を 1 つずつ取得することなく、LinkedList の 10 番目の要素に直接アクセスする方法はありません。

それで、あなたの質問：

arrayList に要素を挿入するのは、なぜですか? linkedList で簡単に

要素を ArrayList に挿入する際には、次の 2 つの問題があります。

  1. 要素を位置 3 に配置するときは、最初に位置 3 から始まるすべての要素を移動し、一度右にシフトする必要があります (3 が 4 になる、4 が 5 になるなど...)。新しい要素

  2. ArrayList をサポートする配列が既にいっぱいになっている場合は、新しい配列を作成する必要があります。メモリを再度割り当ててから、すべての要素を新しい配列にコピーし、古い配列を破棄する必要があるため、これは非常にコストがかかります。

一方、Linkedlist では、2 を指す要素 1 に移動し、次に 2 に移動します。2 には、古い要素 3 への参照があり、一時的に別の場所に保存します。それを新しい要素への参照に置き換え、新しい要素で古い 3 への次のポイントを作成します。したがって、これははるかにコストがかかりません。

arraylist の要素を削除するのはなぜ? linkedList で簡単に

挿入と同様の理由。ArrayList では、すべての要素を再び下にシフトする必要があります。LinkedList では、要素 2 に到達したら、次のポイントを 4 にすると、ほら、3 が消去されます。

完全 を期すために、要素にランダムな順序でアクセスする場合は ArrayList が最適ですが、加算と減算の問題があります。LinkedLists は追加と削除に優れていますが、最初でも最後でもない要素を取得するには追加のコストがかかります。したがって、常にトレードオフがあります。

于 2012-06-11T08:09:44.527 に答える
2

ArrayList は配列によって支えられており、配列は拡大または縮小できず、要素を挿入または削除することもできません。したがって、新しい配列を作成し、既存の値をある配列から別の配列にコピーする必要があるため、挿入と削除はコストのかかる操作です。ただし、配列はインデックスでアクセスできるため、ここではランダム アクセスの方がはるかに高速です。

LinkedList は、一方向または双方向で相互へのポインター (はい、知っています) を持つノード オブジェクトで構成されます。これらのノードの 1 つを削除したり、新しいノードを挿入したりするのは非常に安価ですが、ノード番号を取得する必要があります。12345、最初から開始して 12344 ノードを歩く必要があります。つまり、ここではランダム アクセスが非常に高価です。注: Java LinkedList はリストであるだけでなく、インターフェースQueueとDequeインターフェースも実装しています。

どちらも単純な反復には同じように適していると思いますが、根底にあるメカニズムはまったく異なります。

于 2012-06-11T08:11:02.333 に答える