Remaining data structures

If the main data structures (at least based on my experience) are Lists, Arrays and Maps, the remaining important ones are:

• Stack and Queue

• Tree

I covered Lists and Arrays here, and Maps here. Now let’s talk about the remaining ones. Oh, a disclaimer that these are not all the data structures that exist. We have a bunch of others, but I’ve almost never used them while working in a real application, so I won’t write about them.

Are Stacks and Queues the same thing? Why are they together?

Stacks and Queues are similar in some aspects. That’s why I like to talk about them at the same time. Both are data structures that store and retrieve elements in a certain order. A Queue will retrieve the oldest element first, just like a real life queue… The first person to arrive at the movies queue will be the first person to enter the theater, unless he gets cut out. Same thing with data structures that share the name Queue. There’s an official way to say this, which is First In First Out (FIFO), but honestly, I prefer thinking of this as a real life queue, then I can easily understand that the first one to arrive is the first one to be chosen.

Stacks on the other hand, I see as a stack of paper. I put one paper, then another above it, then another above it. When I want to take a paper, I just take the one at the top which just happens to be the last one to arrive at the stack. Again, officially, people call it Last In First Out (LIFO) but I don’t care about the naming. If you think about a stack of paper, it’s pretty clear that you’ll take the most recent paper on top, unless you are a degenerate that tumbles everything to pick something in the middle to prove a point.

Cool, but that sounds pretty simple. Is there something else?

I mean, of course you can complicate issues a lot if you want, but I like to keep it simple. Stacks are structures where you retrieve the element that has just arrived. Queues are structures where you retrieve the element that arrived ages ago and is waiting in line. Both structures are useful for some real life scenarios. For example, if you have an application that sells sports tickets for a huge event where a lot of people want to go, but only a few spots are available, you’ll need to decide who gets the tickets. One way to do it is to use a Queue to store the users that arrive first and give them the chance to buy first. On the other hand, if you are developing a game where the user can always undo his previous actions, you might want to keep adding the actions in a Stack, and when the user decides to undo his last action, you just need to get the element from the Stack to know what his last action was.

That is it for the main purposes of both Stacks and Queues. It’s worth mentioning that it can indeed become a little more complex, like, for example, when we decide to evaluate a queue by priority of elements instead of order of insertion. Concurrency needs to be taken into account as well if we are dealing with a shared Queue/Stack in a multi-threaded environment. And of course, let’s never forget about handling edge cases, like when the structure is empty, and we try to fetch an element anyway.

What about the trees?

A nice way to think about tree is to visualize it in a paper. Like in this image:

We have a lot of different trees type, like Binary Tree, AVL Tree, Red-Black Tree, B- Tree, B+ Tree and a lot of others. I’d say the main one is the Binary Tree. The Binary Tree is this structure where each node has at most 2 children. Although the concept is pretty simple, it’s very powerful. If you create a rule that each node can only have smaller values to the left and higher values to the right for example, you are able to perform a search operation quite quickly (this is called a Binary Search Tree by the way).

There are those developers that think it is important to know how to implement a Binary Search Tree from the top of your head, but I’m more on the pragmatic side that it’s not really useful. You can always find online a bunch of great implementations which will make your life easier. The main thing for me is to understand the underling structure so you know what are the advantages of using it once a situation appears to you.

What about other data structures?

I’ll end this with the final honor mention to data structures that are important to know they exist, but you’ll likely not work with them on a regular basis:

• Graphs - a set of nodes and links, which you can also call vertices and edges.

• Matrix - like an array, but in two dimensions.

With arrays, lists and maps, we can do almost anything efficiently. Stacks, queues and trees can also come in handy at times. Unique problems may require the usage of graphs or matrixes. With these data structures as a basis you can solve almost any problem :)