配列

もどる トップにもどる

概要

配列とは、同じ型のデータを連続して格納するためのデータ構造です。

• メリット
  • 要素のランダムアクセスが O(1) で可能。
  • メモリを連続で確保するので、キャッシュ効率が良い。
  • データサイズが固定なので、メモリ管理が簡単。
• デメリット
  • サイズが固定なので、要素数の変更が難しい。
  • 要素の挿入や削除に O(n-i) 必要

では、なぜ配列のランダムアクセスは O(1) で可能なのでしょうか。

それは配列の仕組みを考えると、単純な話で、下の図のようにメモリ上に連続して確保しているからです。

例えば、int型(=4bytes) の配列 A を作ったとき、先頭(=A[0])がメモリ上の 0x0000 に存在するとき、A[i]のメモリ上の位置は 0x0000 + i*4 となり、これは O(1) で計算が可能です。

では、int型(=4bytes)ではなく、char型(=1byte)の配列 B を作り、先頭(=B[0])がメモリ上の 0x0000 に存在するとき、B[i]のメモリ上の位置は 0x0000 + i*1 となるのでしょうか。

答えは Yes です。

どの型であっても、i番目の要素のメモリ上の位置は、(先頭アドレス) + i*(型のサイズ) で計算できます。 なお、型のサイズを知りたいときは、sizeof演算子を使うといいです。(sizeof演算子の返す型はsize_t型なので、printfでは%zuと記述)

printf("%zu\n", sizeof(int)); // 4
printf("%zu\n", sizeof(char)); // 1
printf("%zu\n", sizeof(long long)); // 8

そして、ここからデメリットである要素の挿入/削除に O(n-i) (nは全体の要素数、iは挿入/削除する要素の位置) 必要な理由を考えることができます。

1つの配列中の全ての要素はメモリ上で連続的に確保されています。

なので、要素の挿入や削除を行うと、それ以降の要素のメモリ位置を全て計算し、ずらす必要があります。 そのため、要素の挿入や削除に O(n-i) の時間がかかります。

実装

C言語では、配列はデフォルトで使うことができます。 下のコードブロックでは、要素数5のint型配列を作成しています。

int ary[5] = {10, 20, 30, 40, 50};

では、これを

int ary[5];

と実装すると、どうなるでしょうか。空の要素が5つ入った配列ができるのでしょうか。

基本的に答えは No です。

C言語では、配列の宣言を行っただけでは、中身の初期化はされません。 そのため、上記のコードを実行すると、メモリ上のランダムな値が入った配列ができてしまいます。

なので、配列を宣言するときは、下記のように初期化を行っておくことを強くお勧めします。

int ary[5] = {0};

また、ary[i]の値を取得したいとき、下のコードブロック内の2種類の書き方が可能であり、上の書き方が一般的だと思います。 下の書き方はary自体を先頭ポインタとして扱い、ポインタ演算を行っています。

int ary[5] = {10, 20, 30, 40, 50};

printf("%d\n", ary[3]); // 40
printf("%d\n", *(ary+3)); // 40