指针和对象的实现

Question

​

​

这是双向链表的多数组表示形式的图像。在原始链表中，键为4的对象跟随在键为16的对象之后。这里4出现在key2中，16出现在key5中。这里的概念是使用不带指针和对象的数组实现双向链表。有人能解释一下这些元素是如何相互联系的吗？

Answer 1

第一个包含关键字9，并存储在索引[7]中。您之所以知道这一点，是因为L包含列表头部的索引(7)。果然，您可以看到它没有"prev“值。

从这里开始，列表中的下一项存储在索引[5]中。(这是在索引[7]处的数组中的"next“中告诉我们的。这个单元格有一个键16。

从这里开始，我们继续讨论具有key 4的[2]和具有key 1的[3]。这是列表中的最后一项，因为它没有"next“。

如果你想倒退，你也可以看看"prev“的值。值得注意的是，"next“和"prev”包含的数字类型与"key“完全不同。Next和Prev引用数组索引，并在此实现中实质上取代了指针。Key包含一个数值，该数值表示列表中该点上节点的实际内容。

Answer 2

您的数据结构将正常工作。如果你在编写C++，你应该只定义next和prev。类型为size_t。但是，我看不到任何值。

1. 需要额外的数学运算才能转到下一个元素。使用传统的通过指针链接的列表，您只需访问存储在pNext字段中的地址。使用链表，计算下一个元素的地址需要一次乘法和一次加法。
2. 如果你的目标是优化内存布局以实现缓存友好-在列表的一些实现中已经做到了。例如，Microsoft在ATL中的实现就是这样做的。CAtlList类不是使用new运算符分配元素，而是批量分配它们，这就是为什么标准的STL列表在与微软的版本进行基准测试时通常会慢2倍。