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.

| improve this answer | |
  • but I can implement a Stack and Queue too (that are ADT) inside an algorithm. no? – FedericoCapaldo Jan 23 '17 at 19:33
  • 1
    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. – Berin Loritsch Nov 14 '19 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 – Giorgi Tsiklauri Apr 6 at 15:25

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

A few examples:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

I guess you get the point.

| improve this answer | |
  • ADT can be said as the general type of a Data structure ? – Owais Qureshi Dec 21 '13 at 17:49
  • 2
    This should be the marked answer. It couldn't have been said more simple for layman. – deppfx Mar 27 '17 at 22:21
  • thanks @dagnelies for the simple and effective answer. This should be marked as answer. – Sarun UK Aug 31 '17 at 9:01
  • 3
    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. – Aditya M P Apr 28 '18 at 8:27
  • @AdityaMP just wanted to point that out as well. I believe the answer should be edited. – Johannes Luong Dec 26 '19 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.

| improve this answer | |

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

| improve this answer | |