配列
複数の要素（値）の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造（コレクションあるいはコンテナ）には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
配列は、複数の要素の集合で、メモリ上に連続した領域を確保して要素を格納して、それぞれの要素にインデックスを使ってアクセスします。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 | 9 | 21 | 35 |
配列はインデックスを使い、どの値にも\( O(1) \)でランダムアクセスできます。
言語により異なりますが、配列に含まれる要素は同じ型で、インデックスは0から始まることが多いです。
2次元の配列を作ることで行列のように扱うこともでき、また、3次元、4次元…の多次元配列を作ることができます。
要素の数によって自動的にサイズが拡張される仕組みを備えた動的配列（⇔静的配列）という配列もあります。
配列の利点
インデックスが分かれば、データを\(O (1) \) で取得できます（ランダムアクセスと呼ばれます）。
実装が簡単で直感的に使いやすいデータ構造です。
配列の欠点
静的配列の場合は事前に要素の個数が分かっていないと配列を生成することができません。
要素の挿入や削除に\( O (n) \)時間かかります。配列はメモリ上の連続領域を必要とするため、要素の挿入時に領域が不足すると拡張のためのメモリ再確保のコストが高くなってしまいます。
また、異なる型の要素を同一配列内に保持することができません。
配列の操作
add 新しい値の追加
配列に新しい値を追加します。
計算量は\( O (1) \) です。
配列がいっぱいになっていない限り、値を配列に追加することができます。
例えば、以下のような配列を生成します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 |
最初に、インデックス 0 に値 3 を追加します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 |
次に、インデックス 1 に値 0 を追加します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 |
… 最終的に以下のような配列になりました。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 | 9 |
このように、要素を配列の最後に追加していく場合、次のインデックスに値を挿入すれば良いので、\( O (1) \) で実行することができます。
insert 値の挿入
既に値の入ったインデックスへ値を挿入します。
計算量は\( O (N) \) です。
例えば、以下の配列でインデックス 1 へ値 5 を挿入します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 | 9 |
まずは、インデックス 1 のスペースを確保するため、現在の1以後の要素を全て一つずつ後方にシフトします。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 | 9 |
次に、空になったインデックス 1 のスペースに値 5 を挿入します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 5 | 0 | -10 | 2 | 9 |
このように、配列への値の挿入は空のスペースを作成するために要素のシフトが必要になるので、\( O (N) \) の計算量になります。
例えば、1000000個の配列の一番最初にデータを挿入する場合は、 1000000回の要素の移動が必要になります。
remove 値の削除
値の削除について考えます。
配列の一番最後の値を削除する場合は、値を追加する時と同じように、\( O(1) \) の計算量で行うことができ、配列の途中の値を削除する場合は、挿入と同様に要素のシフトが必要になり、\( O (N) \) の計算量になります。
まずは、配列の一番最後の値の削除を考えます。
例えば以下の配列からインデックス 5 の値を削除します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 5 | 0 | -10 | 2 | 9 |
インデックス 5 にアクセスして値を空にすれば、要素の削除が終わります。
計算量は\( O (1) \) です。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 5 | 0 | -10 | 2 |
配列の途中の値の削除を考えます。
以下の配列からインデックス 1 の値を削除します。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 5 | 0 | -10 | 2 |
まずはインデックス 1 を空にします。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 |
次にインデックス 2 以後の要素を全て左に一つずつシフトします。
| インデックス | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 要素 | 3 | 0 | -10 | 2 |
これで要素の削除が終了します。計算量は\( O (N) \) です。
