chap patterns of algorithms /*insert record into the skiplist *public void insert(key ke newvalueint newlevel randomlevel()/new node' level if (newlevel level/if new node is deeper adjusthead(newlevel)/adjust the header /track end of level skipnode[update (skipnode[])new skipnode[level+ ]skipnode head/start at header node for (int =leveli>= --/find insert position while(( forward[ !null&( compareto( forward[ikey() ) forward[ ]update[ix/track end at level new skipnode(knewvaluenewlevel)for (int = <=newleveli++/splice into list forward[iupdate[iforward[ ]/who points to update[iforward[ix/who points to size++/increment dictionary size figure implementation for the skip list insert function /*pick level using exponential distribution *int randomlevel(int levfor (lev= dsutil random( = lev++)/do nothing return levonce the proper level for the node has been determinedthe next step is to find where the node should be inserted and link it in as appropriate at all of its levels figure shows an implementation for inserting new value into the skip list figure illustrates the skip list insertion process in this examplewe begin by inserting node with value into an empty skip list assume that randomlevel returns value of ( the node is at level with pointersbecause the empty skip list has no nodesthe level of the list (and thus the level of the header nodemust be set to the new node is insertedyielding the skip list of figure (anextinsert the value assume this time that randomlevel returns the search process goes to the node with value and the new node is inserted afteras shown in figure (bthe third node inserted has value and again assume that randomlevel returns this yields the skip list of figure the fourth node inserted has value and assume that randomlevel returns this means that the level of the skip list must risecausing the header