Data structures let us organize data, so that we can find answers efficiently.
For example, say you had to find all legos of the color red in Figure 1. Which case would be faster?
The second case is faster because the legos are organized. Similarly, in computer science, data structures let us organize data for quick retrieval.
Let us look at some data structures and their use cases.
Let’s say you visit a grocery store to buy bread. Which store would you prefer?
Walmart is a better choice because the food is categorized. You can jump to the correct aisle to find bread. All breads — sourdough, baguettes, buns and bagels — are available on the same aisle. Instead of going through the entire store, you just narrowed your search and saved time.
In computer science, this method of categorizing and labelling data is called a map. By labelling data, we can look up the labels and find answers instantaneously.
Let’s say you ask a voice assistant, “Should I go on a hike today?”
To answer this question, a series of decisions are made on whether the weather is suitable or not.
In Figure 3.2, let’s say the weather is sunny. If so, we don’t need to look at the right side of the tree which deals with rainy weather.
By storing data in a “tree” format, we chose one path and ignored the other path or “branch”. By ignoring some paths, we reached a decision faster.
In computer science, a tree data structure lets us to ignore certain paths so that we can answer quickly.
Let’s say you receive a friend request from Bob on Facebook. Before accepting, you want to find the mutual friend.
Since billions of users exist on Facebook, how can we save friendship data so that the mutual friend can be found quickly?
There are two ways to store users and their relationships, as shown in Figure 4.2. Which would be more efficient, to find friends common between Bob and you?
The second option is a faster way to find that Carol is the mutual friend. We did not need to look at other people like Alice and Ted to find Carol.
This data structure is known as a Graph — it is great for visualizing relationships between users.
Let’s say you press the back button on your browser. How do we store the last visited website?
Figure 5.1 shows that websites are stored in order of visit time— Amazon was the last visited website, followed by Instagram, Youtube and Facebook.
When we click the back button, these websites are navigated to in the same order.
A good analogy is a set of chairs stacked on each other, as shown in Figure 5.2. Only the green chair at the top is useable. It must be removed before the chairs below it can be used. This structure lets us find the last chair added quickly — we need not hunt through all the chairs.
Similarly, Amazon is the last visited website at the top of our “stack” structure. It must be removed before we can access other websites.
In computer science, this “stack” structure finds the “last seen” data quickly.
Let’s say you try to reserve an Uber during a busy time.
Since there is high demand, many passengers are waiting for a car to be assigned. Who gets the next ride?
When you press the reserve button, you are added to the end of a queue. Customers ahead of you are served first so that the wait time remains fair. Everyone who reserved a ride before you gets a car before you do — in a first come, first served fashion.
A “queue” is a data structure that processes data in the order of arrival. The data waiting for the longest duration of time is served first.
We saw examples of some famous data structures and their applications.
In a real world problem, millions of bytes of data need to be analyzed within seconds. Hence, we use data structures to juggle between space constraints (storage cost) and time constraints (find answers quickly).
A carefully chosen data structure leads to an efficient solution.
To learn more about data structures and other fundamentals, click here to book a free session or webinar with Agneez.