配列
逆に決まった要素数しか格納できない配列を、静的配列 (static array) あるいは固定長配列 (fixed length array) と呼ぶ。
なおC言語では、下記のように、実行時に(整数定数式ではない)要素数を指定してスタック上に自動変数として確保することのできる静的配列を可変長配列 (variable-length array) と呼んでいる。GCCに拡張として実装されていたが、C99以降で標準化された。この可変長配列は後から要素を追加したりすることはできない。
動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある(そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある)。最悪ではなく償却計算量でNにならなければ良い、という考え方もある。
ただし矩形配列は全要素が収まる連続領域を確保しなければならず、疎行列などのまばらな配列には空間的オーバーヘッドが大きくなってしまうことから向いていない。また、.NET Frameworkの中間言語には1次元配列の要素アクセスに関する専用命令が存在するため、矩形配列よりもジャグ配列のほうが速度性能面で有利になるケースも存在する。
C言語では、配列を指すポインタは、その配列のサイズを固定しなければならない。配列を指すポインタではなく、「『配列の先頭要素を指すポインタ』の配列」によって、次のようにしてジャグ配列のようなデータ構造を作ることができる。
例示したように、「配列の配列」と同様の構文でアクセスできるが、データ構造としては異なっている。当然、(生成されるコードを読めばわかるが)意味的に違うものであって、混同してはならない。ましてや「多次元配列がサポートされていると考えるべき」などと考えるのは、混乱の元でしかない。
要素数によって自動的にサイズが拡張される配列を、動的配列 (dynamic array) あるいは可変長配列 (variable-length array) と呼ぶ。メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。ライブラリで提供されるもの(C++のstd::vector、Javaのjava.util.ArrayList、.NETのSystem.Collections.ArrayListやSystem.Collections.Generic.Listなど)と、言語に組み込まれているもの(PerlやDなど)がある。またPerlなど、言語によっては、最初に配列を生成する際に指定されたサイズからはみ出してアクセス(範囲外アクセス)しても、自動的に拡大されるような配列を持っているものもある。
「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、Ο(1) でアクセスできる具象あるいは実装を特に指す場合がある(その意味では、次節の連想配列などは「配列」ではない、ということになる)。
配列に要素を挿入/削除する際、要素間に「隙間」が無いようにするには、線形リストと異なり、挿入/削除位置から後ろの領域にあるすべてのデータの移動(コピー)が必要となる。そのため、挿入/削除にO(n)時間かかる。さらに配列は連続領域を必要とするため、挿入時に領域が不足した場合に拡張する際のメモリ再確保のコストが高い。
探索は一般的には線型探索になるためΟ(n)だが、データがソート済みであれば二分探索を使うことでΟ(log n)に軽減することもできる(抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。en:Sorted array を参照)。
添え字は一般に通例0か1始まりの (非負) 整数である。一方、文字列など他のデータ型を添え字のように使用できる配列を連想配列という。
複数の要素(値)の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造(コレクションあるいはコンテナ)には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。
ここでは例示にC言語 (C99) を使う。
例えば、6人の生徒の平均点を計算するプログラムを書くとする。配列を使わない方法では、それぞれの生徒に対応する変数を、次のように個別に用意することだろう。
しかし、この方法では生徒数が増減したときに、変更や拡張が大変になってしまう。より良い解は6要素の配列を使うことである。
配列を用いることで、添え字演算子による統一的なアクセスおよび一括処理が可能となる。また、処理すべきデータ個数が増減したときにも対応しやすくなる。