CODEWITHSUNDEEP
algorithmdata-structures
tural
tural

Reputation: 320

ADT or concrete

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.

Upvotes: 0

Views: 331

Answers (2)

Hamed Nassar
Hamed Nassar

Reputation: 19

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.

Upvotes: 0

codebox
codebox

Reputation: 20254

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
}

Upvotes: 1

Related Questions