Can someone clarify the exact difference between abstract data type(ADT) and concrete data structure. As I am reading the book(Anany Levitin, Design and Analysis of Algorithms), it states that ADT is a data structure plus set of operations on them. However, what confuses me is that, Arrays and Linked Lists also have some certain operations defined on them(e.g adding element,deleting element) and they are considered as concrete data types. Due to that confusion, I cannot decide a new data structure for me(e.g heap, tree, binary search tree) to be abstract or concrete by myself.
Asked
Active
Viewed 327 times
0
-
[Abstract Data Type and Data Structure](http://programmers.stackexchange.com/q/148747). [What is the difference between an Abstract Data Type(ADT) and a Data Structure?](http://stackoverflow.com/q/13965757) [Is there a difference between 'data structure' and 'data type'?](http://stackoverflow.com/q/18940961) [Abstract data types vs Data structures](http://abrickshort.wordpress.com/2005/03/06/abstract-data-types-vs-data-structures/) (and a few dozen / hundreds of others) – Bernhard Barker May 31 '14 at 00:53
2 Answers
1
An ADT is a description of what a data structure looks like, it does not contain any code - think of it as a specification that you might give to a programmer when asking them to write a data structure for you.
The ADT for a Stack might look like this:
void push(int)
int pop()
The corresponding concrete data structure would contain the actual code needed to make these functions work:
void push(int x){
// implementation code here
}
int pop(){
// implementation code here
}
codebox
- 19,927
- 9
- 63
- 81
0
The relation between Data structure, Abstract data type and Data type is the same as the relation between Algorithm, Pseudo-code and Program. The first is an idea, the second a description and the third an implementation.
Hamed Nassar
- 19
- 1