Abstract data types vs Data structures

March 6, 2005 at 11:43 pm 25 comments

C++ data structures is another course am learning this semester. This course is a pre-requisite for all non-Computer Science students. I have already learnt and implemented all the C++ data structures in a private course during my undergraduate studies, but not with the same understanding am learning them these days. Frankly I dont know much about data structures during my work experience. So I consider this course as an opportunity to get my hands on C++ again and implement various datastructures.

First thing I got to know is.. the difference between the abstract data types (ADT) and datastructures. Earlier I thought they are same.

Before starting that, we need to be clear about the logical and implementation level of data. Let us take an example of a simple built-in data type integer. At the logic level, we application programmers know only about what are the operations an integer data type can perform, ie., addition, subtraction etc., But we are no way aware of how the data type is actually implemented. At the implementation level, it is about how the data type integer is implemented in the machine level, ie., it could either of binary-coded decimal, unsigned binary, sign-and-magnitude binary, One's complement and Two's complement notation.

Now.. for the understanding the ADT and data structure, we need to assume a higher level abstraction where we have the built-in types at the implementation level.

To put it simple, ADT is a logical description and data structure is concrete. ADT is the logical picture of the data and the operations to manipulate the component elements of the data. Data structure is the actual representation of the data during the implementation and the algorithms to manipulate the data elements. ADT is in the logical level and data structure is in the implementation level.

As you can see, ADT is implementation independent. For example, it only describes what a data type List consists (data) and what are the operations it can perform, but it has no information about how the List is actually implemented.

Whereas data structure is implementation dependent, as in the same example, it is about how the List implemented ie., using array or linked list. Ultimately, data structure is how we implement the data in an abstract data type.

This is something new of what I have learnt.

Entry filed under: data structures.

got to know.. ‘Leda’ How function calls work?

25 Comments Add your own

1. kurt | October 27, 2006 at 2:08 am

We really had the same problem-finding out the difference between the two. But when I google it I found your link and now it’s confirmed as I’ve read also from a certain book. Thanks for your explanation.
Reply
2. Shevesh Srivastava | November 13, 2006 at 6:18 pm

Atlast I got my query solevd from ur this explanation. It is really very simple and precise explanation of, I think, some of the most confusing/critical aspects of computer programming.

Just, if possible, plz explain what does it mean by…

“we need to assume a higher level abstraction where we have the built-in types at the implementation level.”

… in the fourth para.

Thanks & Regards
Shevesh
Reply
3. Shevesh Srivastava | November 13, 2006 at 6:43 pm

I have read sumwhere that …

The choice of the data structure often begins from the choice of an abstract data structure.

… can i ask for an explanation, how is it so… plz..
Reply
4. Vignesh M.P.N. | November 23, 2006 at 9:18 pm

@ Shevesh
On your first question, in the earlier para I took an example of integer data type, so I was treating the programming language as logical level. Basically I was dealing with three layers: machine level, high-level programming language and application layer. So for the integer data type example, high-level programming language is the logical level while machine level is the implementation level.
For explaining further about ADT and data structure, I said to assume a higher level of abstraction wherein the application layer is the logical level. Now the programming language will be the implementation level where integer is a built-in type.
Hope this helps. 🙂
Reply
5. sapna | March 6, 2007 at 9:52 am

Hi,

can you please explain me ADT with an example? it will be helpfull for me.

Thanks in advance.
Reply
6. sapna | March 6, 2007 at 10:52 am

Hi,

I am new to the topic ADT. Please give me the explanation of it with some easy example.

thanks.
Reply
7. edson | March 18, 2007 at 9:35 am

hi
i would like to know if an array is a data structure or an abstract data structure,and why.
Reply
8. Rahul | September 25, 2007 at 6:42 pm

Coolest explanation available on net.
Reply
9. omkar | September 26, 2007 at 5:15 am

hi,
you have explained a very confusing topic very skillfully. Thanks a lot. Similar topics ll be always welcome
omkar
Reply
10. tirsit hailu | April 11, 2008 at 1:28 pm

please tell me how i become nice programer and send to me about the reference that help me to get aknawledge about ADT
Reply
11. sagar | December 4, 2008 at 6:57 am

thanks…………
Reply
12. sagar | December 4, 2008 at 6:57 am

thanks a lot
Reply
13. Jahanzeb | April 25, 2009 at 9:29 am

Thanks, for your explanation. I was doing my assignment and i was so confused between the difference. A now have got an idea where to start from.
Reply
14. santhosh | October 9, 2009 at 2:05 pm

its good definition
Reply
15. Rajit | December 7, 2009 at 10:02 am

Thank you.
Reply
16. Bilal Ahsan | January 10, 2010 at 5:33 pm

This is difference berween Abstract Data Type and Concrete Data Structure,,
Can u explain what is difference between Abstract Data Type and Abstract Data Structure?
Reply
17. nasrin | April 26, 2010 at 7:40 am

its pretty gud..:)
Reply
18. Saurabh | November 18, 2010 at 1:10 pm

Thank you bro for this article 🙂
Reply
19. Ankit | October 20, 2011 at 4:22 am

Thanks a lot for such a simple explanation. It helped me to understand the concept at last
Reply
20. ashutosh tripathi | November 8, 2011 at 7:37 pm

nicely explained. thanks a lot
Reply
21. Vignesh(not the author) | September 6, 2012 at 11:51 am

Nice explanation, esp from the aspect of an application programmer trying to understand computer science. Just wanted to add some more input from my side.

Statement: Stack is an ADT having push and pop operations on it. ( who says this matters.)
Statement: Stack is an datastructure having push and pop operations on it. ( ho says this matters. )
Both are true.

From the consumer’s perspective, Stack is an data structure but for the implementors of Stack this is an ADT. But while implementing the stack we might be using array data structure(a concrete usage), but the array is an ADT in itself. We do not know how array is implemented but for the array implementors(say for K&R, in case of C language) array is a ADT whereas its internal implementation would be using a data structure.

So it all boils down to at what abstraction hierarchy we are speaking from. If I am speaking as webapp developer using Stack to store my incoming request, I could use the word Stack as a data structure but if I were to be an implementor implementing Stack (using Linked List or array or whatever ‘data structure’) I would consider Stack as an ADT.

Please do correct me if I have gone wrong in my understanding. Thanks.
Reply
22. Ranjani | September 1, 2013 at 10:05 am

Nice Explation. Helped a lot
Thanx!
Reply
23. veerendhar | September 18, 2013 at 4:14 am

i had same problem as u , but now i my problem was cleared ,
thank u
Reply
24. poornima | September 18, 2013 at 5:04 am

can you please mention difference between with an example
Reply
25. Karim Oumghar | January 22, 2016 at 9:57 pm

Reblogged this on Bits and Pieces of Code.
Reply