データ構造の基礎：ADT（抽象データ型）としての配列表現とその特徴

ADT（抽象データ型）としての配列：基本概念

ADTは「Abstract Data Type（抽象データ型）」の略称です。

配列が抽象データ型として定義される理由は、同じ順序で連続した要素を保持できる点にあります。さらに、インデックス（添字）や位置を指定することで、特定の要素へ直接アクセスすることも可能です。

「抽象的」と表現されるのは、配列が特定のデータ型に縛られないためです。int型の数値でも、String型の文字列でも、独自に定義したPersonクラスのようなオブジェクトでも柔軟に扱えます。

int[] arrA = new int[1];
String[] arrB = new String[1];
Person[] arrC = new Person[3]; // Personは定義済みのクラスとして扱う

配列のメリット

• 高速なランダムアクセス： インデックスを指定すれば、どの位置の要素にも一定時間でアクセスできます。
• 高いメモリ効率： 格納するデータ自体に必要なメモリ以外は、ごくわずかな追加メモリしか消費しません。

配列のデメリット

• 挿入・削除が遅い： 途中の要素を追加・削除する際、後続の要素をすべてずらす必要があるため処理に時間がかかります。
• サイズが固定（静的）： 配列のサイズは作成時に決定し、その後変更できません。事前に必要な容量を見積もる必要があります。

ADTリストの配列による実装例

以下は、抽象データ型「リスト」を配列ベースで実装したJavaのコード例です。

public class ListArrayBased implements ListInterface {
    private static final int MAX_LIST1 = 50;
    private Object items1[];   // リスト項目を格納する配列
    private int numItems1;     // リスト内の項目数

    public ListArrayBased() {
        items1 = new Object[MAX_LIST1];
        numItems1 = 0;
    } // end default constructor
}

この実装では、最大50個の要素を格納できるObject型の配列を用意し、コンストラクタで初期化しています。フィールドnumItems1が現在のリスト内の項目数を管理しており、これによりリストの状態を常に把握できます。