chap patterns of algorithms node to gain an additional two (nullpointers at this pointthe new node is added to the front of the listas shown in figure (dfinallyinsert node with value at level this timelet us take close look at what array update is used for it stores the farthest node reached at each level during the search for the proper location of the new node the search process begins in the header node at level and proceeds to the node storing value because forward[ for this node is nullwe cannot go further at this level thusupdate[ stores pointer to the node with value likewisewe cannot proceed at level so update[ also stores pointer to the node with value at level we proceed to the node storing value this is as far as we can go at level so update[ stores pointer to the node with value finallyat level we end up at the node with value at this pointwe can add in the new node with value for each value ithe new node' forward[ipointer is set to be update[ ]->forward[ ]and the nodes stored in update[ifor indices through have their forward[ipointers changed to point to the new node this "splicesthe new node into the skip list at all levels the remove function is left as an exercise it is similar to inserting in that the update array is built as part of searching for the record to be deletedthen those nodes specified by the update array have their forward pointers adjusted to point around the node being deleted newly inserted node could have high level generated by randomlevelor low level it is possible that many nodes in the skip list could have many pointersleading to unnecessary insert cost and yielding poor ( th( )performance during searchbecause not many nodes will be skipped converselytoo many nodes could have low level in the worst caseall nodes could be at level equivalent to regular linked list if sosearch will again require th(ntime howeverthe probability that performance will be poor is quite low there is only once chance in that ten nodes in row will be at level the motto of probabilistic data structures such as the skip list is "don' worrybe happy we simply accept the results of randomlevel and expect that probability will eventually work in our favor the advantage of this approach is that the algorithms are simplewhile requiring only th(log ntime for all operations in the average case in practicethe skip list will probably have better performance than bst the bst can have bad performance caused by the order in which data are inserted for exampleif nodes are inserted into bst in ascending order of their key valuethen the bst will look like linked list with the deepest node at depth the skip list' performance does not depend on the order in which values are inserted into the list as the number of nodes in the skip list increasesthe probability of