What is the difference between data structures and abstract types of data?

Asked

Viewed 213 times

8

I looked in some books and some Internet pages, but I couldn’t get a clear answer.

terminology computer-science
  • 1

    Abstract type describes what the type does, is the 'API' so to speak. Data structure is the real thing, is how the type is implemented.

  • What confuses me are structures like AST and ASG where the 'As' in the acronyms already means Abstract (Abstract Syntax Tree and Abstract Semantic Graph).

  • Did the answer solve your question? Do you think you can accept it? See [tour] if you don’t know how you do it. This would help a lot to indicate that the solution was useful to you. You can also vote on any question or answer you find useful on the entire site

1 answer

8

It is said that ADT is the abstract way of defining structures without specifying the way it works, without the concern with certain criteria, ie if you want to put a list of objects your Abstract Data Type is the List.

We start talking about data structure when we specify the implementation, for example from this list. So if it is a list as a array, whether a hash, If it is turned on, etc., then it is the concrete way to do the ADT. The data structure defines the details of how the data is disposed, how it will be placed, retrieved, removed, how it can be computed, what conditions each operation will take place, how it will be memory consumption, time for each type of algorithm, etc.

Let me give an example that I think helps understand and relates to the questions Applying trees to real problems and What is the difference between a map, a dictionary, an associative array and a hash table?.

Let’s say you have a mechanism called a dictionary, that’s an ADT. It can give some characteristics that he must have to solve certain problems. Each language or library can deliver this dictionary with these features any way they want. Therefore the implementation can choose the data structure it wants to produce the expected result giving the opportunities determined by the ADT. You can do the most crazy things you want. You can use a data structure from a red black tree. But nothing prevents you from using other trees, or a Skip List, or even a form of hash the ADT does not say that it needs order (usually needs), or could use a array if you don’t need to find a data with near constant time (what you usually need, just one example).

  • I saw the same thing Maniero, as if it were Class/Object... are those terms that get confused, seem the same thing, and should have a subtle difference. I remember that in college I was "data structures", the term "Abstract data type" is more "chic" :)

  • I think I understand what you mean, but class and object do not get confused https://answall.com/q/100812/101. I understand that they are different things and this q answered is correct, but I think loose, I want to try to find something more solid than that, it may not exist. I’ll try to explain why the difference makes sense, I need to find the tone of the text.

  • The article The Birth of Simula (Stein Krogdahl) speaks of a possible origin of Tads: Object-orientation "paved the way for the later Concept of Abstract data types (see C. A. R. Hoare. Proof of correctness of data representations. 1972)". Interesting Tads to be (a little) posterior to objects.

Browser other questions tagged terminology computer-science

You are not signed in. Login or sign up in order to post.