chap patterns of algorithms skip alternating nodesas shown in figure (bdefine nodes with only single pointer as level skip list nodeswhile nodes with two pointers are level skip list nodes to searchfollow the level pointers until value greater than the search key has been foundthen revert to level pointer to travel one more node if necessary this effectively cuts the work in half we can continue adding pointers to selected nodes in this way -give third pointer to every fourth nodegive fourth pointer to every eighth nodeand so on -until we reach the ultimate of log pointers in the first and middle nodes for list of nodes as illustrated in figure (cto searchstart with the bottom row of pointersgoing as far as possible and skipping many nodes at time thenshift up to shorter and shorter steps as required with this arrangementthe worst-case number of accesses is th(log nto implement skip listswe store with each skip list node an array named forward that stores the pointers as shown in figure (cposition forward[ stores level pointerforward[ stores level pointerand so on the skip list class definition includes data member level that stores the highest level for any node currently in the skip list the skip list is assumed to store header node named head with level pointers the find function is shown in figure searching for node with value in the skip list of figure (cbegins at the header node follow the header node' pointer at levelwhich in this example is level this points to the node with value because is less than we next try the pointer from forward[ of ' node to reach because is greater than we cannot go forward but must instead decrement the current level counter to we next try to follow forward[ of to reach the node with value because is smaller than we follow ' forward[ pointer to because is too bigfollow ' level pointer to because is not less than we fall out of the while loop and move one step forward to the node with value the ideal skip list of figure (chas been organized so that (if the first and last nodes are not countedhalf of the nodes have only one pointerone quarter have twoone eighth have threeand so on the distances are equally spacedin effect this is "perfectly balancedskip list maintaining such balance would be expensive during the normal process of insertions and deletions the key to skip lists is that we do not worry about any of this whenever inserting nodewe assign it level ( some number of pointersthe assignment is randomusing geometric distribution yielding probability that the node will have one pointera probability that it will have twoand so on the following function determines the level based on such distribution