I wanted to write an article on this distinction because I think it's a useful one, but as I thought this through there are areas that are still a bit vague to me too.
What is an Abstract Data Type (ADT)
An ADT is like an interface in object oriented languages, but it also includes semantics of what these operations do.
So for example a Stack is an object that has push and pop operations for pushing data onto it and popping data off, with first-in-last-out (FILO) semantics, meaning that items are returned by invocations of pop in the reverse order they were pushed.
This says nothing about how the data is stored internally. It could be a linked list, it could be an automatically growing array, or whatever other representation you like.
Where do you draw the line
But I'm not sure where you draw the line. For example, a linked list could be seen as an ADT where each list item has a next operation that yields the next item in the list. But then it's also a data structure as it describes structured data with pointers pointing to the memory address of the next item.
Come to think of it, maybe the most useful conclusion is that there is both a linked list ADT and a linked list data structure. Because you could implement the linked list ADT with an array, even though that wouldn't be very useful.
Top comments (0)