42

JavaListなどで X 要素の範囲 (末尾など) を削除する効率的な方法はありますか?LinkedList

最後の要素を 1 つずつ削除することは明らかに可能であり、これにより O(X) レベルのパフォーマンスが得られるはずです。少なくともLinkedListインスタンスでは、O(1) パフォーマンスを実現できるはずです (削除する最初の要素の周囲に参照を設定し、ヘッド/テール参照を設定することにより)。残念ながら、最後の要素を一度に削除したり削除しListたりする方法はありません。LinkedList

現在、リストを使用して置き換えるList.subList()ことを考えていますが、同等のパフォーマンスがあるかどうかはわかりません。少なくともコード内ではより明確になりますが、提供される追加機能は失われLinkedListます。

私は主にリストをスタックとして使用していますLinkedList。少なくともセマンティクスに関しては、これが最良の選択肢のようです。

4

2 に答える 2

78

subList(list.size() - N, list.size()).clear()N最後の要素を削除するための推奨される方法です。実際、Javadoc forsubList はこのイディオムを具体的に推奨しています。

このメソッドにより、明示的な範囲操作 (配列に一般的に存在する種類の操作) が不要になります。リスト全体の代わりに subList ビューを渡すことにより、リストを必要とする操作を範囲操作として使用できます。たとえば、次のイディオムは、リストから要素の範囲を削除します。

 list.subList(from, to).clear();

実際、このイディオムは呼び出し時間よりも効率的である可能性があると思います(一定の係数ではありますが) 。最後から 1 番目のノードがremoveLast() N見つかったら、リンクされたリスト内の一定数のポインターを更新するだけで済みます。最後のノードNのそれぞれのポインターを一度に 1 つずつ更新するのではなく、N

于 2012-05-29T11:22:28.760 に答える
15

元のリストのビューsubList()を返すことに注意してください。つまり、次のことを意味します。

  1. ビューに加えられた変更は元のリストに反映されます
  2. 返されたリストはそうではありません- それはシリアライズ可能ではないのLinkedList内部実装ですList

いずれにしても、Java でリンクされたリストの最初または最後の要素をポップすることは操作であるため、またはのいずれremoveFirst()かを使用するremoveLast()ことは十分に効率的である必要があります。 .O(1)LinkedList

m要素を一度に削除する場合、 をO(m)使用するとパフォーマンスが低下しますが、奇妙LinkedListなArrayListことに、より良いオプションになる可能性があります。ArrayListの場合のように、ガベージ ノードがぶら下がったままになることはありませんLinkedList。最良の選択？両方のアプローチを試し、それらをプロファイリングし、数字がそれ自体を物語るようにします.

于 2012-05-29T11:14:23.743 に答える