配列の基本概念

配列は、同じデータ型の要素を連続したメモリ空間に格納する最も基本的なデータ構造である。各要素には添字（インデックス）を使ってアクセスすることができる。

特徴と性能

インデックスによる直接アクセス（O(1)の時間複雑度）
連続したメモリ空間による効率的なメモリ使用
固定サイズ（静的配列）または可変サイズ（動的配列）
キャッシュの局所性が高く、高速な要素走査が可能

主な操作と時間計算量

操作	時間計算量	説明
要素へのアクセス	O(1)	インデックスを使用した直接アクセス
要素の挿入（末尾）	O(1)	動的配列の場合、再配置が必要な場合はO(n)
要素の挿入（先頭/中間）	O(n)	後続要素のシフトが必要
要素の削除（末尾）	O(1)	最後の要素の削除
要素の削除（先頭/中間）	O(n)	後続要素のシフトが必要
配列の探索	O(n)	線形探索の場合

配列の種類

1. 静的配列

サイズが固定された配列で、宣言時にメモリが確保される。

Rubyでの実装例

# 固定サイズの配列作成
array = Array.new(5).freeze

# 要素の追加
array[0] = 1
array[1] = 2
array[2] = 3

# 要素へのアクセス
puts array[1]  # 2を出力

# 配列の走査
array.each { |element| puts element }

# 配列のメソッドを使用した操作
array.push(4)        # 実行時にエラーになる
array.unshift(0)     # 実行時にエラーになる
array.pop            # 実行時にエラーになる
array.shift          # 実行時にエラーになる
array.insert(2, 10)  # 実行時にエラーになる

2. 動的配列

サイズが可変の配列で、要素数に応じて自動的にメモリが再割り当てされる。

Rubyでの実装例

# 動的配列の操作
array = []
array << 1          # 末尾に追加（push演算子）
array.concat([2,3]) # 複数要素の追加
array.delete_at(1)  # インデックス1の要素を削除

# 配列の変換と処理
mapped = array.map { |x| x * 2 }    # 各要素を2倍
filtered = array.select { |x| x > 2} # 2より大きい要素を抽出

メリットとデメリット

メリット

要素への高速なアクセス（O(1)）
メモリ効率が良い（連続したメモリ空間）
キャッシュの局所性による高速な走査
実装が単純で理解しやすい

デメリット

固定サイズの場合、サイズ変更が不可能
要素の挿入・削除が非効率（O(n)）
メモリの事前確保が必要
連続したメモリ空間が必要

一般的な使用例

行列演算や画像処理（多次元配列）
固定長データの格納（ユーザーIDリストなど）
バッファやキャッシュの実装
データベースのインデックス構造

参照

¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹