Abstract data type vs Data Type vs Data Structure, with respect to object-oriented programming

Question

It is my understanding that a data structure is essentially a blueprint which contains all the information necessary to create a final product according to its specification, and a data type is a physical implementation or realization of that design (quite similar to the difference between a genotype and phenotype, from biology).

When it comes to object-oriented oriented programming, would it be accurate to say that an abstract class or interface is a data structure, because it contains a set of values and declared behaviors, and that a class which implements that abstract class or interface is a data type, because it is a concrete manifestation of those behaviors?

If this is the case, then what about the distinction between an abstract data type (ADT) and a data type? Are they truly distinct, or is ADT just colloquially shortened to 'data type'?

I ask this because it has seemed to me that these terms are often used interchangeably in conversation, and it made me wonder if my understanding was incorrect.

Answer 1

I am fairly new to answering on stackoverflow and to this sort of data structure vs data types discussion, but hopefully this helps. These links have done a lot for me in addition to what I've been taught:

Is there a difference between 'data structure' and 'data type'?

Explain the difference between a data *structure* and a data *type*

http://cs.lmu.edu/~ray/notes/dtds/

First of all, I'm going to define my usage of the word "implementation" since it seems I might be using it slightly differently than you are. I define implementation like the implementation files in C++. Such implementation contains the source code for how some interface works. For example the implementation of a singly linked list is a bunch of nodes that each contain data with a starting node that points to the next node until the last node points to some sort of null. In that sense, I can't quite say that a data type is a physical implementation of a data structure. A simplified version is that a data structure is actually the physical implementation of one or more data types. For example, a stack is a data type while a LinkedStack is a data structure that implements a stack. Although a data type can represent all possible instances of a data structure as described by the links above, not all data types have to. For example, an int is a data type, but it's not exactly the best idea to say it is a data structure.

To summarize each, please let me go in the order of data types, abstract data types, and then data structures.

Data types or types for short classify data by its values and operations. For example, if the data is 42, is 42 an int or a string? If it's an int, what int is it (what's its value)? Is it positive or negative? What kinds of operations does it have? Can I divide with it? In that sense, data types depend purely on their external behavior.

Now some data types might not specify any sort of implementation and those data types are called abstract data types. Basically, a data type is an abstract data type if the user can't access nor care about access to how the values and operations are implemented. For example, ints are abstract data types since a programmer doesn't need to know and might not care to know how ints work or how ints are added. Yet, said programmer can still work with ints, adding away to his/her content. User made data types that don't reveal its implementation would also be abstract data types. Because of this, many data types are abstract data types. In addition, abstract data types can model similar data types and data structures and be implemented by specific data types and data structures as the links above describe.

Finally data structures are ways to efficiently store data, and they are all about the implementations. For example, a singly linked list and a doubly linked list are different data structures because they have different implementations. Single linked lists only go forward whereas double linked lists can go forward and backward. I described the implementation for singly linked lists above while in short a doubly linked list's implementation is the same as a singly linked list's implementation but each node would also have a pointer to each previous node to allow the doubly linked list to go backward. The gist of data structures is that the implementation (how data is organized/stored) of a data structure is how it is distinguished.

If you want an example of the efficiency doubly linked lists have over singly linked lists, these links are nice:

When is doubly linked list more efficient than singly linked list?

https://social.msdn.microsoft.com/Forums/vstudio/en-US/270bebdb-9032-4fc1-97c6-bc017d7e0a45/when-to-use-single-linked-list-and-when-to-use-double-linked-list?forum=csharpgeneral

Otherwise, hope I was of some use and good luck.

Answer 2

Abstract Data Type

• Defines contractual agreement for behavior and state management
• Abstract Data Types exists only conceptually. They have no concrete existence in the context of a language. This is why Wikipedia refers to it specifically as a mathematical model.

Data Structure

• Class level implementation of the contract defined by an abstract data type.

• Data Structures exists in the form of the code that comprises your class definition.

Data Type

• Concrete instance of a class

• Data Types exists in the form of objects created from classes you defined.

Examples

• A Priority Queue is an abstract data type which can be implemented with a Binary Heap data structure.

• A List is an abstract data type that can be implemented with an array or linked list data struture

TLDR

Abstract Data Type > Data Structure > Data Type