動的配列

動的配列は、実行中に論理的な要素数を増減できる配列です。一般的な実装は要素数である長さと、確保済み領域の要素数である容量を分け、容量不足時により大きな連続領域へ再確保して要素を移します。

■ 試験で押さえるポイント

• 容量に空きがある末尾追加は通常$O(1)$です。満杯時は新領域の確保と全要素コピーが必要なので、その一回は$O(n)$になります。

• 容量を一定要素ずつでなく2倍など幾何級数的に増やすと、n回の末尾追加に必要な総コピー回数は$O(n)$となり、一回当たりの償却計算量は$O(1)$です。

• 添字アクセスは静的配列と同様に通常$O(1)$ですが、途中への挿入・削除は要素移動のため$O(n)$です。ノードをリンクする連結リストとは構造も特性も異なります。

• 長さを減らしても容量を直ちに縮小しない実装があり、頻繁な再確保を防ぎます。拡張時には一時的に旧領域と新領域の両方が必要になる点も容量見積りに関係します。

■ 選択肢での判断ポイント

容量不足時の再確保は最悪$O(n)$、通常の末尾追加は償却$O(1)$と区別します。全ての追加が$O(1)$という断定や、途中挿入まで高速という説明は誤りです。

例: 容量4の配列[10,20,30,40]へ50を追加し、容量を8へ拡張するなら、8要素分を確保して4要素をコピー後、50を格納します。この追加はコピー4回を伴いますが、次の3回は再確保なしで追加できます。