next up previous
Next: 2.7.4 Buddy Systems of Memory Allocation Up: 2.7 Programming Assignments Previous: 2.7.2 Polynomial Arithmetic

2.7.3 Skip Lists

A skip list is an efficient linked list-based data structure that attempts to implement binary search on linked lists. Read the following paper: William Pugh. Skip Lists: A probabilistic alternative to balanced trees. Communications of the ACM, Volume 33, Number 6, pp. 668-676, 1990. Also read the section on Skip Lists in Chapter 4 of this lecture notes. Develop programs to implement search, insert, and delete operations in skip lists.