javaリストの拡張メカニズム

javaの`List`インタフェースのよく使われる実装クラスは2つあり、`ArrayList`と`LinkedList`と呼ばれています。

ArrayListは要素を格納するために内部で配列を使用しており、ArrayListの容量が足りなくなると自動的に拡張されます。ArrayListの拡張メカニズムは、現在の容量が不足すると、容量がより大きい新しい配列を作成し、元の配列内の要素を新しい配列にコピーすることです。デフォルトでは、拡張を行うたびに、新しい配列の容量は元の配列容量の1.5倍（つまり50％増）になります。

LinkedListは双方向の連結リストで、各ノードは前のノードと後ろのノードへの参照を持っています。エレメントを追加する時、LinkedListは拡張操作をする必要がありません。なぜなら、その格納構造は動的であり、ノードを必要に応じて柔軟に割り当てることができるからです。

要約すると、ArrayList は拡張メカニズムで動的成長を実現する一方、LinkedList は動的ノード割り当てで動的成長を実現する。