An Extensive Examination of Data Structures, Part 4 Available

A mere 10 days ago An Extensive Examination of Data Structures: Part 3 was published on MSDN. Part 3 looked at trees, binary trees, and binary search trees (BSTs), and looked at implementing both binary tree and BST classes in C#.

Today, Part 4 of the article series was made available. Part 4 starts with a quick look at self-balancing BSTs, and then moves on to an in-depth examination of skip lists, which are a randomized, mutated linked list that provides log₂ n asymptotic time for searches, inserts, and deletes. The article includes complete, working C# source code for the skip list class as well. And, yes, Part 4 is another testament to my long-windedness, as it clocks in at 31 printed pages. (In my defense, it's hard to be terse when talking about this topic matter; also, there are many pretty pictures and diagrams which quickly inflate the page count.)

Enjoy!