展开链表

展开链表是线性数据结构这是一种变体链表．展开链表不是在每个节点上只存储一个元素，而是在每个节点上存储整个数组。

的优点结合了展开链表数组(内存开销小)与链表(快速插入和删除)的优点相结合，从而产生更好的性能。通过在每个节点上存储多个元素，展开链表可以有效地跨多个元素分散链表的开销。因此，如果一个展开链表在每个节点上存储一个由4个元素组成的数组，那么它将链表开销(指针)分散到这4个元素上。

他们有更快的性能，当你考虑缓存管理现代cpu。与常规的单链表相比，展开链表每个节点的开销相当高。不过，通常情况下，与现代计算中的好处相比，这个缺点是很小的。

展开链表

展开链表本质上是一个链表，其中节点持有一个值数组，而不仅仅是一个值。每个节点上的数组可以包含典型数组可以包含的任何内容，例如基本类型等抽象数据类型．每个节点都有它可以容纳的最大值数量，典型的实现使每个节点保持在的平均值左右 $3／4$能力。当某些数组太满时，它通过在数组之间移动值来实现这一点。

展开链表的开销在每个节点上稍微大一些——现在每个节点还必须存储其数组所能容纳的最大数量的值。但是，当以每个值为基础分析时，它比常规链表要低得多。随着每个节点中数组的最大大小的增加，每个值所需的平均存储空间会下降。当值的类型非常小(例如，一点)时，空间优势甚至更大。

实际上，展开链表结合了数组和链表。它利用了数组的超快速索引和存储的局部性。这两个好处都来自于静态数组的底层属性。此外，它保留了链表提供的插入和删除节点的优势。

用于在展开链表中插入和删除元素的算法在不同的实现中可能有所不同。通常，低水位标记为50%—这意味着，如果插入发生在一个节点中，而该节点不能适合该元素，则创建一个新节点，并将原始节点的一半元素插入到该节点中。相反，如果我们删除一个元素，并且该节点中的值的数量下降到50%以下，我们将从相邻数组中移动元素，以将其填充到50%以上。如果该数组也低于50%，则合并两个节点。

通常，这使平均节点的利用率在70-75%左右。相比链表，在节点大小合理的情况下，开销非常小。链表每个节点大约需要2或3块开销。展开的链表在其元素之间摊销此开销 $1 /大小$哪一项开销接近数组．

您可以通过更改低水位标记来更改展开链表的性能。通过增加它，您将增加每个节点的平均利用率。然而，这将以更频繁的分裂和合并为代价。

插入和删除的算法进行如下。在这个例子中，每个节点有一个数组数据，数组中当前的一些元素numElements，以及指向下一个节点的指针下一个．

1 2 3 4 5 6 7 8 9 10 11

如果e. numelements < e.data.size e.data.push(newElement) e. numelements ++ else创建新节点e1将e.data的最后一半移到e1中。e1.data.push(newElement) e1.data = e.numElements / 2numElements = e1.data。尺寸/ 2 + 1

1 2 3 4 5 6 7 8 9 10 11

删除(元素)在节点e e.data.remove(元素)e. numelements——while e. numelements < e.data.size / 2将元素从e.next.data放入e.data. next. numelements——e. numelements ++ if e.next. numelements < e.next.data.size / 2合并节点e和e.next删除节点e.next

对于这两个函数，程序员可以采取许多自由的做法。例如,在插入，由程序员决定在哪个节点中尝试插入。它可以是第一个节点，也可以是最后一个节点，或者可以基于您希望维护的某种排序或分组。通常情况下，它将特定于您将要处理的数据类型。

展开链表很难分析，因为它们有许多不同的实现方式，并且根据数据有许多不同的变化。然而，由于它们跨元素的摊销，它们具有很好的时间和空间分析。

时间

要插入一个元素，必须首先找到要插入的节点。这是 $O (n)$．如果该节点没有满，那么就完成了。如果已满，则必须创建一个新节点并移动值。这个过程不依赖于链表中的总值，所以它是常数时间。删除的工作原理与此相同，只是方式相反。由于链表可以相对快速地更新彼此之间的指针，而与链表的大小无关，因此我们可以利用这些常量时间操作。

索引是展开链接表的另一个重要特性。但是，它高度依赖于缓存，我们将对此进行讨论下面．

对于展开链表，重要的是要记住，真正的好处来自于实际应用，而不一定是渐近分析。

空间

展开链表所需的空间不同于 $(v / m) n$来 $2 (v / m) n$在哪里 $v$是每个节点的开销， $米$每个节点的最大元素是，和 $n$是节点数。而这最终等同于与其他线性数据结构一样的渐近空间链表，重要的是要知道它更好，因为它将开销分散到许多元素上。

展开链表的真正好处在于缓存。展开链表在进行索引时利用了这一点。

当一个程序从内存中访问一些数据时，它会提取整个页面。如果程序没有找到正确的值，我们称之为a缓存错过．这意味着我们最多可以为一个展开链表建立索引 $m / n + 1$缓存错过。这取决于的因素 $米$比普通链表快。

我们可以通过考虑缓存线的大小进一步分析这一点，我们将称之为缓存线 $B$．通常，每个节点数组的大小， $米$，将等于或是缓存线大小的倍数，以优化获取过程。在此分析中，可以遍历每个节点 $(n / B)$缓存丢失，所以我们可以遍历列表 $(m / n + 1) (n / B)$．的最佳缓存缺失值非常接近 $(m / B)$．