[解決済み】配列/配列リストよりリンクリストを使用するのはいつ？

質問

私はリストと配列をたくさん使いますが、配列リストがリンクリストと同じくらい、あるいはそれ以上に簡単に使えないというシナリオにまだ出会ったことがありません。 どなたか、リンクリストの方が特に優れている例を教えていただけませんか？

どのように解決するのですか？

リンクリストが配列よりも望ましいのは、以下のような場合です。

1. リストへの挿入/削除を一定時間行う必要がある場合（時間の予測可能性が絶対的に重要なリアルタイムコンピューティングなど）

2. リストに何個のアイテムが入るかわからない。 配列の場合、配列が大きくなりすぎると、メモリの再宣言とコピーが必要になることがあります。

3. 要素へのランダムアクセスが必要ない場合

4. リストの途中にアイテムを挿入できるようにしたい場合（プライオリティ・キューのようなもの）。

配列が望ましいのは、次のような場合です。

1. 要素へのインデックス付き/ランダムアクセスが必要な場合

2. 配列の要素数を事前に把握しておき、 配列に適切な量のメモリを割り当てることができます。

3. すべての要素を順番に反復処理するときに、スピードが必要な場合。 配列の場合はポインタの計算で各要素にアクセスできますが、リンクリストの場合は各要素のポインタに基づいてノードを探す必要があり、その結果ページフォールトが発生してパフォーマンスが低下する可能性があります。

4. メモリが気になる。 充填された配列は、リンクされたリストよりも少ないメモリしか消費しません。 配列の各要素はデータだけです。 リンクリストの各ノードは、データと、リンクリストの他の要素への1つ（またはそれ以上）のポインターを必要とします。

配列リスト（.Net のもの）は、配列の利点を提供しますが、リソースを動的に割り当てるので、リストのサイズをあまり気にする必要がなく、任意のインデックスでアイテムを削除でき、手間や要素の再シャッフルをする必要がありません。 性能面では、アレイリストは生の配列よりも遅くなります。