There are many data structure across the whole of computer science. As a developer, you only use a small handful for the majority of your work. A large handful are important enough to know about off the top of your head. The majority can be considered exotic and can be looked up when you need to.
This is a list trying to answer the question “What Data Structures Should You Know?” by bucketing them into roughly the categories above.
This is a general recommendation based on decades of engineering experience across a wide array of fields and industries, from semi-conductor to healthcare. Your industry will have different priorities. Graphs and ZDDs/BDDs become more important in if you work with maps, geo-coordinates, etc.
In some languages, certain data structures are more important. If your language’s native, internal implementation of an “array” is a linked list, you better know that linked lists take a relatively long time to count the elements in it.
As a hiring manager, Senior Engineers typically shift up a level. The Must Knows become “Know it like I know how to spell my name” and the Should Knows become Must knows. For Hobbyists or Early Career Engineers the should knows tend to be more of a Lookup When You Need It. The Must Knows are always Must Knows. At any level, there is nothing that will disqualify you faster in a technical interview than using an array when you should be using a map.
This list is primarily geared towards getting day to day work done as an average engineer. It is unfortunately not sufficient for interviewing. Interviews are broken. If a company asks you to implement a red-black tree from scratch, I hope you are interviewing to work on complier or database internals or something, because that is rarely a useful question to ask.
A basic understanding of BigO notation is an important prerequisite as well. Here’s a gentle video intro on the concept and an excellent short blog post.
Lastly, when we say “know” we don’t mean you need to know how to implement them from scratch. 1
Here are the general guidelines (barring any job/industry specific requirements):
“Know” means you should understand how they are used, what kind of problems they solve and have a rough sense of big O for time/memory/space for typical activities such as insertion, removal, retreival, search, etc.
“Be Familiar With” is having an understanding of the basic usage and properties of a given data structure. For example, Being Familiar With a stack mean a simple understanding of how a it works (LIFO array) and that push and pop are O(1) operations but search is O(n).
Most of the items in the “Be Familiar With” category aren’t that common with respect to day to day usage, but are fairly important when you need them. As a homeowner, you may not use a vice or clamp that often, but there aren’t a lot of good options if you really need one. It’s also likely that they are used under the hood of much of the tools and libraries you do use often.2
You may have noticed that the Caveat section is longer than the list itself. It’s quite subjective, but I’ve tried to focus on doing day to day engineering work. Feel free to hit me up on twitter @amattn if you have any feedback or suggestions.
Footnotes: