skip lists an interesting data structure for realizing the sorted map adt is the skip list in section we saw that sorted array will allow (log )-time searches via the binary search algorithm unfortunatelyupdate operations on sorted array have (nworst-case running time because of the need to shift elements in we demonstrated that linked lists support very efficient update operationsas long as the position within the list is identified unfortunatelywe cannot perform fast searches on standard linked listfor examplethe binary search algorithm requires an efficient means for direct accessing an element of sequence by index skip lists provide clever compromise to efficiently support search and update operations skip list for map consists of series of lists { sh each list si stores subset of the items of sorted by increasing keysplus items with two sentinel keys denoted and +where is smaller than every possible key that can be inserted in and is larger than every possible key that can be inserted in in additionthe lists in satisfy the followinglist contains every item of the map (plus sentinels and +for list si contains (in addition to and + randomly generated subset of the items in list si- list sh contains only and an example of skip list is shown in figure it is customary to visualize skip list with list at the bottom and lists sh above it alsowe refer to as the height of skip list intuitivelythe lists are set up so that si+ contains more or less alternate items of si as we shall see in the details of the insertion methodthe items in si+ are chosen at random from the items in si by picking each item from si to also be in si+ with probability / that isin essencewe "flip coinfor each item in si figure example of skip list storing items for simplicitywe show only the itemskeysnot their associated values