链表数据结构与算法图（跳转链表、自组织链表）

解决常见的链表搜索问题。首先，分析问题的瓶颈。对于搜索来说，自然是从头到尾按顺序搜索。那么如何才能更快的找到目标元素呢？对链表中的元素进行排序可以加快搜索过程，但仍然需要顺序搜索。因此，对于链表来说，最好允许跳过某些节点以避免顺序处理。基于以上思想，提出了跳过链表的概念。跳转链表是有序链表的一个有趣的变体，可以执行非顺序搜索。算法复杂度为O(lgn)，比O(n)低一个数量级。
首先使用自然语言概述跳转列表。假设我们已经有一个由 N 个元素组成的有序单向链表，我们取出 n1 个元素来创建一个新的单向链表。我们称此为二层链表，然后从二层链表中继续删除层链表中的元素n2，形成三层链表。最后，在此循环中，您可以任意定义 m 层的链接列表，m。这是一个跳跃链表。简单的链表就像盖高楼一样，只有一层，从头到尾只能查找一个元素。但是，如果我们组织一个多层链表，可以从最高到最低逐层搜索，在这个过程中可以跳过很多元素。达到快速查找的目的。数学定义如下：

位于2^(k-1)*i的节点指向位于2^(k-1)*(i+1)的节点，约束条件：i>=1,1<=k<=lgn，lgn向下取整复制代码

跳转链表：

这意味着第 2 个节点指向前面 2 个单位的节点，第 4 个节点指向前面 4 个单位的节点，以此类推。为此，请在链表中包含不同数量的指针：一半节点有一个指针，1/4 节点有两个指针，1/8 节点有 3 个指针，依此类推。

搜索逻辑概述：

假设您要查找元素el。您应该从顶层指针开始，当找到元素时搜索将成功结束。如果到达链表末尾或者遇到元素key大于元素el，则从包含的节点之前的节点重新开始搜索，但是这次从比上一级低一级的指标开始搜索。直到找到el，或者一级指针到达链表末尾，或者找到大于el的元素，搜索才会停止。

例如，如果您要在上面链接的跳转列表中查找 5，那么您首先要尝试的是第四层。本层第一个节点是8，如果查找不成功，则回到节点8的上一个节点，找到指针root，找到root第3层，先找到4，再找到8，如果查找不成功，则回退到前一个节点节点8。找到节点4，搜索节点4的第二层，先找到6，如果搜索不成功，则回到节点6的上一个节点。找到节点4，搜索节点4的第一层，先找到5，然后搜索是成功的。

动态图如下：

搜索跳过链接列表的复杂度仅为O(lgn)。这是非常好的效率，但是由于链表的设计，插入和删除的效率非常低。为了插入新元素，必须重构新节点后面的所有节点，这显然是令人望而却步的。为了保留跳转链表的搜索优势，同时避免插入和删除节点时需要重建链表，我们可以放弃对各级节点位置的要求，只保留对各级节点数量的要求。通过计算，我们可以知道不同层之间的节点数比例如下：

假设层数为n，则第n层到第1层的节点数比例为：2^0 : 2^1 : ... : 2^ (n -1)

例如上面的链表有4层，所以比例是1:2:4:8。需要注意的一点是，由于我们放弃了位置要求，因此链表的级别可以任意指定，通常为4级。即使节点数为10000，如果层间节点数比例不变，搜索也不会受到影响。效率。

采用上述方法，增删算法的复杂度也保持在O(lgn)。这是因为添加和删除也依赖于搜索。跳过链表是添加或删除时首先依赖的顺序列表。只有找到节点的位置后，才能进行后续的操作。

加法操作我就不多说了。其逻辑与常规链表类似。普通链表只插入一层，而跳跃链表插入首先确定新插入节点的层级m（可以使用随机数确定，只需保留层级节点的比例即可），然后将节点插入到链表的每一层中。

总结：

相比于自适应树或AVL树等更高级的数据结构，跳跃链表的效率相当不错，因此用跳跃链表替代这些数据结构是可以的。

• 自组织链表

我们已经几乎涵盖了链表的数据结构。其实我们上面讨论的是链表的静态结构，我们研究的是基于有组织的链表的算法。我们还可以使用一些方法来动态组织链表，以提高搜索效率。动态组织的链表可以称为自组织链表。

这里有4种动态组织链表的方法：

1. 前推法。找到想要的元素后，将其放在链表的顶部。
2. 换位法。找到所需的元素后，如果它不在链表的开头，则与其前一个元素交换位置。
3. 计数法。按元素的访问次数对链表进行排序。
4. 排序方法。按节点的元素属性对链表进行排序。

我们用一组表来说明这4种方法：

假设有一个空链表和一个数据流-ACBCDADACACCEE。我们利用以上4种方法将数据流动态组织成链表。

要测试这些方法的有效性，请将实际比较次数与最大可能比较次数进行比较。通过在处理每个元素时添加链表的长度来计算最大可能的比较次数。例如，在上表中，数据体包含14个字母。在处理每个字母之前记录链表的长度。结果是0+1+2+3+3+4+4+4+4+4+4+4+4+5=46，这个总长度是用来和比较次数进行比较的。对于所有方法来说，总长度是相同的，并且是最大的，因此可以用来进行比较。

我们通过将不同文本中的单词排列成链表来测试上述方法的搜索效率：

我们比较了使用两种不同嵌入方法的普通方法、重定向方法和转置方法。从上面的数据总结出以下几个特点：

• 随着数据量的增加，所有方法的效率都会提高
• 在末尾插入数据总是比在前面插入数据更高效
• 转到链接列表 > 枚举法 > 前移法 > 转置法

可以看出，跳转链表的查询效率相比其他方法有着巨大的优势，其次是计数法，然后是前移法和转置法比字母顺序和卓越的普通法则更好。

并不是说查询效率越高越好。组织跳转链表的方法比其他方法要复杂得多。事实上，计数法在软件开发中经常被使用，而我们平时看到的“热点数据”本质上也是计数法。这些方法以简单有效的方式组织链表，并且经常被大量使用。

需要注意的是，上表仅包含数据比较，不包括执行这些方法所需的其他操作。如果包含此信息，这些方法之间的差异可能不会那么显着。

在这里总结一下，对于中等数据量，使用链表就足够了。随着数据量的增加和访问频率的增加，需要更复杂的方法和数据结构。

作者：BackSlash
链接：https://juejin.im/post/5c1a4272e51d4572c70b3cf5
来源：掘金
。商业转载请联系作者获得许可。非商业转载请注明来源。