静的配列

静的配列は、確保時に要素数が決まり、その配列が存在する間は長さを変更しない配列です。多くの実装では同じ型の要素を連続領域へ置き、基準位置と添字から要素位置を一定時間で計算できます。

■ 試験で押さえるポイント

• 要素長s、0始まりの添字iなら、一次元配列A[i]のアドレスは$\text{基準アドレス}+i\times s$です。このため添字による参照・更新は通常$O(1)$です。

• 長さが固定なので、必要最大数を超える要素は入れられません。大きく取り過ぎると未使用領域、小さ過ぎると別配列への作り直しが必要になります。

• 途中への挿入や削除では、順序を保つため後続要素の移動が必要で、最悪$O(n)$です。空き位置があっても配列そのものの長さが自動で伸びるわけではありません。

• 静的とは要素の値が変更不能という意味ではありません。固定されるのは要素数であり、各要素の値は通常更新できます。コンパイル時定数か実行時確保かは言語仕様によります。

■ 選択肢での判断ポイント

添字アクセス$O(1)$、固定長、連続配置という長所と、途中挿入・削除$O(n)$、容量変更不可という短所を対応付けます。値の更新禁止という説明を選びません。

例: 要素長8B、100要素の静的配列はデータ部に$100\times8=800\,\mathrm{B}$必要です。先頭への挿入で既存100要素の順序を保つなら最大100要素を後方へ移す必要があります。