1. ホーム
  2. java

[解決済み] なぜArrayListは初期容量で始まるのですか?

2022-04-26 05:54:24

質問

の通常のコンストラクタは ArrayList

ArrayList<?> list = new ArrayList<>();

しかし、その初期容量のパラメータを持つオーバーロードされたコンストラクタも存在します。

ArrayList<?> list = new ArrayList<>(20);

を作成するとなぜ便利なのでしょうか? ArrayList というのも、最初の容量が決まっていれば、あとは好きなように追加できるからです。

解決方法は?

の大きさがあらかじめ分かっている場合は、その大きさに合わせたものを使用します。 ArrayList は、初期容量を指定した方が効率的です。そうしないと、リストが大きくなるにつれて、内部配列の再割り当てを繰り返さなければならなくなります。

最終的なリストが大きければ大きいほど、再割り当てを回避することで時間を節約することができます。

とはいえ、プリアロケーションがない場合でも、挿入された n の後ろにある ArrayList は合計で O(n) 時間です。言い換えれば、要素の追加は償却された定数時間操作である。これは、各再配置が配列のサイズを指数関数的に増加させることによって達成されます。 1.5 . このアプローチでは、総操作回数は であることを示すことができる。 O(n) .