Java ListIteratorパフォーマンス

ここでは、Java ArrayListとLinkedListのパフォーマンスについてthreadを読んでいました。 Mr Kevin Brockから次のような回答があります。Java ListIteratorパフォーマンス

「リンクリストの追加は常にO（1）ない[または、これは（addLastを言うべき） O（1）である]。反復子内から行う場合、これが唯一の真実である。アドオンJavaのLinkList実装のメソッドは、が先頭または末尾にない場合は、リストを検索する必要があります。

「ListIteratorを使用した場合にのみ」という意味を理解していません。リンクされたリスト内に各索引の参照を保持するデータ構造が存在し、特定の索引からlistiteratorを取得すると直ちにlistiteratorがその索引を検索することなく直ちに戻されますか？

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

2010-12-12 Abidi

これは、イテレータがノードを直接一覧表示することを意味します。 get（int）を介したアクセスはO（N）になりますが、iterator.next（）はO（1）になります。 Latterは直接参照を持ち、何もトラバースする必要はありません。前者はリストの先頭から移動する必要があります。

2010-12-12 19:00:37 StaxMan

迅速な回答Staxmanに感謝します。それで、ListIteratorはノードの参照を保持するために "linkedlist"と並行して維持されるものですか？ – Abidi

@Abidi、ありがとうございます。しかし、私はあなたがやっていることが、より効率的に別の方法でやることができると思っています。通常は、実行する必要があることを実行する別の方法がありますので、ランダムな場所にリストを挿入する必要はありません。 –

@Peter、あなたの答えをありがとう。 – Abidi

ListIteratorが指しているLinkedListに追加すると、O（1）になります。これは、LinkedListの先頭またはArrayListの末尾に追加するのと同じです。

2010-12-12 19:01:09

このコメントは、2つの引数addメソッド[add(int,E)] [1]を参照しています。線形に分布したインデックスを仮定すると、適切なノードを見つけるためにリストを反復する必要があるので、これはO（n）になります。 add(E)には該当しません。

[1]：、E）

2010-12-12 21:19:42

答えて