配列（はいれつ、Array）は、プログラミングにおけるデータ構造の一つ。科学技術計算分野ではベクトルという場合もある。また、リストも参照。配列はデータの集合であり、添え字で個々の要素を区別するものを指す。古典的なプログラミング言語では同じデータ型の集合に限定されるが、比較的新しい言語や多くの高水準言語では異なった型も格納することができる。例えばJavaScriptでは一般的なオブジェクトも一種の連想配列である。通常、変数には1つの値しか格納できない。しかし、ときには、ある関係を持つ複数の値を格納できる変数があると都合の良いことがある。その場合に用いられるのが配列である。例えば、6人の生徒の平均点を計算するプログラムを書くとする。それぞれの生徒の点数を格納する変数は、愚直に考えれば、次のC言語で書かれた例のように個別に宣言することになるだろう。より良い解は6要素の配列変数を宣言することである。このようにすると、Cではscore[0]からscore[5]までの6つの要素を持った配列変数が作られる。配列内のデータへのアクセスはO(1)時間でできるが、線形リストと異なり、挿入・削除にはO(n)時間かかる。探索は一般的には線型探索になるためO(n)時間かかるが、データがソート済みであれば二分探索を使うことでO(log n)に短縮することもできる。配列内のあるデータにアクセスする際は、添え字でどのデータにアクセスするか指定する。古典的な言語では添え字は非負整数であり、配列の最初の要素を指定する番号は通例0または1である（始まりの番号を指定できる言語もある）。一方、文字列など他のデータ型を添え字に使用できる配列を連想配列という。要素数によって自動的にサイズが拡張する配列（dynamic array）。要素の末尾追加や途中挿入が自由であり、可変長配列（variable length array）とも言われる。ライブラリで提供されるもの（C++のstd::vector、Javaのjava.util.ArrayList、.NETのSystem.Collections.ArrayListやSystem.Collections.Generic.Listなど）と言語に組み込まれているもの（PerlやDなど）がある。逆に決まった要素数しか格納できない配列を静的配列（static array）あるいは固定長配列（fixed length array）と言う。多くの言語では、実行時あるいはコンパイル時に指定された要素数をもとに、静的配列をヒープ上に動的に生成すること（動的メモリ確保）も可能ではあるが、こちらはあとから要素数を変更できないなど、前述の動的配列とは仕様や意味合いが異なる。C言語では、実行時に要素数を指定してスタック上に確保することのできる静的配列を可変長配列と称している。配列は、1次元だけではなく2次元・3次元などの多次元配列もつくることができる。codice_1、codice_2などの方式で添字を指定する。C言語やJavaでは多次元配列がサポートされていないと誤解されることが多いが、CやJavaで多次元配列を定義したとき（配列の中に配列を定義したとき）には、C言語は行×列の要素のメモリが連続的に確保されJavaはヒープ領域にオブジェクトとして複数の異なる配列を一つの配列の要素が参照する形をとるので、サポートされていると考えるべきである。この際、要素へのアクセスはcodice_1のように「配列の配列」として記述する。ただし「配列の配列」は言語によっては「ジャグ配列 (jagged arrays)」として理解され、「多次元配列」という言葉とは明確に区別される場合がある。さらに、Cでは用途に応じて「配列へのポインタの配列」を用意するなどして、擬似的に多次元配列を実現することもある。この場合も、codice_1のように要素にアクセスするが、codice_5の結果の比較からも分かるように、両者の内部構造はまったく異なる。以下の図はこのようにして擬似的に実現した多次元配列の例である。ジャグ配列は、不規則配列とも言われ、多次元配列の一種であり、同一次元内での要素数が揃っていないことがあり得るものを言う。これに対して通常の多次元配列を指す場合、矩形配列などと言う。特にC#では通常の配列と区別する表記を言語が直接用意している。イメージ的にはより「配列の配列」に近い。

出典:wikipedia