skipsearchin code fragment given this methodit is now easy to implement the operation find(kwe simply perform skipsearch(kand test whether or not key(pk if these two keys are equalwe return potherwisewe return null code fragment search in skip list variable holds the start position of as it turns outthe expected running time of algorithm skipsearch on skip list with entries is (lognwe postpone the justification of this facthoweveruntil after we discuss the implementation of the update methods for skip lists insertion in skip list the insertion algorithm for skip lists uses randomization to decide the height of the tower for the new entry we begin the insertion of new entry ( ,vby performing skipsearch(koperation this gives us the position of the bottom-level entry with the largest key less than or equal to (note that may hold the special entry with key -we then insert (kvimmediately after position after inserting the new entry at the bottom levelwe "flipa coin if the flip comes up tailsthen we stop here else (the flip comes up heads)we backtrack to the previous (next higherlevel and insert ( ,vin this level at the appropriate position we again flip coinif it comes up headswe go to the next higher level and repeat thuswe continue to insert the new entry ( ,vin lists until we finally get flip that comes up tails we link together all the references to the new entry (kvcreated in this process to create the tower for the new entry coin flip can be simulated with java' built-in pseudo-random number generator java util random by calling nextint( )which returns of each with probability / we give the insertion algorithm for skip list in code fragment and we illustrate it in figure the algorithm uses method insertafterabove(