2

我不是 100% 确定如何描述这一点，但我会尽力而为。我目前正在开发一个项目，其中他们有一个结构（称为集合），其中包含指向一组结构（称为 objs）的指针。要访问这些结构集，on 必须遍历它们的内存地址（如数组）。主结构在其集合中具有结构的数量。我就是这样做的

objs = set->objs;

for(n=0; n < set->numObjs; n++)
{
  do_something(objs);
  objs++;
}

我的问题是，链表会更安全、更快还是更好？一个结构数组怎么样？

谢谢。

4

3 回答 3

3

数组通常在元素方面的遍历和操作要快得多，因为所有数据都连续位于内存中，因此将非常有效地使用 CPU 缓存。相比之下，链表在缓存使用方面或多或少是最差的，因为每个链表节点都可能很容易地最终位于内存的一个完全独立的部分，并独自占据整个缓存行。

另一方面，链表作为容器更容易操作，因为您可以以非常低的成本插入和删除元素，而您根本无法真正使用数组，除非您愿意移动整个片段周围的阵列。

任你选。

或者更好的是，尝试两者并配置文件。

于 2012-08-27T14:24:44.777 回答
1

这个源代码有些不完整，但似乎 objs 是指向与 set->objs 中相同类型的指针。您正在做的是通过使用指针算法而不是使用数组语法索引来迭代这些 objs 的列表或数组。但是，obj 列表存储在顺序内存中，否则指针增量将无法为您提供顺序列表中的下一个 obj。

问题实际上是就维护和更改列表而言，您想要执行什么样的操作。例如，如果列表基本上是一个很少更改的静态列表，那么顺序列表应该可以正常工作。如果唯一的主要操作是将某些内容添加到列表中，那么如果您知道最大数量并且可以分配那么多顺序内存，那么顺序列表可能会很好。

链表的亮点在于以下领域：（1）从列表中插入和/或删除元素，尤其是不在前面或后面的元素，（2）能够增长并且不必依赖于特定的数字列表中的元素。

为了增加一个固定大小的顺序列表，您通常必须分配一个新的内存区域并将列表复制到新的内存区域。

另一种选择是拥有一个基本上是一组链接顺序列表的数据结构。随着顺序列表填满并且您需要更多空间，您只需分配另一个顺序列表区域，然后将两者链接起来。但是，使用这种方法，您可能需要额外的代码来管理空白空间，这取决于您是需要删除项目还是在插入新项目时将它们按某种排序顺序排列。

这是关于链接列表的维基百科文章。

于 2012-08-27T14:35:01.163 回答
0

链表会更慢，因为您可能不会有效地使用内存缓存（与数组不同，列表节点可能位于不同的内存页面上），但是使用链表可能更容易也更安全。如果您发现链表解决方案太慢，我建议您仅使用数组。

于 2012-08-27T14:21:49.287 回答