Table of Contents
Let’s face it: there’s no way around 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. It’s best if it doesn’t take an awful lot of space, too. This is where data structures come in handy, so let’s learn the important basics about them.
What are data structures
Data structures are a way of organizing data and providing convenient access to it. Quite 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 somehow. We could put it all in a random bag or build a grand 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 decide 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, and understand the capacity of the machine.
Now let’s return to the definition and try again: data structure refers to a collection of elements containing data, relationships among these elements, and data operations. As a rule, data structures have two types of operations: internal operations that support data organization and operations available to users for storing, retrieving, or modifying data.
There is a famous book titled Algorithms + Data Structures = Programs written by a Swiss scientist Niklaus Wirth in 1976. The book covers some of the fundamentals topics of computer programming; its title quite clearly demonstrates just how important it is for a programmer to understand data structures.
There are several common data structures: array, linked list, hash table, and a whole variety of trees (binary search tree, heap, red-black tree, B-tree, etc.). They are considered at length on our platform, but don’t hurry: let’s absorb the basics.
Abstract data type
There is another term: abstract data type (ADT), which is sometimes used as a synonym for data structures, though this is not entirely true. Let’s try to figure out what ADT is by considering yet another example.
We hope you have no doubt that this is a vending machine. You probably also know how to interact with it: you insert a coin inside and get your drink. If you are just thirsty, this information is more than enough. You don’t care how the beverages are organized inside the machine or how many there are; you just know how to get your soda. So this is an abstract vending machine for you.
Abstract Data Type is an abstract type that is defined by a value and a set of possible operations (behavior) from the user’s point of view. This type of description is used to give a “big picture” without confusing anyone with specific details. There are some common ADTs that every trained programmer should know: stack, queue and so on. As a rule, modern programming languages like Java, Python, and C++ provide them in standard libraries to be used in new programs.
Comparison
Let’s get back to our vending machine parable once again to see how data structures compare to ADTs.
There are different ways to create a simple vending machine that performs a single function of “exchange a coin for a drink”. The soda can be kept in a huge bottle; it can be already in different bottles in a heap inside the storage; the bottles and tins can be put in one big row or ten different rows. All these arrangements can be called the implementations of a simple abstract vending machine. If you want to create a more complicated mechanism with several functions, for example, “choose a type of soda and then give a coin” or “choose a drink or an ice cream”, some of the previous implementations won’t work for that.
ADTs contrast with data structures that are concrete representations of data; they are the point of view of an implementer, not a user. A good example of an abstract data type is an integer. We know what values they can have and what operations they support (addition, subtraction, multiplication and so on). They may be represented as one’s or two’s complement in computer memory, but we usually don’t care. It is enough for us to know that what we have is an integer, not a floating-point number.
In some sense, ADT defines the logical form of the data type, while data structure implements the physical form of the data type.
Conclusion
There is a lot of types of data structures used to efficiently organize and manage data in programs. Another closely related concept to keep in mind is abstract data type (ADT) that conceals a specific data structure, providing only a well-defined set of operations necessary for the user-programmer.