配列
出典: フリー百科事典『ウィキペディア（Wikipedia）』
配列（はいれつ、Array）は、プログラミングにおける、データ構造の一つ。科学技術計算分野ではベクトルという場合もある。
配列はデータの集合であり、添え字でインデックスされたものを指す。古典的なプログラミング言語では、同じデータ型の集合に限定されるが、比較的新しい言語や多くの高水準言語では異なった型も許す。JavaScriptでは一般的なオブジェクトも一種の配列である。プログラミング上多用されるので、それ自体配列型として導入される場合が多い。
目次 |
[編集] 概要
配列内のあるデータにアクセスする際は、添字でどのデータにアクセスするか指定する。古典的言語では、添字はスカラー数値であり、配列の先頭（0または1、または、始まりを指定できる言語もある）からの番号で指定する。文字列など他のデータ型を、添字に使用できる配列を連想配列という。
配列内のデータへのアクセスはO(1)時間でできるが、線形リストと異なり、挿入・削除にはO(n)時間かかる。探索は一般的には線型探索になるため O(n) 時間かかるが、データがソート済みであれば二分探索を使うことで O(log n) に短縮することもできる。
配列は、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)の結果の比較からも分かるように、両者の内部構造はまったく異なる。以下の図はこのようにして擬似的に実現した多次元配列の例である。
[編集] 配列のバリエーション
[編集] 動的配列
要素数が実行時に決定する配列。可変長配列とも言われる。逆にソースコード上で要素数を決定する配列を静的配列と言う。静的配列と動的配列とで構文上区別するもの（C++,JavaのArrayList,Vectorなど）とそうでないもの（C#など）などとがある。
動的配列はただの動的に確保された配列とは異なる。動的配列における挿入はならし時間で O(1) かかる。
[編集] ジャグ配列
多次元配列の一種であり、同一次元内での要素数が揃っていないものを言う。これに対して通常の多次元配列を指す場合、長方形配列などと言う。特にC#では通常の配列と区別する表記を言語が直接用意している。イメージ的にはより「配列の配列」に近い。
| ● | ● | ● | ● | ● | ||||||
| ● | ● | ● | ● | |||||||
| ● | ● | ● | ● | ● | ● | ● | ● | ● | ● | ● |
| ● | ● | ● | ● | ● | ● |
- 縦軸を1次元目、横軸を2次元目とし、●を配列に格納されている要素とする。
