1

哪个更快，为什么？1. 数组 2. 链接列表。如果我们只想在 for 循环中迭代并打印它而不考虑 cpu 缓存。

4

5 回答 5

2

差异可以忽略不计。这将取决于您如何编写循环以及编译器中的优化。如果您在 gui 中将其打印到屏幕上，则其本身的开销将超过两者的总和。

于 2013-06-28T03:31:29.687 回答
1

无论对象存储在哪里，“打印它”部分都将是相同的。

唯一不同的部分是“移至下一项”。

对于一个数组，它涉及增加一个指针——很可能是 CPU 最快的操作。

对于链表，它涉及从内存中加载一个值——一个非常快的操作，但不如递增快。

然后还有其他问题。数组将是连续的，并且比链表占用更少的整体空间，这意味着更好地使用缓存。

但是，请记住——两者都快得令人眼花缭乱——但是，数组会稍微快一些。

于 2013-06-28T03:34:37.703 回答
0

假设您的查询仅与顺序访问有关。

对于顺序访问，阵列在任何给定时间都会更快，主要原因是更新的 CPU 对此进行了优化。

如果我们忽略 CPU 优化，即使在该数组访问之后也会更快。让我们看一下这两种操作的步骤，这将有助于理解原因。

数组访问：

int a[10];
int *ptr = a;

访问下一个元素就是做 

*(ptr++);

涉及的操作是
1. 读取 ptr 的值
2. 将当前值加 1
3. 访问新地址

链表： 

Node {  
  int data;  
  Node* next;
};

访问下一个数据将是这个 

(*(node->next))->data;
  1. 节点读取值
  2. 移入地址表以到达下一个成员
  3. 读取下一个值
  4. 访问下一个值

希望这可以帮助您理解为什么数组访问会更快。此外，当您为阵列 1 和 2 添加 CPU 优化时，将得到进一步优化。话虽如此，在现实生活中的应用中，您会感觉到可以忽略不计的差异

于 2013-06-28T11:13:14.943 回答
0

与 LinkedList 相比，数组总是更快。数组将数据直接存储到内存位置。Linkedlist 将创建节点，将数据添加到节点然后存储它。再次在迭代时，linkedlist 将使用指针转到下一个元素并打印，而在数组中，你只提供从 0 到 sizeof 数组的位置。 ..

于 2013-06-28T10:06:12.057 回答
0

数组比链表快。主要是因为数组连续存储所有元素。基本链表不保证后续访问。

不考虑 cpu 缓存是一个非常奇怪的假设，因为缓存主要是在使用数组而不是链表时提供主要性能。

链表具有将元素相互连接的指针，而数组没有这种超重结构。您迭代数组，但不直接迭代链表。

您不应该根据大 O 表示法在数学上比较它们，因为这给出了相同的性能（“细节中的魔鬼”）。

于 2013-06-28T03:54:43.777 回答