SkipList

boolean insert(l,key,value) 
    register list l;
    register keyType key;
    register valueType value;
{
  register int k;
  // 使用了update数组
  node update[MaxNumberOfLevels];
  register node p,q;
  p = l->header;
  k = l->level;
  /*******************1步*********************/
  do {
        // 查找插入位置
        while (q = p->forward[k], q->key < key)
            p = q;
        
        // 设置update数组
        update[k] = p;
    } while(--k>=0);    // 对于每一层进行遍历
    
    // 这里已经查找到了合适的位置，并且update数组已经
    // 填充好了元素
   if (q->key == key)
   {
     q->value = value;
     return(false);
   };
    
   // 随机生成一个层数
   k = randomLevel();  
  if (k>l->level) 
  {
      // 如果新生成的层数比跳表的层数大的话
    // 增加整个跳表的层数
    k = ++l->level;
    // 在update数组中将新添加的层指向l->header
    update[k] = l->header;
  };
        
  /*******************2步*********************/
  // 生成层数个节点数目
  q = newNodeOfLevel(k);
  q->key = key;
  q->value = value;
      
  // 更新两个指针域
  do 
  {
        p = update[k];
        q->forward[k] = p->forward[k];
        p->forward[k] = q;
    } while(--k>=0);
    
    // 如果程序运行到这里，程序已经插入了该节点
  return(true);
}