为什么插入跳表的时间复杂度是线性的?

我已经实现了整数的跳跃表。当测试方法插入时，我在计数器j的for循环中插入从1到1000000的自然数。我也使用秒表。附录:在实际程序中，值是双精度的，因为我对值使用了哨兵翻倍。正无穷大，负无穷大。(但这不应该是问题所在)伪代码:

MyList = new SkipList();
stopwatch.start();    
t1 = stopwatch.Elapsed.TotalMilliseconds;
for(int j = 0; j<1000000; j++){
    steps = MyList.insert(j);
    if(j%500==0){
        t2= stopwatch.Elapsed.TotalMilliseconds -t1;
        write j,t2 in a file1;
        write j,steps in a file2;
        t1 = t2;
    }
}

当我制作图形时间/节点数时，它是线性的，但图形步骤/节点如预期的那样是对数的。(steps是insert方法的循环次数(~操作)。

方法insert创建额外的节点并设置一些指针。节点的实现方式如下:

class Node 
{
    public Node right;//his right neighbour - maybe "null"
    public Node down;//his bottom neighbour -maybe null
    public int? value;//value
    public int depth;//level where node is present: 0, 1, 2 ...
    public Node(int i,Node rightt,Node downn,int depthh) {
        //constructor for node with two neighbours.
        value = i;
        right = rightt;
        down = downn;
        depth = depthh;
    }
   //there are some other contructors (for null Node etc.)
}
class SkipList
{
    public Node end;//upper right node
    public Node start;//upper left node
    public int depth;//depth of SkipList
    //there are left (-inf) and right sentinels (inf) in the SkipList.
}

跳跃表由节点组成。

Insert在类SkipList中定义，工作方式如下:

public int Insert(int value2, int depth2)
    {
        //returns number of steps
        //depth2 is calculated like (int)(-Math.Log(0<=random double<1 ,2))
        //and works as expected - probability P(depth = k) = Math.Pow(0.5,k)
        //lsit of nodes, which will get a new right neighbour
        List<Node> list = new List<Node>();
        Node nod = start;
        int steps = 0;
        while (true) {
            if (nod.right.value >= value2)
            {
                //must be added to our list
                lsit.Add(nod);
                if (nod.down != null)
                    nod = nod.down;
                else
                    break;
            }
            else {
                nod = nod.right;
            }
            steps++;
        }
        //depth (of skipList) is maybe < depth2, so we must create
        //k = 2*(depth2-depth) new edge nodes and fix right pointers of left sentinels
        List<Node> newnodes = new List<Node>();
        for (int jj = 0; jj < depth2 - depth;jj++ )
        {
            steps++;
            //new sentinels
            Node end2 = new Node(double.PositiveInfinity, end,depth+jj+1);
            Node start2 = new Vozlisce(double.NegativeInfinity, end2,
                                                               start,depth+jj+1);
            start = start2;
            end = end2;
            newnodes.Add(start2);
        }
        //fix right pointers of nodes in the List list (from the beginning)
        Node x = new Node(value,list[list.Count-1].right,0);
        list[list.Count-1].right=x;
        int j =1;
        while(j<=Math.Min(depth2,depth)){
            steps++;
            //create new nodes with value value
            x = new Node(value,lsit[list.Count -(j+1)].right,x,j);
            list[list.Count-(j+1)].right = x;
            j++;
        }
        //if there are some new edge sentinels, we must fix their right neighbours
        // add the last depth2-depth nodes
        for(int tj=0;tj<depth2-depth;tj++){
            steps++;
            x = new Node(value,newnodes[tj].right,x,depth+tj+1);
            newnodes[tj].right = x;
        }
         depth = Math.Max(depth, depth2);           
         return steps;
    }

我还实现了一个版本的跳跃表，其中节点是块，并有n = node.depth右邻居，存储在数组中，但图时间/num。的节点仍然是线性的(和步骤/num)。

10 : 1010
 6 : 0110
---------
 ^ : 1100 = 12