[CS基礎 #6] データ構造：配列と連結リスト

データ構造とは？

データ構造は、データをどのように保存し、取り出し、変更するかを決める仕組みです。適切なデータ構造を選ぶと、コードはシンプルで速くなります。

配列

配列は、データを連続した領域に並べて保存する構造です。

[10][20][30][40]

インデックスを使えば、特定の位置の要素にすばやくアクセスできます。

操作	計算量
インデックスアクセス	O(1)
末尾追加	多くの場合O(1)
中間挿入	O(n)
中間削除	O(n)

連結リスト

連結リストは、ノードが次のノードへの参照を持つ構造です。

[10] -> [20] -> [30]

中間の挿入や削除は得意ですが、特定の位置へ直接アクセスするのは苦手です。

使い分け

場面	向いている構造
インデックスで頻繁に読む	配列
順番に処理する	配列または連結リスト
中間挿入・削除が多い	連結リスト
キャッシュ効率を重視	配列

学習のポイント

配列と連結リストは、他のデータ構造を理解するための土台です。時間計算量とメモリ上の配置を意識すると、なぜ使い分けが必要なのか分かりやすくなります。