3 ms·
Previously: http://news.ycombinator.com/item?id=229668 http://news.ycombinator.com/item?id=229668 First things first, read Pugh's original paper (ftp://ftp.cs.
by silentbicycle 17y ago
Previously: http://news.ycombinator.com/item?id=229668 http://news.ycombinator.com/item?id=229668
First things first, read Pugh's original paper (ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf). That would be the better link, but HN doesn't let you submit links to FTP sites.
Also: A lecture I watched compared skip lists to subway routes with multiple (randomly routed) express lines. That's one of the best metaphors for a data structure I've ever heard.
- jaydub 17y agoA lecture I watched compared skip lists to subway routes with multiple (randomly routed) express lines. I had Prof. Pugh for an honors CS course @ UMD and that's how he first described it to the class.