>>140
[補足]
コンテナ内にN個の要素がある場合、
リンクリストは、1個の要素の追加はO(1)。しかし、全走査や探索は、O(N)。
彼の実験だと、1個追加する際に、追加する場所を探すために平均で N/2 個の
ノードを巡ることになっているから、
1要素あたりに必要な時間 = 場所を探す時間 + 追加の時間
= O(N/2) + O(1)
= O(N)
となる。一方、vector の場合、
1要素あたりに必要な時間 = 場所を探す時間 + 追加の時間
= O(N/2) + O(N/2)
= O(N)
となる。
オーダー的には、O(N)で同じだが、前者は、キャッシュミスが酷くなるので、
「係数」がとても大きくなっている。
だから、前者の方が後者よりも遅くなっていっる理由は明確。

結論は、要素を追加する際に「場所を探す」ことを行なっていて、それがLinkedList
の不得意分野だから。