配列とリンクリストの違いについて、それぞれのメリット・デメリットをまとめる
配列
メリット
・ランダムな値の読み取りが高速
配列はインデックスを持つので、ランダムな値を検索する時に非常に高速。そのインデックスの要素に飛ぶだけでいい。
その性質のため二分探索などとも相性がいい。
デメリット
・メモリ上の連続したスロットを使用する
どういう事かと言うと、配列の長さ分の連続したスロットが空いていないとその配列は作成できない。
例えば長さが10の配列を生成する場合、メモリには10個の連続したスロットがないといけない。
（10個のスロットが点々としていたり、離れていたらダメ）
また要素を追加した結果、スロットが足りなくなった場合は
必要な分の連続したスロットが存在する場所に行き配列を作り直す。
・要素の追加、削除が遅い
追加や削除がされた要素から、後の要素のインデックスは全て修正する必要がある。
そのため要素の先頭に追加や削除をした場合、全ての要素のインデックスを再計算することとなる。
情報処理技術者試験の午前問題でよく出てたのはこれ
リンクリスト （基本的に配列と逆の特徴を持つ）
メリット
・リストの要素は、メモリ上のどこにでも配置可能
配列と違いリストは次の要素へのアドレスを持つ。
そのため次の要素が必ずしも連続したスロットに存在する必要はなく、点々としたスロットに存在することが可能。
また要素が追加されてもリストを再生成する必要はない。
・要素の追加、削除が高速
要素の追加や削除がされても、その前の要素が持つ次要素へのアドレスを修正するのみでいい。
デメリット
・ランダムな値の読み取りが遅い
配列と違いインデックスを持たないため、最初の要素から読み取りたい要素まで順番に検索する必要がある。
つまり5つ目の要素を読み取りたい場合、1 > 2 > 3 > 4 と次の要素のアドレスを追わなくてはならない。
ただしすべての要素を読み取る場合は、配列と性能差はない。
まとめ
【配列】
・ランダムな読み取りが高速。O(1)
・要素の追加、削除が遅い。O(N)
・メモリ上の連続したスロットが必要。
【リスト】
・ランダムな読み取りが遅い。O(N)
・要素の追加、削除が高速。O(1)
・メモリ上に連続したスロットは必要なく、要素分の空きスロットがあればいい。