Data structures

Let's face it: you can't ignore algorithms if you're hoping to write an innovative and efficient program. However, algorithms are not the only thing you need: besides the question of processing, there's also the question of data storage, including how much space your program takes. Here data structures come in handy, so let's learn some essential information about them.

What data structures are

Data structures are a way of organizing data and providing convenient access to it. Rather abstract? Okay, let's look at a more specific example.

Imagine that we have a variety of soda cans and bottles that we would like to organize. We could put them all in a random bag or build a can tower, but this way, it won't be easy to fish out a specific type of soda or even count the items. After a bit of pondering, we decided to put them in a vending machine. This vending machine will be a structure of beverages: it has a specific order, and you can easily observe the tins and bottles, count them, access one or another, as well as understand the capacity of the machine and perform many other operations.

Now let's return to the formal definition and try again: the term data structure refers to a collection of elements containing data, as well as relationships between them and data operations. As a rule, data structures have two types of operations: internal, supporting data organization, and external, available to users for storing, retrieving, or modifying data. There are several common data structures: an array, a linked list, a hash table, and a whole variety of trees (binary search tree, heap, red-black tree, B-tree, etc.). You can read about all of them in detail on our platform, but don't hurry: let's get to know the basics first.

The role of data structures

Now, why is it so important to have all these kinds of data structures? We've mentioned that organizing soda cans in a vending machine instead of a can tower is much more efficient, as it is far easier for us to perform any actions on these cans. What does this mean formally? In a nutshell, different data structures have different time complexities for performing the same external operations in a set of data. This is why it is essential to consider all the possible structures and choose the most efficient among them. Let's illustrate what we've said above in an example.

Later on, you will learn about an important shortest path algorithm: Dijkstra's algorithm. It has two main implementations: using an array or a heap as a data structure. In the first case, Dijkstra's algorithm time complexity will be $O(n^2+m)$, whereas if we use the second type of data structure, our algorithm will work on $O((n+m)\log n)$. Just for now, we suggest ignoring the names and the unfamiliar terms — the idea is to simply illustrate how using different data structures can lead to different time complexities of the same algorithm. There is a famous book entitled Algorithms + Data Structures = Programs, written by the Swiss scientist Niklaus Wirth in 1976. This book covers some of the fundamental topics of computer programming; its title shows quite clearly just how essential it is for a programmer to understand data structures.

Common principles

There are several key principles of data structures. Data structures:

1. provide a systematic way to organize and structure data, ensuring efficient storage and retrieval.

2. are designed to optimize operations such as searching, insertion, deletion, and so on, ensuring efficient algorithmic performance.

3. provide scalability and flexibility, allowing systems to handle growing or changing datasets without sacrificing performance.

4. optimize memory usage and manage memory allocation and deallocation efficiently.

5. promote code reusability by encapsulating data and operations into reusable modules, enhancing software development productivity and maintainability.

Conclusion

To sum up, let's revisit the key points covered in this topic:

• Data structures are tools for organizing data and providing efficient access to it. They encompass a wide range of types and implementations.

• Data structures have two types of operations: internal operations, which facilitate data organization, and external operations, which allow users to store, retrieve, or modify data.

• Different data structures come with varying time complexities for the same external operations. Selecting the most efficient data structure is crucial for optimizing program performance.

In conclusion, understanding data structures and their role in computer science is essential. In the following topic you will study data structures deeper, by learning some more formal definitions and concepts, and after this you will have the chance to explore many of the data structures used in practice by professionals.