Starting back in November 2003 I wrote a six-part article series for the C# section on MSDN Online titled, An Extensive Examination of Data Structures. This article series examined a number of the built-in data structures in the .NET Framework - arrays, the ArrayList, the Hashtable, the Queue, and the Stack - as well as the fundamentals and working examples of other common data structures - a binary search tree, a SkipList, a Graph, and a Set.
A few months ago I started retooling these articles for the .NET Framework version 2.0, and the six parts of the original article series have been updated and are now published on MSDN Online:
- Part 1: An Introduction to Data Sturctures - this first part starts by looking at the fundamentals of data structures and then examines two of the most commonly used data structures - the array and the List (the List being a new data structure in 2.0 that is, essentially, a Generics version of the ArrayList). This article series also includes a discussion on what Generics are and their benefits.
- New to the 2.0 Series - discussion on generics; discussion of the built-in List data structure.
- Part 2: The Queue, Stack, and Hashtable - this second part starts with an examination of the Queue and Stacks, two data structures that allow for a collection of items to be stored, but place limits on the order with which items are added and removed. The second half of the article looks at the Hashtable and Dictionary objects, which provide a way to store items using key/value semantics.
- New to the 2.0 Series - the generic versions of the Queue and Stack are used in the discussion; the Dictionary class, new to 2.0, is discussed.
- Part 3: Binary Trees and BSTs - the third part of this article series is the first that looks at data structures not found in the .NET Framework BCL. Trees are discussed, and implementations of a binary tree class and a binary search tree class are provided.
- New to the 2.0 Series - the binary tree and BST classes use Generics to allow for type-safe trees; used the yield syntax to provide iterators for the tree data.
- Part 4: Building a Better Binary Search Tree - BSTs have some shortcomings in that the order with which the data was inserted into the tree can greatly affect its running time. To combat this phenomenon, computer scientists have created various data structures to circumvent the problem. One technique is to have the trees automatically self-balance on insert. Another technique is the SkipList, which maintains a pseudo-tree with randomly assigned heights following a particular distribution that affords the optimal big-O running time.
- New to the 2.0 Series - the SkipList is now type-safe, thanks to Generics.
- Part 5: From Trees to Graphs - graphs are a more generalized version of a tree. In this fifth part of the article series, the concepts of graphs are discussed and a Graph class is introduced.
- New to the 2.0 Series - the Graph class uses Generics; the Graph class has been refactored into a better design.
- Part 6: Efficiently Representing Sets - a set is a collection of unordered items, and is a construct that's commonly used in mathematics. There are a number of real-world computer science problems that need to be able to efficiently work with sets, yet there is no support for sets in the .NET Framework BCL. This sixth and final part of the article series examines a set class and provides a discussion on a particular set scenario: maintaining a collection of disjoint sets.