algorithm - 为什么不使用指针数组来优化链表而使用跳过列表呢？

Question

最近在学习skip list，了解到它是为了加快链表的查找速度而设计的。但我想知道为什么不使用基于链表结构添加所有节点指针数组的数据结构？对于一个2^n节点列表，如果每一层我们有下一层指针数量的一半我们将添加2^n-1ponters，这几乎与添加每个节点的指针列表的数量相同，同时也是 O(1 ) 按索引访问。

一定有一些理由不实施我的想法，有人可以告诉我吗？

标签： algorithmdata-structureslinked-listlookupskip-lists

Answer 1

跳过列表提供O(log(n))读取、插入、更新和删除任何索引处元素的平均性能。

您的指针数组想法为相同的操作提供了O(1)、O(n)和O(1)的平均性能。O(n)诚然，在O(n)操作上有一个很好的常数，但它仍然是这样扩展的。

这两种数据结构都在实践中使用。它们只是用于不同的情况。