最近,我正在学习跳过列表,并且我了解到它是为加快链接列表的查找而设计的。但是我想知道为什么不使用基于链表的结构添加所有节点的指针数组的数据结构?对于2^n
节点列表,如果每个级别我们都拥有较低级别的指针数量的一半,那么我们将添加2^n-1
ponter,几乎等于添加每个节点的指针列表的数量,并且同时它是O(1 )以按索引访问。
一定有一些原因不能实现我的想法,有人可以告诉我吗?
跳过列表提供O(log(n))
了在任何索引处读取,插入,更新和删除元素的平均性能。
您的指针数组的想法提供的平均表现O(1)
,O(n)
,O(1)
以及O(n)
用于同样的操作。可以O(n)
肯定的是,在操作上有一个很好的常数,但这仍然是它的扩展方式。
两种数据结构都在实践中使用。它们仅用于不同的情况。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句