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 the map operation del [kwe begin by executing method skipsearch(kif the position stores an entry with key different from kwe raise keyerror 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 while removing levels of the towerwe reestablish links between the horizontal neighbors of each removed position the removal algorithm is illustrated in figure and detailed description of it is left as an exercise ( - as we show in the next subsectiondeletion operation in skip list with entries has (log nexpected running time before we give this analysishoweverthere are some minor improvements to the skip-list data structure we would like to discuss firstwe do not actually need to store references to values at the levels of the skip list above the bottom levelbecause all that is needed at these levels are references to keys in factwe can more efficiently represent tower as single objectstoring the key-value pairand maintaining previous references and next references if the tower reaches level secondfor the horizontal axesit is possible to keep the list singly linkedstoring only the next references we can perform insertions and removals in strictly top-downscan-forward fashion 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 figure removal of the entry with key from the skip list of figure the positions visited after the search for the position of holding the entry are highlighted the positions removed are drawn with dashed lines