動的配列

動的配列は連続メモリに要素を保存し、実要素数 size と収容数 capacity を分けます。添字アクセスは address + index × element_size で位置を求めるため、読み書きは O(1)。連続配置の費用は挿入、削除、拡張に現れます。

右側に空きを残した番号付きの箱の列と考えてください。追加は最初の空きを使います。満杯なら倍の列を確保し、全値を移して旧配列を解放します。まれな高費用の拡張が、多くの安い追加を支えます。

動的配列の仕組み

基底配列は capacity 個の位置を持ち、先頭 size 個が有効、残りは予備です。この実装は削除時に縮小しません。

• 添字アクセス：get、set は隣をたどらず位置を計算します。添字 0 と 9,000 も同じ種類の計算です。
• 追加：size == capacity を検査し、空きがあれば添字 size に書いて size を増やします。
• 拡張：満杯なら 2 × capacity を確保し、size 個を順番にコピーし、旧配列を解放してから追加します。一回のコピーは O(n) ですが、幾何的成長では多数の追加の合計が線形で、一回当たり償却 O(1) です。
• シフト：位置 i への挿入は size − i 個を右へ、削除は後ろの size − i − 1 個を左へ移します。最悪 O(n)、先頭が最も高く、末尾は移動不要です。

挿入は右から左へコピーします。最後を空きへ移してから戻れば、未移動の値を上書きしません。削除は左から右へ隙間を埋めます。

操作をステップで追う

既定は空、capacity = 4 で九操作です。

1. append(5)：添字 0 に書き、size = 1。
2. append(8)：添字 1、size = 2。
3. append(2)：添字 2、size = 3。
4. append(9)：添字 3、size == capacity == 4 で満杯。
5. append(4)：容量 8 を確保し、5、8、2、9 を順にコピー。旧配列を解放後、添字 4 に 4 を書く。[5, 8, 2, 9, 4]、size = 5、capacity = 8。この追加には四回のコピーがある。
6. get(2)：走査せず添字 2 から 2 を読む。
7. set(2, 6)：直接書き換え、[5, 8, 6, 9, 4]。
8. insert(1, 7)：後ろから 4 を添字 5、9 を 4、6 を 3、8 を 2 へ移し、1 に 7 を書く。[5, 7, 8, 6, 9, 4]、size = 6。一挿入で四要素を移動。
9. remove(3)：6 を外し、9 を 4 から 3、4 を 5 から 4 へ移す。size = 5、結果は [5, 7, 8, 9, 4]。末尾の使用位置が予備へ戻る。

最後は容量 8 に五要素、空き三つです。画面右の破線の箱が空き容量、実線の箱の括弧が size を示します。

時間・空間計算量

保存空間は O(capacity)。追加だけの倍増では要素数に対して O(n) で、拡張直後は約半分が空きます。この実装は縮小しないため、大量削除後の確保量は過去の最大容量に依存し、現在の size だけでは見積もれません。

ここでは二倍に拡張します。1 より大きい一定比率なら償却 O(1) の追加を保てます。実装例では Java ArrayList が約 1.5 倍、C++ std::vector がよく 1.5–2 倍、CPython list が約 1.125 倍です。実装・版によって変わる方針で、インターフェースの保証ではありません。

境界ケース

• 末尾の挿入・削除：insert(size, v) は追加と同じでシフト不要。ただし満杯なら拡張する。remove(size − 1) は size を減らすだけで O(1)。
• 先頭の挿入・削除：insert(0, v) は元の全要素、remove(0) は残る全要素を動かす。最悪の場合で、連結リストの先頭挿入は O(1)。
• 範囲外：get、set、remove は 0 ≤ i < size、insert は 0 ≤ i ≤ size。外れると IndexError となる。入力パネルはそうした添字のボタンを無効にするので、アニメーションでは実行されない。
• 空：get、set、remove に有効添字はない。insert(0, v) は有効。
• 表示上限：容量 16 で倍増を止める。実際の構造はこの固定上限を持たず、メモリや実装の制約に従う。

よくある間違い

• 毎回の追加を O(1) とする。 拡張する回は全要素をコピーします。O(1) は複数操作の償却費用です。
• シフトを逆向きにする。 挿入を低い添字から始めると、未移動の値を上書きし、同じ値を後ろへ広げます。挿入は高い方から、削除は穴から後ろへ進みます。
• 削除後に穴を残す。 有効領域は連続します。i を null にするだけではなく、後続を詰めます。
• size と capacity の混同。 空きスロットがあっても、有効添字は size − 1 までです。
• 操作の割合を無視する。 添字アクセスと連続走査は得意ですが、先頭の挿入・削除は高費用です。主要な操作に合わせて配列かリストを選びます。