跳转表用两种不同的实现方式，为什么效率差别大？

Question

题目更新得更详细了，请留意：
在书上看到的跳转表，实现的方式是每层都用一个特殊的List，它的节点连接上下左右：

 template <typename T> struct QuadlistNode {
   T data; 
   QuadlistNode<T>* pred;  QuadlistNode<T>* succ; //前驱、后继
   QuadlistNode<T>* above; QuadlistNode<T>* below; //上邻、下邻
};
template <typename T> class Quadlist { //Quadlist模板类
private:
   int _size; QuadlistNode<T>* header; QuadlistNode<T>* trailer; //规模、头哨兵、尾哨兵
}

最后再用一个普通的List存储每一层的特殊List：

 List<Quadlist<T>*>

。
我一开始看到这里感觉空间效率太低，毕竟每层的节点都有自己独自的data，所以自己实现时，节点使用vector储存不同层的前后驱：

 template <typename T>
struct SkiplistNode{
    T _data;
    Vector<SkipListNode*> succ;
    Vector<SkipListNode*> prev;
};

测试时插入、删除、搜索操作合计一百万次，最后层次达到16层，结果却是书上的时间效率比我的快一倍。。。请问为什么会这样呢？谢谢！

Answer 1

它的实现都是针对跳转表所做的元素插入，查找，删除。链表效率更高。而你的vector就没有这么快。