An Extensive Examination of Data Structures - Part 2

My second part of a (proposed) six-part series on data structures is now live on MSDN - An Extensive Examination of Data Structures: Part 2.

In Part 1 of the article series, I discussed the importance of data structures and their impact on the performance of algorithms. The most basic and durable data structure - the array - was discussed, as well as the ArrayList. In Part 2, I examine the cousins of the ArrayList, the Stack and the Queue classes. There are many pretty pictures and diagrams illustrating how queues and stacks are implemented in the .NET Framework.

Part 2 also contains a look at hashtables and, specifically, the Hashtable class in the .NET Framework. If you're unfamiliar with hashtables, or if it's been a while since you've studied hash functions, collision resolution, and rehasing, you might find the article of particular interest. It was a blast to write.

Part 3 has already been written and will (hopefully) be on MSDN's site before too long. Part 3 looks at trees, and build a binary tree and binary search tree class. It ends with a discussion on the perils of binary trees (namely their unbalanced-ness), which provides a segue into Part 4, where we will briefly discuss self-balancing trees and then look at a randomized data structure - the Skip List - which exhibits the properties of a self-balancing binary tree.