Array は連続したメモリ位置に要素を格納するため、格納された要素のアドレスが容易に計算でき、これにより特定のインデックスにある要素に速くアクセスできるようになります。 リンクリストは、そのストレージ構造においてあまり厳密ではなく、要素は通常連続した場所に格納されないので、次の要素への参照を与える追加のタグで格納される必要があります。 このようなデータ格納方式の違いにより、どのデータ構造がより適切であるかが決まります。

配列のデータ格納方式

リンクリストのデータ格納方式

大きな相違点は以下のとおりである。

• サイズ。 データは配列内の連続したメモリブロックにしか格納できないため、他のデータに上書きされる危険性があり、実行時にそのサイズを変更することはできない。 しかし、リンクリストでは、各ノードが次のノードを指すため、データは散在した (連続しない) アドレスに存在することができます。
• メモリ効率：配列ではコンパイル時、リンクリストでは実行時。 同じ要素数であれば、データと共に次のノードへの参照も格納されるため、リンクリストの方がより多くのメモリを使用する。 配列ではサイズの上限に相当するメモリを確保しなければならないが、リンクリストではデータ量に比例して段階的にサイズを大きくすることができる。 実行時間：配列のどの要素にもそのインデックスで直接アクセスできるが、リンクリストの場合、どの要素に到達するにも前の要素をすべてトラバースしなければならない。 また、配列のキャッシュの局所性（連続したメモリ割り当てによる）を改善することで、性能を大幅に向上させることができます。 その結果、ある操作（特定の要素の変更など）は配列の方が速く、別の操作（データ内の要素の挿入/削除など）はリンクリストの方が速くなります。

以下はリンクリストに有利な点である。
(1) 配列の大きさが固定されている：そのため、要素数の上限をあらかじめ知っておく必要がある。 また、一般に割り当てられたメモリは使用量に関係なく上限と同じであり、実用上、上限に達することはほとんどない。

(2) 要素の配列に新しい要素を挿入する場合、新しい要素のための部屋を作る必要があり、部屋を作るために既存の要素を移動させなければならないため、コストがかかる。

例えば、IDのソートされたリストを配列idで管理しているとする。

id = .

そして、新しいID 1005を挿入したい場合、ソート順を維持するために、1000以降の要素をすべて（1000を除いて）移動させる必要があります。

配列の削除も、特別なテクニックを使わない限りはコストがかかる。 例えば、idの1010を削除するには、1010以降を全て移動させなければならない。

そこで、リンクリストは配列に対して以下の2つの利点を提供する。
1) 動的サイズ
2) 挿入/削除の容易さ

リンクリストには以下の欠点がある。
1) ランダム・アクセスは許されない。 最初のノードから順に要素にアクセスしなければならない。 従って、リンクリストを使ったバイナリサーチはできない。
2) リストの各要素に対してポインタのための余分なメモリ空間が必要である。
3) 配列はキャッシュの局所性に優れているので、性能にかなり大きな差が出る。