Posted by Marta on March 27, 2021 Viewed 44185 times
In this article, you will learn the top 6 data structures that you should know if you want to become a software engineer and when to use which data structure.
Data Structures are fundamental in computer science. A program will use them to manipulate the data inputs received. Data refers to all kinds of information, number, string, or more complex pieces.
Data structures are the structures that you use to hold and organize your data so you can easily access it and manipulate it. Depending on how you manage your data, in other words, the data structure that you choose, your code could be faster or slower.
A good understanding of data structures and the performance implications for each is vital to write elegant code that runs quickly and smoothly.
Any engineer’s primary data structures should know Array, Tree, Stack and Queue, Graph, Hash Table, and Linked List.
Each of these structures has different names in different programming languages; however, the general concept is the same. Let’s talk about each of those briefly.
The array is the most basic data structure, merely a list of data elements that you can access by an index, which is the data’s position inside the array. Arrays are quite efficient at searching if the elements in the array are ordered. However, insertion and deletion are not as efficient since you have to shift all elements when you delete or insert an item.
Hashtable is a list of paired values, the first item in the pair is the key, and the second item is the value. With a hash table, you can access objects by the key, so this structure is high-speed for lookups. Hash tables are faster than the arrays for lookups. Also, quick for inserting and deleting objects; however, a hash table doesn’t maintain any order.
Stacks and queues are arrays; however, there are some restrictions on how to use them. These data structures are beneficial as a temporary container that allow you to handle the data in order. Let’s say you would like to store the charges in a restaurant. It would be vital that you processed the orders in the same order as received.
Stacks works like a pile of plates, only inserting elements at the end of a stack. You can only read and remove from the end of the stack. Also known as LIFO, Last In First Out.
Queues work similarly to a line of people in a movie theatre. The first one on the line is the first one that leaves the queue, and people can only join the queue at the end. In other words, you can only insert at the end, only read from the front, and only removed from the front.
Linked List is a node-based data structure. A linked list is similar to an array in the sense that it represents a list of elements. However, linked List manages memory differently. Unlike the arrays, the memory cells are not next to each other but spread across different cells. How can the computer find these cells? Every node stored the memory address of the next node in the linked list.
The benefit of Linked List over an array is that you can delete and insert elements from the beginning in one step.
The benefit of a Linked List over an array is that you can delete and insert elements from the beginning in one step.
Trees are also node-based structures, with every tree has a root node with 0 or more child nodes. A tree cannot contain cycles. There are several types of trees, and one of them is the Binary Tree. In binary Trees, each node has up to two nodes.
Another tree type is binary search trees, which means every node has up to two nodes, and its left descendants are less than or equal to the current node. And the right descendants are greater than the current node. This rule applies to all nodes. The benefit that a tree has over a hash table is besides doing quick search, insertion, and deletion, it can also maintain order.
A graph is a collection of nodes with edges in between. A tree is a graph with some restrictions. In other words, it is a connected graph without cycles. A graph could be directed, which means the nodes are connected in one direction, like a one-way street. You can also have an undirected graph, which means nodes are connected in both directions.
How do you know when to use which data structure in a real case scenario?
You will need to pick a data structure that helps you solve your problem, minimizing the code you need to write. And also, you want to make sure your code is efficient. That means it will complete the task quickly, and it will process a large amount of data in a reasonable time. In technical terms, you will say that the code scale well as the load increase.
Here is a diagram that helps to choose the correct data structure for your coding problems quickly. It shows the key factors you need to consider when selecting a data structure.
The first factor is the amount of data you would like to store. If the amount of data is predictable? It would help if you also considered what you are going to use more often, searching or insertions? or maybe you need both. And finally, if you need your data to be distributed in a specific order.
Check out the following video if you like to learn about the most popular data structures in Python and how to use them:
Let’s put the diagram into practice. Let’s say we would like to find the maximum difference between elements in an array.
One way to solve this problem will be to find the minimum element, the maximum element and see the difference between the two. We could do this easily if the numbers in the array are ordered. Let’s use our diagram to pick the appropriate structure.
First, we will consider the amount of data. For this example, we will assume the array won’t be more extensive than 100 elements to have a small amount of data.
Next, is the amount of data predictable? The answer is yes since we know the size of the array beforehand. And next question, is search speed more important than insertion speed? Since we need to know the maximum and minimum, we will be using searching more often. Therefore searching is more important. So the ordered array will be the right data structure for this problem.
To summarize, we have seen the most frequently used 6 data structures and when to use each of them. I hope you enjoyed the article, and thank you so much for reading and supporting this blog. Happy Coding!
If you like the article and you would like to be notified when I publish more articles feel free to follow, give it a like or subscribe. 🙂
Steady pace book with lots of worked examples. Starting with the basics, and moving to projects, data visualisation, and web applications
Unique lay-out and teaching programming style helping new concepts stick in your memory
Great guide for those who want to improve their skills when writing python code. Easy to understand. Many practical examples
Perfect Boook for anyone who has an alright knowledge of Java and wants to take it to the next level.
Excellent read for anyone who already know how to program and want to learn Best Practices
Perfect book for anyone transitioning into the mid/mid-senior developer level
Great book and probably the best way to practice for interview. Some really good information on how to perform an interview. Code Example in Java