配列 (Array)

**配列 (Array)**は、同じ種類の要素をインデックスで識別する線形データ構造である。

仕組み

要素幅w、先頭アドレスbならi番目の位置はb+i×wで計算できる。連続配置によりランダムアクセスを実現する。

計算量・性質

アクセスはO(1)、未整列検索はO(n)、途中の挿入・削除は後続要素の移動が必要でO(n)。

具体例

整数列[4,7,9]では添字1から7を直接取得できる。

限界と注意点

境界外アクセス、固定長と動的配列の混同、再確保時の参照無効化に注意する。