なぜp ++はp = p->よりもはるかに高速です

Question

リンクリスト構造に大きなバッファが割り当てられているため、ノードは連続したメモリブロックにあります。私はリンクリストを反復処理しようとすると、2つの方法が以下のようにさまざまなパフォーマンスにつながる ：

while(index<ListCount) { 
    if (first[index++].key == key) { return;} 

} 

別の方法がある：

while(first) { 
    if (first->key == key) { return; } 
    first = first->next; 
} 

性能が異なる大があり、第二の方法は、遠く離れています最初のやり方の後ろで、なぜこれが起こったのですか？

各ノードには、次のポインタを含む16バイトの変数が含まれています。

Answer 1

擬似コードに満足しているようですので、擬似コードで回答しています。

インデックスを作成している構造がリンクされたリストである可能性があります。リンクされたリストに1,000要素があるとします。あなたが言うとき、

yourList[1000] 

1000番目の要素へのアクセスを取得する唯一の方法は、あなたのループでは、あなたの目標は、アクセスすることで、一度各要素を参照する場合、だから、この

counter = 1000; 
while(counter-- > 0) { //Ignoring potential off by 1 errors, this is for demonstration purposes only 
    node = node->next; 
} 

を行うことです1000倍 要素2：インデックスで要素を使用すると、エレメント1

を訪問している999回 要素3：998回 要素4：997回 等など

リンクリストはその要素に直接アクセスできないため、インデックスで要素にアクセスするたびに、その要素に到達するために各ポインタをクロールする必要があります。