list with list at the bottom and lists , above it alsowe refer to as the height of skip list figure example of skip list storing entries for simplicitywe show only the keys of the entries intuitivelythe lists are set up so that + contains more or less every other entry in as we shall see in the details of the insertion methodthe entries in + are chosen at random from the entries in by picking each entry from to also be in + with probability / that isin essencewe "flip coinfor each entry in and place that entry in + if the coin comes up "heads thuswe expect to have about / entriess to have about / entriesandin generals to have about / entries in other wordswe expect the height of to be about logn the halving of the number of entries from one list to the next is not enforced as an explicit property of skip listshowever insteadrandomization is used using the position abstraction used for lists and treeswe view skip list as twodimensional collection of positions arranged horizontally into levels and vertically into towers each level is list and each tower contains positions storing the same entry across consecutive lists the positions in skip list can be traversed using the following operationsnext( )return the position following on the same level prev( )return the position preceding on the same level below( )return the position below in the same tower above( )return the position above in the same tower we conventionally assume that the above operations return null position if the position requested does not exist without going into the detailswe note that we can easily implement skip list by means of linked structure such that the above traversal methods each take ( timegiven skip-list position such linked