This is a very simplified view. For a formal approach, you need to look at
There is no real difference. Data structures are just standardized
types and type constructors (such as tuple or list), with associated
primitives operations, that are convenient for building other types
with usually a very direct implementation, and are predefined in the
kernel of your programming language.
An abstract data type is defined as an abstract domain D, with its
primitive operations, which is implemented by defining a mapping so
some (more concrete?) type defined with the preexisting constructors.
The primitive operations are also implemented as function using the
primitive operations available for the more concrete
implementation. Then there is an encapsulation mecanism so that the
concrete implementation is hidden, and only the abstract part is usable
in the program.
This abstract data type can be a constructor when its definition
depends on some other yet unspecified type.
Then we can remark that:
the data structure types defined by the programming languages are
themselves abstractions: a domain of value and its primitive
operations. It is seen as concrete because it is mapped in simple
ways on the computer hardware.
the definitition of an abstract data type may well use another
previouly defined abstract data type for its implementation.
Hence there is no reason to make a difference.
However, the expression "data structure" refers generally to the types
obtained with the primitive types and constructors of the programming
As a reply to some comments, and to make things clearer:
I can define a balanced tree (pick your preferred flavor) as an ADT,
Balanced, implemented with the more elementary types provided
by the language, possibly parameterized by the type of the data it
contains (which would rather make it an ADT constructor, to use my
informal terminology). Then I can used this ADT
Balanced to build another ADT
Set for sets, as suggested in the answer of Wandering
Logic. Then I can use the ADT
Set to implement some other ADT
Note that I could be more specific and actually call my ADT
with a corresponding implementation, if I want to suggest that it will
have exactly all the properties of red-black trees. It will
nevertheless be an ADT, since the program will be allowed to use only
the given primitives, without being allowed to fiddle with the
pointers of the implementation at the risk of bugging the structure.
Then people may consider that data-structures are what is used for
implementation, while ADTs are the abstraction that is built with the
data structure. I will not fight it as this is terminology, and it
does not really matter to me (see further comments below). But, then,
I will point out that
Set, are clearly ADTs when
being defined, but become data structures when looked at from the
point of view of the other ADTs they are used to implement.
This only confirms what I said. They are the same.
I know "we eat beef and pork rather than cow and pig", but
these four names cover only two species, and the difference is only in
the use made of the animal. Whether an ADT is pork or pig may be
convenient terminology, may indicate a difference in intent, or a difference of perspective, but not a
difference in substance.
Another issue raised in that context is that of complexity, as if it
mattered more when looking at data structure, at implementation.
An immediate consequence of what I just said is that there cannot be
any difference on that basis. When I implement the ADT
Balanced, I am
of course very careful to have a good implementation. And the
complexity characteristics of the functions associated with that ADT
(insertion, deletion, traversal, ...) are of course part of the
specification, though that is usually implicit in the program, as well
as other interesting properties of the abstraction (quite often). Then
I can rely on the complexity of the
Balanced primitives to analyse the
complexity of whatever is implemented using
When I use the ADT
Balanced as data structure to implement the ADT
Set, I will again be careful to get good complexity of its primitive
operations (such as union or intersection of
Set values) which will be
(possibly implicitely) part of the Set interface specification. So,
when I analyse the complexity of the ADT
XXX, I can simply rely on what
I know of the complexity of
And this is very much what we do when studying the complexity of
intricate algorithms. We rely on existing, well analysed constructs,
and seldom look into the way they were themselves designed and
analyzed. This is the essence of abstraction, and it is only the classical way of doing Mathematics. When we
use a theorem, we do not have to think about its proof (Thanks to
Curry and Howard for their support in this discussion).
Now I gave my view of the use of the terminology. It may be outdated,
I do not know. But I would not worry a second about it since the two
expression denote the same substance anyway. The difference, if any,
is in the way you want to look at that substance. My own perception is
that the only concrete difference is between the fact that original
data types of the language are hard-coded by the compiler and have to
be taken as they are, while all others, user or library defined abstract data
types, can be re-implemented if need be. As I perceive that as the only
significant difference, I rather use the extra word data structure to
identify that. It may be that there is a different consensus in some
communities, actually shared by the answer of Wandering Logic.
A justification for it is that people could use the implementation
based on other types without ever abstracting it, which would support
the idea of having a specific name for it (I often just use the word
Then, just to make things a bit more confused, the Wikipedia page for
Data Structure talks also of Abstract Data Structure, wich a link
to ... Abstract Data Type.
Somehow, I strongly doubt there is an official unified terminology for all
this. Except probably when giving formal definitions using type theory.