谁能解释一下什么是展开链表。据我所知，它是一个链表，其中每个节点都有元素数组。当然，这使搜索更快。
在这个图中，添加那张图中的数据 1,2,3 是清楚的，没有复杂性……但是为什么他们在第二个节点中添加了 4？为什么不在第一个节点的第四个元素中？这样做有什么好处？他们在那里使用的分裂策略是什么？
问问题
5308 次
3 回答
2
好处是，他们可以在之后插入数据而无需移动列表中的每个项目。是否要分段也取决于您。您可以使添加功能检查最后一个节点是否已满 3/4，在这种情况下创建一个新节点。或者他们可能做了什么：
如果数组已经满了，我们首先在当前节点之前或之后插入一个新节点，并将当前节点中的一半元素移动到其中。（http://en.wikipedia.org/wiki/Unrolled_linked_list）
于 2013-05-09T10:37:33.987 回答
0
数字 4 添加到第一个节点的第 4 个元素。添加 5 后，它会拆分该节点，其中 1、2、3 位于节点 1 中，4、5 位于节点 2 中。
于 2013-05-09T10:39:10.423 回答
0
假设你现在的元素不超过'n'（当然你可以在以后添加元素）并且你想创建一个链表，就缓存性能而言，最好的方法是选择Unrolledlinked list。您在 n 上创建一个大小为 ceil 平方根的块，然后如果其大小小于 n 的平方根的 ceil，则开始在块中添加元素。因此，您最终在 n 个块上获得了平方根的地板。这在搜索链表中的第 k 个节点时很有用，因为它的复杂性现在已从 n 降低到 n 的平方根。
当块已满时，意味着如果块包含等于 n 个元素的平方根，则必须进行移位操作，使该块中的尾部成为下一个块的头部，而下一个块的尾部成为头部它的下一个等等，直到你点击 NULL
在每个块中，维护的是循环链表，而不是简单的链表。
希望这可以帮助.. ：）
于 2014-09-11T12:43:02.377 回答