[解決済み] リンクリストはどのような場合に有効か？

質問

人々がリンクリストを使おうとしているのを見るたびに、私にはそれが悪い（あるいは非常に悪い）選択のように思えます。おそらく、リンクリストがデータ構造の良い選択である、またはそうでない状況を探ることは有用でしょう。

理想的には、回答はデータ構造を選択する際に使用する基準について説明し、どのデータ構造が特定の状況下で最もよく機能すると思われるかを説明するでしょう。

編集部：私は、回答の数だけでなく、その質にも非常に感銘を受けたと言わざるを得ません。私は1つしか受け入れられませんが、もう少し良いものがなかったら受け入れる価値があったと言わざるを得ないものが2つか3つあります。リンクリストが本当に有利な状況を示しているのは、2つだけ（特に私が最終的に受け入れたもの）でした。スティーブ・ジェソップは、1つだけでなく3つの異なる答えを導き出し、そのどれもが非常に印象的だったので、ある種の栄誉を受けるに値すると思います。もちろん、回答ではなく、コメントとして投稿されたものですが、Neil のブログのエントリも読む価値があると思います。

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

並列データ構造のために有用です。 (現在、以下に非同時的な実際の使用例があります - それはもし ニール はFORTRANについて触れていませんでした;-)

たとえば ConcurrentDictionary<TKey, TValue> は、.NET 4.0 RCでは、リンクリストを使って同じバケツにハッシュするアイテムを連結しています。

の基礎となるデータ構造は ConcurrentStack<T> もリンクリストです。

ConcurrentStack<T> の基礎となるデータ構造の一つです。 新しいスレッドプール の基礎となるデータ構造の 1 つです (ローカルの "queues" は基本的にスタックとして実装されています)。(他の主なサポート構造である ConcurrentQueue<T> .)

新しいスレッドプールは、次に、新しい タスク並列ライブラリ .

リンクリストは現在、少なくとも1つの偉大な新技術の主要な支持構造の1つとして機能しています。

(単一のリンクされたリストが説得力のある ロックフリー - で主要な操作が行えるので、このような場合、待ち時間がないわけではありませんが、魅力的な選択となります。 CAS (+retries) で実行できるからです。 Javaや.NETのような最新のGC-d環境では ABA問題 は簡単に回避することができます。 追加したアイテムを新しく作成したノードでラップし、それらのノードを再利用しないだけで、GC にその仕事をさせることができます。 ABA 問題のページでは、ロックフリーのスタックの実装も紹介されています。

編集 : @Neilです。 実は、あなたがFORTRANについて述べたことで、同じ種類のリンクリストが、おそらく.NETで最も使用され乱用されているデータ構造で見られることを思い出しました。 プレーンな.NETジェネリック Dictionary<TKey, TValue> .

1つではなく、多くのリンクリストが配列に格納されています。

• 挿入/削除時に多くの小さな（デ）アロケーションを行うことを避けることができます。
• 配列が順次充填されるため、ハッシュテーブルの初期ロードはかなり高速です（CPUキャッシュと非常によく連携します）。
• チェーン ハッシュ テーブルがメモリに関して高価であることは言うまでもなく、この "trick" は x64 で "pointer sizes" を半分に削減します。

本質的に、多くのリンクリストは配列に格納されます。(使用するバケットごとに 1 つ)。 再利用可能なノードの空きリストは、（削除があった場合）それらの間に "interwoven"されます。 リハッシュ開始時/終了時に配列が確保され、その中にチェーンのノードが保持される。また フリー ポインタ（配列のインデックス）があり、これは削除の際に使用されます。つまり、信じられないかもしれませんが、FORTRANのテクニックはまだ生きているのです。(...そして、最も一般的に使用される .NET データ構造の 1 つ以外にはありません;-)。