search and update operations in skip list the skip-list structure affords simple map search and update algorithms in factall of the skip-list search and update algorithms are based on an elegant skipsearch method that takes key and finds the position of the item in list that has the largest key less than or equal to (which is possibly -searching in skip list suppose we are given search key we begin the skipsearch method by setting position variable to the topmostleft position in the skip list scalled the start position of that isthe start position is the position of sh storing the special entry with key we then perform the following steps (see figure )where key(pdenotes the key of the item at position if below(pis nonethen the search terminates--we are at the bottom and have located the item in with the largest key less than or equal to the search key otherwisewe drop down to the next lower level in the present tower by setting below( starting at position pwe move forward until it is at the rightmost position on the present level such that key( < we call this the scan forward step note that such position always existssince each level contains the keys and it may be that remains where it started after we perform such forward scan for this level return to step figure example of search in skip list the positions examined when searching for key are highlighted we give pseudo-code description of the skip-list search algorithmskipsearchin code fragment given this methodthe map operation [kis performed by computing skipsearch(kand testing whether or not key(pk if these two keys are equalwe return the associated valueotherwisewe raise keyerror