为什么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倍 等，等

因为链接列表不能直接访问其元素，所以每次通过索引访问元素时，都必须通过每个指针进行爬网才能访问该元素。