動的配列

2025年10月22日

動的配列

英語表記: Dynamic Array

概要

動的配列は、データ構造（リスト, スタック, キュー, ツリー）という大きな分類の中で、「配列とリスト」の性質を理想的に融合させた「配列系データ構造」の一つです。これは、プログラムの実行中に格納される要素の数が増減しても、そのサイズを自動的に拡張したり縮小したりできる柔軟な配列のことです。あらかじめ最大容量を固定する必要がある静的配列とは異なり、動的配列はメモリを効率的に使いながら、配列が持つ高速なインデックスアクセス（ランダムアクセス）の特性を維持できる点が非常に魅力的です。これにより、プログラマはサイズ制限を気にすることなく、データを連続的に扱うことができるようになります。

詳細解説

動的配列が「配列とリスト」のカテゴリにおいて、現代のプログラミングで標準的に利用されるようになったのは、その優れた柔軟性とパフォーマンスのバランスのおかげです。静的配列は初期設定のサイズを超えるとエラーになるか、処理が停止してしまいますが、動的配列はその問題を内部処理によって完全に解消しています。

目的と内部構造

動的配列の主要な目的は、データの量が実行時に変動するアプリケーション（例えば、ユーザーが入力するデータ量や、ネットワークから受信するデータの量など）において、メモリの無駄を最小限に抑えつつ、配列の持つ O(1) の高速アクセス性能を最大限に活かすことです。

動的配列は、マジックのようにサイズが変わるわけではありません。その内部は、実は「静的配列」で構成されています。動的配列は、この内部の静的配列へのポインタと、現在の要素数、そして現在の配列の容量（キャパシティ）の三つを管理しています。

サイズ拡張（再配置）の動作原理

要素を追加していき、内部の静的配列が満杯（要素数＝容量）になったとき、動的配列は非常に重要な処理、すなわち「再配置（リサイズとコピー）」を実行します。このプロセスこそが、動的配列の動的な性質を支える心臓部です。

新しいメモリ領域の確保: システムに対し、現在の配列よりも大きな（通常は1.5倍や2倍など、一定の成長率に従った）連続したメモリ領域を確保するよう要求します。
要素のコピー: 現在の配列に格納されているすべてのデータを、新しい大きなメモリ領域に順番にコピーします。このステップは、データ量 N に比例した時間 O(N) がかかります。
ポインタの切り替え: 動的配列が指すアドレスを、古い配列から新しい配列の先頭アドレスに切り替えます。
古いメモリの解放: 役目を終えた古い配列のメモリ領域をシステムに返却します。

この一連の処理は、プログラマからは意識されず自動で行われるため、あたかも配列がシームレスに拡張されたかのように見えます。しかし、この O(N) のコピー処理がボトルネックになる可能性があるため、動的配列を扱う際は、このコストの存在を常に頭の片隅に置いておく必要があります。