Abstract data types vs Data structures

March 6, 2005 at 11:43 pm 20 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.

About these ads

Entry filed under: data structures. Tags: .

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

20 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Author

I am Vignesh M.P.N., a graduate student, doing my MS in Computer Science at IIT chicago.

About

In this weblog I will share all the technical things related to computer science, that I learn from diverse resources and the educational experience in my graduate school.

Subscribe

Recent Posts

LinkedIn Profile

View Vignesh M P N's profile on LinkedIn

Visitors


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: