1. ホーム

[解決済み】なぜArrayDequeはLinkedListより優れているのか?

2022-04-10 05:56:18

質問

を理解しようとしています。 なぜJavaのArrayDequeは、JavaのLinkedListよりも優れているのか? どちらも Deque インターフェースを実装しているためです。

ArrayDequeを使っている人をほとんど見かけません。もし誰かがArrayDequeがどのように実装されているのか、もっと光を当ててくれると助かります。

理解できれば、自信を持って使えると思います。JDKの実装では、先頭と末尾の参照をどのように管理するのかがよくわからなかった。

どのように解決するのですか?

リンク構造体は、各要素のキャッシュミスを伴う反復処理を行うには、おそらく最悪の構造体です。そのうえ、より多くのメモリを消費します。

両端の追加/削除が必要な場合は、リンクリストよりもArrayDequeの方が圧倒的に優れています。各要素のランダムアクセスも巡回型キューではO(1)です。

リンクリストの唯一の優れた操作は、反復中に現在の要素を削除することです。