Where do you draw the line between data structures and abstract data types (ADTs)

_bigblind profile image Frederik πŸ‘¨β€πŸ’»βž‘οΈπŸŒ Creemers ・1 min read

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.

Posted on by:

_bigblind profile

Frederik πŸ‘¨β€πŸ’»βž‘οΈπŸŒ Creemers


I'm never sure what to put in a bio. If there's anything you want to know, don't be afraid to ask!


markdown guide