連結リストどういうときに使うと有効かなーと考えていたときに下記の記事が参考になった。

連結リスト(LinkedList)の使い所 - KAYAC engineers’ blog

配列と辞書で何か足りない時は、連結リストという選択肢も持っていると良いと思います。 「入れた順にアクセスしたい辞書」は一つの例です。

また、下記のデータ構造の選択肢の整理が参考になった。

  • 固定サイズ配列(Array): 最初にこれで足りないか考える
  • 可変サイズ配列(List): 個数可変ならこっちにするが、必要な操作が限られているならキューかスタックを検討する
  • キュー(Queue): 途中に触る必要がなく、入れた順に出すならこれ
  • スタック(Stack): 何かをプールしとく時は大抵これ。可変サイズ配列の類では一番制約が厳しいのでバグりにくく速い。
  • 連結リスト(LinkedList): すでに他のデータ構造に入ってるものに順序をつけたい時にこれを併用する
  • ハッシュ(Dictionary): 検索が必要な時の第一選択
  • キーだけのハッシュ(HashSet): DictionaryでValueがいらない時。単にダブリを消したい時なら配列でソートする方がメモリを汚さない。
  • 探索木(SortedDictionary): キーの順序でループしたい辞書、といえばこれ。
  • 木: 子の配列を持つより、「最初の子と次の兄弟」形式の方が大抵は効率がいい。親の参照は不要なら持たない方がいい。
  • ヒープ: 何かをプールする時に、何かの値で順序をつけたい時にはStackでなくこっち。

連結リスト vs 配列

連結リストと配列の比較。下記記事より引用。

連結リストのちょっとした問題集

配列で要素を挿入、削除するときに、連続しているメモリーを使っているため、挿入・削除インデックス以降のデータのシフトコストがかかります。例えば、配列の冒頭（index=0）にデータを挿入しようとすると、全てのデータを1ずつずらす必要があります。この操作がO(n)となってしまいます。それに対して、連結リストではポインターの指すメモリーアドレスを変えれば良いので、O(1)で操作可能となります。

操作 配列 連結リスト
探索 O(1) O(n)
挿入 O(n) O(1)
削除 O(n) O(1)

連結リスト実装 in Ruby