# Abstract Data Type and Data Structure

It's quite difficult for me to understand these terms. I searched on google and read a little on Wikipedia but I'm still not sure. I've determined so far that:

Abstract Data Type is a definition of new type, describes its properties and operations.

Data Structure is an implementation of ADT. Many ADT can be implemented as the same Data Structure.

If I think right, array as ADT means a collection of elements and as Data Structure, how it's stored in a memory. Stack is ADT with push, pop operations, but can we say about stack data structure if I mean I used stack implemented as an array in my algorithm? And why heap isn't ADT? It can be implemented as tree or an array.

Simply put, an ADT (Abstract Data Type) is more of a logical description, while a Data Structure is concrete.

Think of an ADT as a picture of the data and the operations to manipulate and change it.

A Data Structure is the the real, concrete thing. It can be implemented and used within an algorithm.

• but I can implement a Stack and Queue too (that are ADT) inside an algorithm. no?
– Fed
Commented Jan 23, 2017 at 19:33
• Stack and Queue are logical representations with specific computer science meanings. However, the implementation of a Queue in C#, Java, Go, or [name your language] is going to be slightly different. Queue the concept is ADT, the Java Queue is a Data Structure. Same with the C# Stack implementation. Commented Nov 14, 2019 at 14:50
• Explanation is clear; however, does that mean, that this article has a wrong explanation of Dynamic Array? because, Dynamic Array is definitely some abstract concept, and not a particular implementation. en.wikipedia.org/wiki/Dynamic_array Commented Apr 6, 2020 at 15:25
• i think one possible explanation is that the behaviour of a dynamic array can be implemented in many different ways (e.g. reallocation, large preallocation, multiple arrays).
– MrR
Commented Mar 2, 2023 at 11:21

ADT is to a data structure what an interface (what it does) is to a class (how it does it).

A few examples:

``````ADT: List

DS:  HashMap, TreeMap...
``````

I guess you get the point.

• ADT can be said as the general type of a Data structure ? Commented Dec 21, 2013 at 17:49
• This should be the marked answer. It couldn't have been said more simple for layman. Commented Mar 27, 2017 at 22:21
• thanks @dagnelies for the simple and effective answer. This should be marked as answer. Commented Aug 31, 2017 at 9:01
• Not sure why but I prefer a small re-arrangement in the wording here: `ADT is to a Data Structure, what an Interface (what it does) is to a Class (how it does it)`. The examples are spot on. Commented Apr 28, 2018 at 8:27
• @AdityaMP just wanted to point that out as well. I believe the answer should be edited. Commented Dec 26, 2019 at 11:58

Abstract Data Type: ADT may be defined as a set of data values and associated operations that are precisely specified independent of any particular implementation. Thus an Abstract Data Type is an organized collection of information and a set of operations used to manage that information. The set of operations defines the interface of the ADT. As long as the ADT fulfills the conditions of the interface, it doesn’t really matter how the ADT is implemented. Since, in ADT, the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language, we may reason about effects of the operations, relations to other abstract data types whether a program implements the data type etc. One of the simplest abstract data type is the stack data type for which functions might be provided to create an empty stack, to push values onto a stack and to pop values from a stack.

The basic difference between abstract data type (ADT) and concrete data type is that the latter allow us to look at the concrete representation, whereas the former hide the representation from us. An ADT may be pure ADT or Updatable ADT. A pure ADT is one where all operations are pure functions. This means that operations have no side effects. In particular, they do not modify or update there input arguments. They just use these arguments to generate output, which are fresh values of ADT (or of other types). Most concrete types are pure. For example, no operation on integers actually modifies an integer. Instead, all the operations like ‘+’ produce fresh outputs.

An updatable ADT is one where some operations actually change values of the ADT. For example, suppose we had an operation called ‘pop’ that took a stack as an argument and modified it. (“in place”, “destructively”) by removing the highest priority item. This operation would be considered impure and the whole ADT would then be impure also. An ADT may be user defined ADT.

We know that an Abstract Data Type is a data type that satisfies the following two conditions:

1. The representation, or definition, of the type and the operations are contained in a single syntactic unit.

2. The representation of objects of the type is hidden from the program units that use the type, so only direct operations possible on those objects are those provided in the type’s definition.

A user defined Abstract Data Type should provide:

1. A type definition that allows program units to declare variables of the type, but hides the representation of these variables.

2. A set of operations for manipulating objects of the type.

An example of a user defined abstract data type is structure. ’C’ provides four basic types: int, char, float and double. However, ‘C’ also provides the programmer with the ability to define his/her own types. Structure is one such example. A structure is an aggregate of different parts, where each part is of some existing type.

``````struct abc

{int x;

float y;

};
``````

The above structure definition does not create any variables, rather it creates a new type. Variables of this type may be created in a similar way to variables of a built in type.

``````struct abc a;
``````

The typedef keyword allows us to create new type names for our new types.

For example:

``````typedef struct abc AB;
``````

where AB is a new type name that can now be used to create new types.

``````AB b;
``````

Data Structures: The following are the characteristic features of data structures:

1. It contains component data items, which may be atomic or another data structure (still a domain).

2. A set of operations on one or more of the component items.

3. Defines rules as to how components relates to each other and to the structure as a whole (assertions).

Data Structures:

A data structure may be static or dynamic. A static data structure has a fixed size. This meaning is different from the meaning of static modifier. Arrays are static; once we define the number of elements it can hold, the number doesn’t change. A dynamic data structure grows and shrinks at execution time as required by its contents. A dynamic data structure is implemented using links.

Data structures may further be categorized into linear data structures and non-linear data structures. In linear data structures every component has a unique predecessor and successor, except first and last elements, whereas in case of non-linear data structures, no such restriction is there as elements may be arranged in any desired fashion restricted by the way we use to represent such types.

First of all, Terminologies in data Structures can be very confusing.

ADT is like theory or model or guideline etc. which tells how a data structure should behave, what kind of operations it should support etc. Three fundamental abstract data types are containers, dictionaries, and priority queues. For example dictionary, it tells us that every data structure which implements this dictionary ADT must support key-value pairs, search based on keys, insertion of items, finding successor and predecessor of a given key etc.

Now everything else that implements this above ADT is Data structure (DS), Data structure are real things which you implement in your problems and find inside libraries. In case of dictionary, you can chose to implement it via Array or Linked list.

I think real confusion arises when someone name their DS as ADT, for example some people will call their aforementioned DS as 'Dictionary' instead of DictImplementation which is perfectly legal, it just causes some confusion.

Ref: Skiena : The algorithm design manual

• what makes it most confusing, I think, is that everybody uses lamguages like Python that have so much abstraction that you can't realistically talk about implementing data structures. Just on another thread on stackexchange people were talking about how you can implement stacks and other DSs in python. Those aren't DSs. Those are ADTs. And implementing a linked list in python isn't something you can do. You instead implement its stereotypical behavior, in which case you've turned into more of an ADT. A linked list makes 0 sense in python. Commented Jan 17, 2021 at 0:58
• HI @Daniel are the definition in here correct ? Data Structures and Algorithms Using Python 1st Edition doc.lagout.org/science/0_Computer%20Science/2_Algorithms/… , start studying them and dont wont to ge them the wrong way Commented Jan 28 at 19:08