这是双链表的多数组表示的图像。键为 4 的对象在原始链表中键为 16 的对象之后。这里 4 出现在 key[2] 中，16 出现在 key[5] 中。这里的概念是使用没有指针和对象的数组来实现双链表。有人可以解释这些元素是如何相互联系的。
问问题
711 次
2 回答
2
第一个有 key 9，并存储在 index [7]。您知道这是因为L包含列表头的索引 (7)。果然，您可以看到它没有“prev”值。
从这里开始，列表中的下一项存储在 index[5]中。（这就是它在 index 数组中的“next”中告诉我们的内容[7]。这个单元格的键为16.
从这里我们继续[2]，有钥匙4，[3]有钥匙1。这是列表中的最后一项，因为它没有“下一个”。
如果您想倒退，您也可以查看“prev”值。需要注意的是，“next”和“prev”包含与“key”完全不同类型的数字。Next 和 Prev 指的是数组索引，并且在此实现中实质上代替了指针。Key 包含一个数值，表示该节点在列表中该点的实际内容。
于 2013-02-16T03:46:58.003 回答
0
您的数据结构将正常工作。如果您正在编写 C++，您应该只定义 next 和 prev。size_t 类型。但是，我看不到任何价值。
需要额外的数学运算才能转到下一个元素。使用指针链接的传统列表，您只需访问存储在 pNext 字段中的地址。使用您的链表，计算下一个元素的地址需要一次乘法和一次加法。
如果您的目标是优化内存布局以实现缓存友好性 - 它已经在某些列表实现中完成。例如，微软在 ATL 中的实现就是这样做的。CAtlList 类不是使用 new 运算符分配元素，而是分批分配它们，这就是为什么标准 STL 列表在针对 Microsoft 版本进行基准测试时通常会慢 2 倍。
于 2013-02-16T04:05:30.517 回答