3.12.2 Skip Lists: Experimental Analysis

Implement skip list data structure. Analyze the efficiency of search, insert, and delete operations on randomly generated inputs. Carefully take into account all the tradeoffs involved in designing and implementing skip lists. Validate the experimental results with those given in the article by William Pugh (Skip Lists: A probabilistic alternative to balanced trees. Communications of the ACM, Volume 33, Number 6, pp. 668-676, 1990). Design and carry out experiments to compare the performance of skip lists with that of hash tables.