配列の基本概念
配列は、同じデータ型の要素を連続したメモリ空間に格納する最も基本的なデータ構造である。各要素には添字（インデックス）を使ってアクセスすることができる。
特徴と性能
- インデックスによる直接アクセス（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リストなど）
- バッファやキャッシュの実装
- データベースのインデックス構造