爲什麼p ++比p = p-> next更快

Question

我爲鏈表結構分配了一個大緩衝區，所以節點在連續的內存塊中。 當我試圖重複的鏈接列表，兩種方式會導致不同的性能如下：

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; 
} 

所以，如果在你的循環，你的目標是一次引用每個元素，通過訪問由索引的元素你正在訪問

要素1：1000倍 要素2：999次 元素3：998倍 元素4：997倍 等，等

因爲鏈接列表不能直接訪問其元素，所以每次通過索引訪問元素時，都必須通過每個指針進行爬網才能訪問該元素。