データ構造：単一の配列で複数のリストを実現する方法

配列表現におけるメモリの無駄の問題

データ構造における配列による表現は、時間とともに変化するデータを格納する場合、基本的にメモリ領域を無駄にしてしまう傾向があります。あるデータを格納するためには、複数の値を余裕をもって格納できるサイズの配列を事前に確保しておく必要があり、多くの場合、配列の拡張には「配列倍増（アレイ・ダブリング）」という手法が用いられます。

配列倍増の仕組みとその課題

具体的な例で考えてみましょう。現在の配列サイズが8192であり、すでに満杯になっているとします。この場合、配列倍増の手法によってサイズを拡張する必要があり、新しい配列のサイズは16384になります。その後、旧配列から8192個の要素を新配列へコピーし、コピー完了後に旧配列の領域を解放します。

ここで注目すべきは、旧配列を解放する前の一時的な時点において、確保されているメモリの合計が8192の3倍に達するという点です。倍のサイズを持つ新配列と、まだ解放されていない旧配列が同時に存在するためです。このように、配列倍増はシンプルな手法である反面、一瞬的に大量のメモリを消費するという欠点があります。

1つの大きな配列を複数のリストで共有する

こうした無駄を減らす方法のひとつが、複数のリストを格納したい場合に、リストごとに個別の配列を作成するのではなく、より大きな1つの配列を共有するという考え方です。単一の配列内に複数のリストを格納した場合の構造は、以下の図のようなイメージになります。

共有配列方式のメリットとデメリット

この方式は、配列領域を有効活用できるためメモリ効率に優れています。しかし一方で、次のような問題点も抱えています。

• 挿入操作のコストが高い：現在扱っているリストに要素を挿入する際、他のリストに属する要素をずらして移動させる必要が生じる場合があります。その結果、挿入処理の負荷が大きくなります。
• 実装が複雑になる：各リストの先頭位置や長さといった情報を適切に管理しなければならないため、通常の配列表現に比べて実装難度が高くなります。

このように、単一配列による複数リストの管理はメモリ効率の面で優れた手法ですが、挿入コストや実装の複雑さとのトレードオフがあることを理解した上で、用途に応じて使い分けることが重要です。