positions preceding them are flagged removal in skip list like the search and insertion algorithmsthe removal algorithm for skip list is quite simple in factit is even easier than the insertion algorithm that isto perform remove(koperationwe begin by executing method skipsearch(kif the position stores an entry with key different from kwe return null otherwisewe remove and all the positions above pwhich are easily accessed by using above operations to climb up the tower of this entry in starting at position the removal algorithm is illustrated in figure and detailed description of it is left as an exercise ( - as we show in the next subsectionoperation remove in skip list with entries has (lognexpected running time before we give this analysishoweverthere are some minor improvements to the skip list data structure we would like to discuss firstwe don' actually need to store references to entries at the levels of the skip list above the bottom levelbecause all that is needed at these levels are references to keys secondwe don' actually need the above method in factwe don' need the prev method either we can perform entry insertion and removal in strictly top-downscan-forward fashionthus saving space for "upand "prevreferences we explore the details of this optimization in exercise - neither of these optimizations improve the asymptotic performance of skip lists by more than constant factorbut these improvements canneverthelessbe meaningful in practice in factexperimental evidence suggests that optimized skip lists are faster in practice than avl trees and other balanced search treeswhich are discussed in the expected running time of the removal algorithm is (logn)which we show in section figure removal of the entry with key from the skip list of figure the positions visited after