Data structures for Beginners

April 6, 2023

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?

Figure 1: Legos — unorganized v/s organized
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.

Map

Let’s say you visit a grocery store to buy bread. Which store would you prefer?

Figure 2: Grocery store — unlabelled v/s labeled aisles

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 labeling data is called a map. By labeling data, we can look up the labels and find answers instantaneously.

Trees

Let’s say you ask a voice assistant, “Should I go on a hike today?”

Figure 3.1: Voice assistant deciding on — Should you go on a hike?

To answer this question, a series of decisions are made on whether the weather is suitable or not.

Figure 3.2: Tree-like structure that stores questions

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.

Figure 3.1
Figure 3.2

Graph

Let’s say you receive a friend request from Bob on Facebook. Before accepting, you want to find a mutual friend.

Figure 4.1: Friend request with an unknown 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?

Figure 4.2: Ways to store friendship data

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.

Figure 4.1:
Figure 4.2

Stack

Let’s say you press the back button on your browser. How do we store the last visited website?

Figure 5.1: Last visited websites in a browser

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.

Figure 5.2: Last visited website and last added chair are accessible

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.

Figure 5.1:
Figure 5.2

Queue

Let’s say you try to reserve an Uber during a busy time.

Figure 6.1: Reserving an Uber car ride

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.

Figure 6.2: Minions waiting in a queue for their turn

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.

Figure 6.1:
Figure 6.2

Conclusion

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.

Continue learning

To learn more about data structures and other fundamentals, click here to book a free session or webinar with Techmentry.