Note: Check out the entire supplemental source code for this blog series.
Use the Right Tool for the Job
Every developer is familiar with data structures at some level. There are stacks, queues, and binary trees. Oh, and don’t forget linked lists, the data structure that is asked about in almost every coding interview. And then there are the more advanced structures. You know, the ones that are named after colors or letters like B trees, R trees, and red-black trees. We all know that they are important and that most job interviews will likely ask at least a few data structure questions. But what is the point of all of these different data structures? Which ones are important and which ones can you forget about? And most importantly, which one should you use?
As you can probably guess, the answer is “it depends.” Often times we are introduced to data structures one at a time as we need them and it’s easy to lose sight of what’s really important.
Data structures like the ones we will explore are often called sets. If the data structure’s capacity can expand automatically as new elements are added, then they are often referred to as dynamic sets. As we look at many different data structures, it will become clear that they all essentially do the same thing. Each of the primary data structures is merely a way to store, search, and manipulate data. In fact, most everything that the data structures can do can be boiled down into just six simple operations.
- Insert: insert an element
- Delete: delete an element
- Search: find an element with a given key
- Minimum: find the element with the maximum key
- Maximum: find the element with the minimum key
- Iteration: iterate through the elements
To illustrate this point and prove that most common data structures are essentially just dynamic sets let’s create an interface IDynamicSet<T>. Throughout this blog series, we will implement each data structure as a concrete implementation of this interface.
Note: Technically, we’ll be implementing multisets, instead of sets due to the fact that multiple elements with the same value can be added. We could easily change this implementation if we wanted, but removing this restriction allows the code to be simpler and is just fine for our purposes.
What is unique about different data structures is that they are all optimized for different scenarios. When you are able to recognize the scenario you’re trying to solve and understand the optimizations behind each data structure, you’ll be able to determine the best data structure for your situation.
In the following blog posts, I will attempt to look at each of the primary data structures and try to present them as a cohesive picture. We will examine each one in detail as we implement it as a concrete implementation of IDynamicSet<T>. Finally, we will run the data structures through some common scenarios to see how they compare. If you follow me through this journey, you will know how to pick the best data structure for the job and even how to use the underlying principles to create entirely new, custom data structures to solve more difficult problems.