C# ジェネリック リストSystem.Collections.Generic.List<T>は、拡張可能な配列をバッキング ストアとして使用して実装されます。これは、より多くの配列リスト ベースの実装と同様の方法です。リンクリストとして実装されているリストなどに対してランダム (インデックス付き) アクセスを実行する場合、これが大きな利点を提供することは明らかです。
しかし、なぜそれを循環配列として実装することを選択しなかったのか疑問に思っています。このような実装では、インデックス付きランダム アクセスとリストの末尾への追加で同じ O(1) パフォーマンスが得られます。しかし、O(1) プリペンド操作 (つまり、リストの先頭に新しい要素を挿入する) を許可し、ランダムな挿入と削除に必要な時間を平均で半分にするなど、追加の利点を提供します。
これまでのいくつかの回答の要約
@Hachet が指摘したように、循環配列の実装が と同様のインデックス作成パフォーマンスを持つためには、System.Collections.Generic.List<T>常に 2 のべき乗の容量に成長する必要があります (安価なモジュラス操作ができるように)実行されます）。これは、現在リストインスタンスの構築中にある可能性があるため、ユーザーが指定した正確な初期容量にサイズを変更することができないことを意味します。したがって、これは明らかなトレードオフの問題です。
また、いくつかのクイック & ダーティ パフォーマンス テストで示されているように、インデックス作成は循環配列の実装で約 2 倍から 5 倍遅くなる場合があります。
インデックス作成が明らかに優先事項であるため、前追加操作のパフォーマンスが向上し、ランダムな挿入/削除のパフォーマンスがわずかに向上するのに対して、これは支払うには大きすぎるペナルティになると想像できます。
これは、いくつかの補足的な回答情報を含む重複です
この質問は実際に関連しています なぜ典型的な配列リストの実装は両端がありませんか? 、質問を投稿する前に発見できませんでした。それは完全に満足のいく方法で答えられなかったと思います：
私はベンチマークを行っていませんが、これをはるかに上回る他のボトルネック (非ローカルのロード/ストアなど) があるように思えました。もっと説得力のあることを聞かなければ、おそらくこれを受け入れるでしょう、ありがとう。— メルダッド
この質問に対する回答は、コード例や、トレードオフの決定をより明確にするいくつかの定量的な数値など、循環リストのインデックス作成を適切に実行する方法に関する追加情報を提供します。そのため、それらは他の質問にある情報を補完する情報を提供します。したがって、この質問の意図はほとんど同じであることに同意します。したがって、重複と見なす必要があることに同意します。しかし、これに付随する新しい情報が失われるのは残念です.
また、どちらの質問の回答にもまだ存在しない可能性がある、実装の選択に関する潜在的な追加の理由にまだ興味があります。