Skip Lists: A Probabilistic Alternative to Balanced Trees[PDF]. Saw a link to the original skip list paper. I'm not sure whether I've read that one or not. Anyway, if you want to understand concurrency, and the "impending multicore future", skip lists are an interesting thing to consider. Note, the rest of this post assumes a basic understanding of ( Read more... )

Sometime, early on in a computer science education, people take a course in data structures and algorithms, and learn about the wonders of linked lists, write one, and then, learn that it is efficiently(hahaha! oh wait... not to the punch line yet...) implemented in the standard library of their favorite language(for some value of favorite not ( Read more... )