データ構造の落とし穴8選｜LinkedListが遅い理由

RJC Techチーム

データ構造の計算量、O(1)とかO(log n)とか、覚えましたよね。

でも実務では、教科書で速いはずの構造が実機で負けたり、O(1)が突然O(n)に化けたりします。理論と実機の間には、段差があるんです。今回は、「教科書で速いはずのLinkedListが、実は遅い」話から、その段差を8つ集めました。1つでも知らなかったら儲けものです。

① ArrayListのaddは、「たまに全コピー」です

list.add(x) の計算量はO(1)——平均は、です。

内部は固定長の配列で、埋まるとより大きい配列を新しく確保して、全要素をコピーします。この瞬間だけO(n)。

ただ、拡張のたびに容量を一定の倍率で増やしている（Javaでは約1.5倍）ので、コピーのコストを全体でならすとO(1)に収まります（ならし計算量）。

だから、要素数が読めているなら最初に容量を指定しておくと、途中の全コピーがゼロになる。「大量addの前に new ArrayList<>(想定数)」は、地味に効く一手なんです。

HashMapの取得はO(1)——ハッシュがうまく分散していれば、です。

複数のキーが同じ場所に集まると（衝突）、そこは連結リストになり、線形探索O(n)に劣化します。

そこでJavaのHashMapは、1箇所の衝突が8個を超えると（表がある程度大きくなっていれば）、その部分を木構造（赤黒木）に変えてO(log n)で耐えるという改良を入れています。

とはいえ大前提は、hashCodeがちゃんと分散すること。自作クラスをキーにするときにhashCodeを雑に実装すると、O(1)のはずが全部詰まる。「O(1)は、良いhashCodeの上に成り立つ約束」なんです。

教科書では「途中の挿入削除はLinkedListが速い（O(1)）」。でも実機では、ほとんどの場面でArrayListの方が速いんです。理由は2つ。

ArrayListは連続メモリなので、多少のコピーを払ってもキャッシュの恩恵が勝つ。

「計算量では勝っているのに、実機では負ける」の代表例。JavaのLinkedListを書いたジョシュア・ブロック本人が「自分が書いたけど、自分では使わない」と言っているほどです。

配列から要素を1個消したい。真ん中に穴が空きますよね。

要件	やり方	計算量
順序を保つ	後ろを全部前に詰める	O(n)
順序は要らない	最後の要素を穴に移動して、末尾を縮める	O(1)

この「末尾と入れ替え（swap-remove）」は、知らないと絶対に思いつかない一手です。

「並び順はどうでもいいコレクション」なら、削除が劇的に速くなる。順序という要件を1つ捨てるだけで、計算量が変わるんです。

スタック（後入れ先出し）とキュー（先入れ先出し）。別々の構造だと思っていませんか。

実はどちらも、配列やリストの「使い方の制約」にすぎません。両端のどちらから出し入れするかを決めただけ。

そして深いのがここで。「探索の途中を、スタックで管理すれば深さ優先、キューにすれば幅優先」になります。同じ探索コードの、データ構造を差し替えるだけで挙動が変わる。

データ構造は「入れ物」であると同時に、「アルゴリズムの性格を決めるつまみ」でもあるんです。

100万件から上位3件を取りたい。全部ソート（O(n log n)）していませんか。

ヒープ（優先度付きキュー）を使えば、3件ぶんの小さなヒープを保ちながら全体を1回舐めるだけ。計算量はO(n log k)で、kが小さければほぼO(n)です。

「常に最大（最小）を効率よく取り出す」のがヒープの仕事。ランキング、締切の近いタスク、経路探索の次候補選び——全体を並べずに、欲しいものだけ取り出す場面で効きます。

全ソートは、実は贅沢な選択だったりするんです。

巨大なデータに対して「この要素、含まれてる？」を高速・省メモリで知りたい。

ブルームフィルタという構造があります。要素そのものを保存せず、ビット列だけで管理する。特徴が独特で——「無い」は確実、「ある」は“たぶんある”（ごくまれに誤検知する）。

この割り切りのおかげで、桁違いに小さいメモリで判定できます。「DBを引く前のふるい」として使えば、無駄なアクセスの大半を手前で弾ける。

100%の正確さを少し譲る代わりに、メモリを桁で得する。実務の巨大データで効く発想なんです。

最後に、選び方の話でまとめます。

データ構造選びは、計算量表の暗記ではありません。「その中で、何を一番多くやるか」で決まります。