従来は、リンク先リスト（単独リンクリスト）を使用しているときに、nextとprevious隣接ノードのポインタ。配列では、新しい要素（挿入の場合）のためのスペースを作るために、多数の要素を押さなければなりません。リンクリストの挿入/削除効率
しかし、リンクリストの場合に挿入/削除の場所を見つけるプロセスは、配列（ランダムアクセス）と比較して、特に大きなデータがある場合には非常にコストがかかる（逐次検索）。
この要素は、配列に対するリンクリストの挿入/削除の効率を大幅に低下させますか？あるいは、配列の場合に要素をシフトするのに必要な時間は、順次アクセスよりも大きな問題ですか？
アレイ（ランダムアクセス）と比較して、リンクされたリストの場合には、挿入/欠失の位置を見つけるプロセスは、（シーケンシャルサーチ）は、非常に高価である
比較があるため、間違っています挿入/削除操作の効率を比較しています。時間複雑に突き出すためにO(n)
コピー配列要素を持つリンクリストで
シーケンシャル検索：代わりに、この2つの要因を比較します。 n個の配列要素をコピーする必要があるかもしれません。アレイでは
：基本となる型がPODであれば、それだけでrealloc、そうでない場合、それは、オブジェクトのoperator=でそれらを移動する必要がありますすることができます。
だから、すべてがの配列の使用を好むわけではないことがわかります。 リンクリストは、同じデータを何度も何度もコピーする必要がありません。
特に大きなデータがある場合。
これは、押している間にコピーされる配列要素の数が増えることを意味します。
ただし、リンクされたリストの 場合には、挿入/欠失の位置を見つけるプロセスは、我々は、大規模なデータを持っている特別な場合、（シーケンシャルサーチ） アレイ（ランダムアクセス）に比べて非常に高価です。あなたはそれがどこにあるか知っていて、それへのポインタまたはインデックスのように持っていない場合
ランダムアクセスを使用すると、要素を検索する場合、何も解決しないと、それがどこにあるかわからない、と、もはやありませんリンクされたリストや配列を使用している場合でも、要素にアクセスするための検索。この場合、ランダムアクセスが役立つのは、配列がソートされている場合のみです。この場合、ランダムアクセスによってバイナリ検索が可能です。
この要素は、配列上のリンクリストの挿入/削除の効率を大幅に低下させますか？または、配列の場合に要素を押し出すためには、より大きな問題 が必要ですか？ 順次アクセスよりも問題がありますか？
一般に、配列とリンクリストの両方には、要素を見つけるために線形時間の検索が必要なので、少なくとも順序付けられていない配列はありません。そして、人々が重要でない入力サイズに対して頻繁に重要なパスを探す必要がある場合、ハッシュテーブルやバランスのとれたバイナリツリーや試行などを使用することがよくあります。
多くの場合、アルゴリズムの複雑さに関係しないため、多くのパフォーマンスクリティカルなフィールドでリンクリストより配列が優先されます。なぜなら、配列は要素を連続して格納することが保証されているからです。これは、逐次処理のための参照の非常に良いローカリティを提供します。
また、一定時間内にアレイから削除する方法もあります。一例として、配列からn番目の要素を一定時間に削除したい場合は、配列の最後の要素と交換し、最後の要素を一定時間内に削除します。要素を並べ替えることが許されている場合、ギャップを閉じるために必ずしもすべての要素をシャッフルする必要はありません。
リンクされたリストは、ノードを連続して保存する場合と保存しない場合があります。ノードを配列に格納する場合（配列ベースのコンテナまたはアロケータのいずれかを使用）のように、パフォーマンスクリティカルなコンテキストでは、多くの場合、それらは便利です。さもなければそれらをトラバースすると、アクセスされているすべての単一ノードの潜在的にキャッシュミスを伴うキャッシュミスが発生することがあります。
パフォーマンスを比較した素晴らしいグラフ（一番下の行はベクトル表示の非効率性と格納された要素のサイズの増加です）https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque .html – orhtej2