配列

配列（はいれつ、Array）は、プログラミングにおけるデータ構造の一つ。科学技術計算分野ではベクトルという場合もある。また、リストも参照。

配列はデータの集合であり、添え字で個々の要素を区別するものを指す。古典的なプログラミング言語では同じデータ型の集合に限定されるが、比較的新しい言語や多くの高水準言語では異なった型も格納することができる。例えばJavaScriptでは一般的なオブジェクトも一種の連想配列である。

配列とは

通常、変数には1つの値しか格納できない。しかし、ときには、ある関係を持つ複数の値を格納できる変数があると都合の良いことがある。その場合に用いられるのが配列である。例えば、6人の生徒の平均点を計算するプログラムを書くとする。それぞれの生徒の点数を格納する変数は、愚直に考えれば、次のC言語で書かれた例のように個別に宣言することになるだろう。

int score1;
int score2;
int score3;
...

より良い解は6要素の配列変数を宣言することである。

int score[6];

このようにすると、Cではscore[0]からscore[5]までの6つの要素を持った配列変数が作られる。

計算オーダー

配列内のデータへのアクセスはO(1)時間でできるが、線形リストと異なり、挿入・削除にはO(n)時間かかる。探索は一般的には線型探索になるためO(n)時間かかるが、データがソート済みであれば二分探索を使うことでO(log n)に短縮することもできる。

さまざまな配列

連想配列

テンプレート:See also 配列内のあるデータにアクセスする際は、添え字でどのデータにアクセスするか指定する。古典的な言語では添え字は非負整数であり、配列の最初の要素を指定する番号は通例0または1である（始まりの番号を指定できる言語もある）。一方、文字列など他のデータ型を添え字に使用できる配列を連想配列という。

動的配列

要素数によって自動的にサイズが拡張する配列。可変長配列とも言われる。逆に決まった要素数しか格納できない配列を静的配列と言う。ライブラリで提供されるもの（C++、Java、.NETなど）と言語に組み込まれているもの（PerlやDなど）がある。

動的配列はただの動的に確保された配列とは異なる。

多次元配列

配列は、1次元だけではなく2次元・3次元などの多次元配列もつくることができる。a[i][j]、a[i, j]などの方式で添字を指定する。

C言語やJavaでは多次元配列がサポートされていないと誤解されることが多いが、CやJavaで多次元配列を定義したとき（配列の中に配列を定義したとき）には、C言語は行×列の要素のメモリが連続的に確保されJavaはヒープ領域にオブジェクトとして複数の異なる配列を一つの配列の要素が参照する形をとるので、サポートされていると考えるべきである。

この際、要素へのアクセスはa[i][j]のように「配列の配列」として記述する。ただし「配列の配列」は言語によっては「ジャグ配列 (jagged arrays)」として理解され、「多次元配列」という言葉とは明確に区別される場合がある。

さらに、Cでは用途に応じて「配列へのポインタの配列」を用意するなどして、擬似的に多次元配列を実現することもある。この場合も、a[i][j]のように要素にアクセスするが、sizeof (a)の結果の比較からも分かるように、両者の内部構造はまったく異なる。以下の図はこのようにして擬似的に実現した多次元配列の例である。

ファイル:2D array.png

ジャグ配列

ジャグ配列は、不規則配列とも言われ、多次元配列の一種であり、同一次元内での要素数が揃っていないことがあり得るものを言う。これに対して通常の多次元配列を指す場合、矩形配列などと言う。特にC#では通常の配列と区別する表記を言語が直接用意している。イメージ的にはより「配列の配列」に近い。

ジャグ配列のイメージ

● ● ● ● ●

● ● ● ●

● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ●

縦軸を1次元目、横軸を2次元目とし、●を配列に格納されている要素とする。