为什么不使用指针数组来优化链表而是使用跳表？
Why not use an array of pointers to optimize linked list but use skip list?
最近在学习跳表，了解到它是为了加快链表的查找速度而设计的。但我想知道为什么不使用基于链表结构添加所有节点指针数组的数据结构？对于2^n个节点的列表，如果每层我们有下层指针数量的一半，我们将添加2^n-1个指针，这与添加每个节点的指针列表的数量几乎相同，同时按索引访问是O(1)。
肯定有一些原因没有实现我的想法，谁能告诉我？
跳过列表提供 O(log(n)) 的平均性能来读取、插入、更新和删除任何索引处的元素。
您的指针数组想法为相同的操作提供了 O(1)、O(n)、O(1) 和 O(n) 的平均性能。诚然，在 O(n) 操作上有一个很好的常数，但这仍然是它的扩展方式。
这两种数据结构在实践中都有使用。它们只是用于不同的情况。
最近在学习跳表，了解到它是为了加快链表的查找速度而设计的。但我想知道为什么不使用基于链表结构添加所有节点指针数组的数据结构？对于2^n个节点的列表，如果每层我们有下层指针数量的一半，我们将添加2^n-1个指针，这与添加每个节点的指针列表的数量几乎相同，同时按索引访问是O(1)。
肯定有一些原因没有实现我的想法，谁能告诉我？
跳过列表提供 O(log(n)) 的平均性能来读取、插入、更新和删除任何索引处的元素。
您的指针数组想法为相同的操作提供了 O(1)、O(n)、O(1) 和 O(n) 的平均性能。诚然，在 O(n) 操作上有一个很好的常数，但这仍然是它的扩展方式。
这两种数据结构在实践中都有使用。它们只是用于不同的情况。