1

List インターフェイスのコレクション フレームワークのチュートリアルには、List 実装からの要素の削除のパフォーマンスに関する興味深い引用があります。

ArrayList などの多くの一般的な List 実装では、リストの末尾から要素を削除するパフォーマンスは、最初から要素を削除するパフォーマンスよりも大幅に優れています。

チュートリアルでは、これ以上の説明はありません。なぜそうなのかを正確に理解しようとしています。

ArrayList<Integer> list以下のように考える：

リスト

最初のシナリオでは、 の末尾から最後の 4 つの要素を削除すると、listこれらの値はnull(または同等の) に設定されます。私の理論では、コピー操作が必要な場合、そうでない要素のみnullがコピーされるというものです。

2 番目のシナリオでは、最初の 4 つの要素を削除すると、それらはnull何度も に設定され、非null要素のみがコピーされます。

この観点から見ると、パフォーマンスはほぼ同じように見えます。最後から実行すると操作が速くなる別の理由はありますか?

一方、 についてLinkedListは、逆が成り立つように見えます。最初から削除する方が高速ですが、最後から削除するには、 atail-pointer が保持されていない限り、ほぼ完全なトラバーサルが必要です。

4

4 に答える 4

6

私の理解によると、ArrayList はリストの配列実装です。したがって、配列の先頭から要素を削除する場合は、残りのすべての要素を移動して、削除した要素を埋める必要があります。したがって、これは基本的に O(n-1) 操作になります。ただし、リストの末尾から要素を削除する場合はそうではありません。これは O(1) になります。

于 2013-03-12T02:10:50.737 に答える
2

リストの先頭から要素を削除するには、単に要素を に設定するだけではありませんnull。また、空いた場所を埋めるために残りの要素を移動する必要があります。

変数を使用して、要素を移動せずにリストの「先頭」を追跡することは可能ですが、配列内の未使用の要素のためにメモリ効率が犠牲になります。

于 2013-03-12T02:11:24.730 に答える
0

ArrayList<>開始からの削除は遅くなります。これは、要素の追加機能以降、配列全体をシフトする必要があり、add開始を空のままにしておくと、メモリが無駄になるためです。

大きな表記を考慮(O)すると、開始からの削除は基本的に線形時間O(n)ですが、終了からの削除は一定時間O(1)です。

于 2013-03-12T02:13:44.603 に答える