Abstract and concrete data structures

After getting familiar with the concept of data structures and its importance, it is time to know some other fundamental details about them. That is to say, we will learn about abstract and concrete data structures, as well as the difference between them. This enables programmers to select the right data structure, design efficient algorithms, manage memory effectively, develop modular and reusable code, and facilitate collaboration and communication within a development team.

Abstractness of vending machines

There is another term: abstract data type (ADT), which is sometimes used as a synonym for data structures, though this is not entirely correct. Let's try to figure out what ADT is by considering yet another example.

We hope you don't doubt that this above is a vending machine. The thing is that you can't see what exactly it contains on the inside. Now, you probably know how to interact with vending machines: you insert a coin and get your drink. If you are just thirsty, this information is more than enough. It doesn't matter to you how the machine works from the inside, how it organizes the payment, the beverages, or how many beverages there are; you only need to know how to get your soda. Hence, this is an abstract vending machine for you.

Abstract data types

For those who would like a formal explanation of this concept, we should say that in programming, such techniques of "covering vending machines" are known as:

• Abstraction — a concept in object-oriented programming; it "shows" only essential attributes and "hides" unnecessary information, a.k.a. abstract classes or interfaces;

• Encapsulation — is a method of making a complex system easier to handle for end users. Formally speaking, encapsulation is the process of combining data and code, operating this data into a single entity. The user needn't worry about the internal details and complexities of the system.

In general, an Abstract Data Type is a mathematical concept, a simpler and more abstract way to view the data structure as a whole. It is a data type that is defined by a set of values (elements/items) and a set of possible external operations (behavior) from the user's point of view. 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 these ADTs in standard libraries so that we can use them in our programs.

How do they vend

Let's get back to our vending machine parable once again to realize the difference between data structures (sometimes referred to as CDTs – concrete data types) and ADTs.

There are different ways to create a simple vending machine that performs a single function of exchanging a coin for a drink. We can keep the soda in a huge bottle; we can put it in different bottles in a heap inside the storage; we can organize the bottles and tins in one big row or ten different rows. All these arrangements can be called the implementations of a simple abstract vending machine. Nevertheless, they are still vending machines that exchange a coin for a drink.

If you want to create a more complicated mechanism with several functions, for example, "choose a type of soda, then insert a coin" or "choose a drink or an ice cream", the previous implementations won't work. In this case, we will have not only a new CDT, but also a new ADT: a vending machine that does much more than just exchange a coin for a drink.

CDT vs ADT

So, data structures (CDTs) are exact representations of data, but ADTs are different: they reflect the point of view of a user, not an implementer. A data structure (CDT) is an implementation of an ADT's functions, a way to look more closely at some specific operations and components of the structure.

Recall from the previous section, that a stack is an abstract data type. It may define operations like push, pop, and peek, regardless of whether it is implemented using an array or a linked list. On the other hand, each one of these possible implementations defines a concrete data structure. For those who are familiar with OOP, java.util.Map, for example, plays the role of an ADT, whereas HashMap or LinkedHashMap can be interpreted as data structures.

Conclusion

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

• Abstract data type (ADT): ADTs represent a higher-level perspective of data structures, focusing on their functions and overall behavior rather than implementation details.

• Comparison of data structures and ADTs: Data structures are precise representations of data, while ADTs define the logical form and behavior of a data type.

It is okay if you don't understand the formal definition of an ADT or a CDT yet in every detail. You will get a chance to get back to it later. So, are you hungry for more? Dozens of topics on specific data structures are waiting for you on our platform.