データ構造 Part.1-1 「静的配列」

静的配列

目次

1. 静的配列とは
2. 各プログラミング言語での静的配列
3. 想定される操作とその計算時間
4. さいごに

静的配列とは

同じ型の要素を複数保持することができるデータ構造のこと。
添え字(index)と呼ばれる先頭要素からの番号で要素を参照することができる。
先頭要素の添え字は 0 である（ことが多い）。

int scoreArray[2];
scoreArray[0] = 100;
scoreArray[1] = 50;
int average = (scoreArray[0] + scoreArray[1]) / 2;
// average is 75

各プログラミング言語での静的配列

プログラミングの経験がある視聴者がイメージしやすいように、
各プログラミング言語における静的配列とそうでないものを挙げます。

• 静的配列の例
  • C言語またはC++における T[]
  • Javaにおける T[]
• 静的配列ではない例
  • C++における std::vector
  • Javaにおける ArrayList と LinkedList
  • JavaScriptにおける Array ( [] )
  • 多くのプログラミング言語でのリスト

ごく一部の言語ではありますが、静的配列とそうでないものの例をあげました。

静的配列をあえて使えないようにしているプログラミング言語が主流になってきています。
それがなぜかは後述します。

想定される操作とその計算時間

添え字を用いた要素の参照（[]）

先頭要素の添え字を0として、先頭要素からの番号で要素を参照できる。
要素の参照ができない添え字として、負の数や配列の長さ以上の数が挙げられる。

int scoreArray[2];
scoreArray[0] = 100;
scoreArray[1] = 50;

// Index Out Of Bounds
// scoreArray[-1], scoreArray[2]

int average = (scoreArray[0] + scoreArray[1]) / 2;
// average is 75

あらゆる1要素の参照にかかる時間は O(1) の定数時間である。
規則性のない参照（ランダムアクセス）に強いデータ構造である。

先頭または末尾から順番に参照することをシーケンシャルアクセスという。
配列はシーケンシャルアクセスにも強い。

さいごに

この記事では静的配列の概要と、各言語での静的配列の名前、
想定される操作とその計算時間を紹介しました。

静的配列はそのシンプルな設計から、少し低いレイヤで何かをする際は、
何かと直接もしくは間接的に使うことになるデータ構造です。
そのため学んでおいて損をするということはないはずです。

次以降の記事では、静的配列のメリットやデメリットを紹介します。
またそのデメリットを克服した新しいデータ構造も紹介したいと思います。