19/12/02 17:15:40.51 Vo2mhncO.net
>>488
リンクリストでシーケンシャルアクセスする場合、キャッシュ以前に
ポインタをたどるようにアクセスしないといけないのですが、
最近、配列と同じような通し番号方式でアクセスしようとする人が
多くなっています。ライブラリなどは、以前にアクセスした番号が
k の場合、そのポインタを覚えておいて、プログラマが k + 1 の番号
をアクセスしようとした場合、後続のノードへのポインタをたどる
ことで高速化している場合があるので、特に問題が無い場合がありますが、
それを深く理解せずに、本当に先頭のノードからたどってしまった場合、
本来なら O(N)で済むところが、O(N^2) になってしまいます。