JavaでLinkedListを削除（インデックス）するよりも遅くなるのはなぜですか？

Question

私は、100000項目のStringを持つLinkedListを持っています。get、remove、addなどのインデックスを持つ操作を実行すると、同じメカニズムに見えます。 まず、Node [index]にアクセスするためにリストをブラウズし、別の操作を行います。 は "get"とNodeの項目だけを参照します。 しかし、なぜ "取得" 操作である

for(int index=99999;index>=0;index--){ 
    links.get(index); 
} 

"削除" 操作よりもたくさんのより多くの時間がかかるナノ秒単位で時間を取得：15083052805ナノ秒単位で

for(int index=99999;index>=0;index--){ 
    links.remove(index); 
} 

デル時間：2310625

のLinkedListの関数：

public E get(int index) { 
    checkElementIndex(index); 
    return node(index).item; 
} 

public E remove(int index) { 
    checkElementIndex(index); 
    return unlink(node(index)); 
} 

Answer 1

あなたはそうではないようです最初のループに入る前にポーリングSystem.currentTimeMillis()（現在の時刻を取得）。

Answer 2

要素をインデックスNに取得するのは非常にコストがかかります。実際に要素に到達するには、要素に到達するまでリストノードを移動する必要があるからです。

あなたのループ内の要素を削除するとき、リストの最後の要素を削除していることに気付いてください。iはそのループ内のlist.size（） - 1に正確に対応します。

node（index）メソッドは、インデックスが0またはlist.size（）に近いかどうかによって、実際には前面/背面からの検索によってアクセスを最適化します。あなたのケースでは、その常に後ろから検索し、最初の試行でヒットを削除します。

学習する教訓：LinkedListはではなく、ランダムインデックスでアクセスするのに適したリストタイプです。