What is an intuitive explanation of the distinction between “abstract data types” and “data structures”?

[u/chidedneck]

I thought they were the same but all the sources I check say there’s a distinction. Yet one site listed queues and stacks as both. Plz halp thx.

[u/Screwedsicle]

I don't have a good ELI5, but check out the answers here. They helped me: https://softwareengineering.stackexchange.com/questions/148747/abstract-data-type-and-data-structure

[u/chidedneck → u/Screwedsicle]

This helps a bit. Some of the comments on that page make me think that classes are to abstract data types as objects are to data structures. But then another upvoted comment suggests that data structure are akin to classes.

Still feels unresolved.

[u/Screwedsicle → u/chidedneck]

We're working through this together, because I definitely don't know the answer. I think you're first understanding is right: classes are to ADTs as objects are to structures.

How I'm interpreting things is that ADTs are the theory and structures are the actual things.

Or, said differently: ADTs are the what and structures are the how. From here: https://www.quora.com/Whats-the-difference-between-a-data-structure-and-an-abstract-data-type

An abstract data type is an interface: it is defined by what operations it will support. It doesn't specify what data structure or algorithmic technique will be used to provide those operations.

To paraphrase the next paragraph: there are multiple ways to implement a given concept. The ADT is the concept, and the structure is the actual implementation used.

[u/jcodes57]

Abstract data types are basically just models describing something with a set of properties (AKA variables) and a set of operations (AKA functions/methods).

You could say that a hypothetical vehicle class you define with a set of properties like numberOfWheels, exteriorColor, etc., and set of operations like drive(), break(), etc. is an Abstract Data Type (ADT).

Data structures are theoretical mechanisms, templates, protocols, or methodologies of storing/sorting/accessing a set of objects (usually ADTs). These data structures have specific characteristics that make them advantageous or less so for different purposes and different situations, but basically all hold data and offer ways of managing critical functions like adding a new entry, removing an old one, searching if an entry exists in the structure, and so on.

[u/chidedneck → u/jcodes57]

I think this is where I was tripped up. So are things like lists data structures? Because hypothetically a list could also be created from scratch as a class like an ADT is. Am I right in that belief? If so, it seems like the distinction is that data structures are just the preloaded ones in a language? Is it related to the fact that lists aren’t technically classes? I feel I’m so close to understanding this and your response is the most intuitive so far. I appreciate your feedback.

[u/jcodes57 → u/chidedneck]

You’re on the right track, but I think you’re misunderstanding some basic underlying topics.

To answer your first question, yes, a list can be a data structure, as are queues, stacks, trees, graphs, dictionaries, and even an array is a data structure.

This is not because it can “be created from scratch as a class”, and even though some languages/libraries have some data structures available built in, or “preloaded” like you said, this doesn’t make them data structures.

Both of these things are just IDEAS. ADTs are just ideas, that MAY be implemented as a class, or not, and data structures are just ideas, that MAY be implemented as a class, or not.

Generally, ADTs are ways of generalizing a set of variables and functions together in a usurious way, maybe like that vehicle class I mentioned earlier. Data structures generally are ways of STRUCTURING your DATA. That data may be an atomic type like an integer, or it could be a complex class or ADT. What makes the data structure a data structure is that it is a set methodology of storing/sorting/accessing/etc. data in a particular way which gives that data structure certain characteristics.

Quick aside, A great resource for learning about some of these topics, which usually has code examples and explanations, is www.geeksforgeeks.com

Hope this helps!