LinkedListがキャッシュ効率が悪いというのも机上の空論。
なぜなら、机上の空論者は、LinkedListのノードのアドレスが「ランダム」で
あると間違った仮定するから。
実際には基本的に連続しており、多くの場合は連続して無いとしても
軽微な数バイトの隙間がところどころ空いているだけ。
大きく変化することもあるが、それは全体の数箇所だけ。
なぜなら、挿入箇所は、一箇所から始まってその周辺を押し広げてノードを挿入している
だけで、それが少数あるだけだから、アドレスが大きく変わる箇所はわずかで、
「バースト的」になっているから。
机上の空論者は、ノードアドレスをランダムだと考えるから、キャッシュ・ミスが常に
起きると考えてしまう。ところが、そんな状況はまず有りえない。