5

至少有两种方式来表示链表：

1.）使用基于数组的链表表示，我们在其中保留std::vector类型的结构

struct {
    <whatever-type-you-want> item ;
     int   nextitem; 
   }

这里插入到列表中，是在向量上执行 push_back() 并为下一项提供适当的值。

2）在其中你有一个遍布 RAM 的结构集合。此处插入是使用 C++ 运算符完成的new。

是否正确地说，第一种方法更有效，因为所有项目都位于内存中的连续位置，因此可以将链表增长到比第二种方法大得多的大小

在第二种方法中，可能存在带有巨大链表的内存碎片，因为这可能会更早地出现分段错误。

4

6 回答 6

5

我会在这里反对其他所有人并说，是的，第一种方法最终可能会更有效。在第二种方法中，您在堆上分配内存 O(N) 次 - N 是列表中的节点数。如果您使用的是向量，那么您只会进行 O(log N) 次堆分配。

此外，如果您使用的是 64 位机器，则在处理大量小项目时，在每个节点中保存指针的开销可能会有点过多。使用向量，您可以使用更小的值nextItem- 例如 32 位而不是 64，如果您要创建一个包含 32 位整数的列表，则内存使用量将提高 1.5。

另一个可能的优化是，如果您预先知道您将处理大量元素，您可以保留一个大向量并在很长一段时间内分配一个单一的堆。

我最近参加了一门关于自动机应用的课程，讲师正在为相当大的数据集实现一些算法。他告诉我们的其中一项技术正是您表示链表的第一种方法。我有一个课程作业，我尝试以两种方式实现（使用指针和向量和nextItem类似的东西）并且向量的表现要好得多（它也有其他优化，但向量肯定有效果）。

给其他人的注意事项

我认为@smilingbuddha 所问的更像是链接列表的集合——或者至少这就是我使用它的目的。例如，当您使用邻居列表保存图形时。您需要每个节点的所有邻居的链表（或数组，或其他）。因此，您只需保留指向每个节点最后插入的邻居的索引数组，而不是保留链表数组或向量向量。

于 2012-07-15T23:57:38.703 回答
3

使用向量实现列表是错误的。

我会解释的。容器通常被设计为实现一组特定的目标，并根据这些目标选择底层实现。

向量非常好，因为它具有连续的内存，并且您可以通过指针算术访问任何单元格。不幸的是，在向量中心插入或删除元素时，向量的性能很差。

列表具有完全相反的意图。导航到列表中的某个点非常耗时，因为您必须跟随链接，因为它不连续。但是列表的主要目的是允许快速插入、删除、重新排序、拼接、反转等。

因此，将向量视为列表的实现基础（虽然可以做到）确实不是看待这个的方式。使用向量实现列表基本上意味着您没有任何使您首先选择列表的优势。

编辑

正如其他人在下面的评论中指出的那样，如果您正在考虑更复杂的实现，那么您肯定可以从中获得性能优势。

例如，如果您维护一个包含对所有指针的引用的向量，并且您努力保持该引用向量有序，那么您可以获得指针算术访问的好处，同时仍然具有相对快速的删除/插入等。另外，由于参考向量只保存指向动态分配对象的指针，因此操作参考向量的成本并不高，而且您仍然不必使用大量连续内存区域（向量只需 NumElements * sizeof(pointer) on你的架构）。

您应该查看 std::deque 实现以获得一些乐趣。 它们在由指针链接的连续内存区域之间有一些有趣的相互作用，以加速插入/删除/其他操作。

于 2012-07-15T23:26:33.667 回答
2

相反; 使用您的第一种方法，从链表中删除项目是低效的，因为您“丢失”了存储该项目的向量中的插槽，并且必须以垃圾收集样式遍历整个列表以发现哪些插槽不是正在使用。

关于内存碎片，有很多小分配通常不是问题；实际上，作为向量需要连续分配内存，因为您需要越来越大的连续内存块，因此会导致碎片。此外，每次调整向量大小时，都会导致复制大块内存。

实际上，您的第一个答案是自负内存分配器和内存管理单元的工作。内存分配器的工作是分配小块内存；MMU（除其他外）的工作是确保内存块之间的指针即使在物理内存中移动时也继续指向相同的逻辑内存。您的nextitemint 成员本质上用作指针。除非您有非常特殊的要求，否则硬件、内核和 malloc 可以比您做得更好。

于 2012-07-15T23:23:48.783 回答
1

你的逻辑是完全倒退的。第一种方法要求内存是连续的，一旦可用的连续内存不足，就会失败。您的第二种方法可以使用内存，无论是否连续，并且将继续工作，直到完全没有内存为止。

于 2012-07-15T23:38:41.077 回答
0

如果在案例 #1 中从列表中删除一个元素，剩余元素的很大一部分可能会nextitem弄乱它们的索引。所以＃2是通常的方法，如果正确实施不会导致任何内存问题，除非您尝试将大量元素插入列表或任何其他容器中。

于 2012-07-15T23:27:56.663 回答
0

您的第一种方法似乎混合了两种算法，因此，我会说效率较低。

链表的优点之一是可以轻松插入和删除项目。然而，使用您的方法，他们需要转移数据。您也可以使用可简单调整大小的数组。

此外，数组要求内存是连续的。在某些情况下，在处理大量数据时，您会比使用真正的链表更快地耗尽内存，因为有时可能会有一定数量的内存可用，但不是连续可用的。

于 2012-07-15T23:24:09.310 回答