HN Explorer

Difference between data structure and ADT?

2 points by yearsinrock ↗ HN
I was reading my semester book fro data structures and algorithms.I am confused between adt and data structure.what is the exact difference between them? + can anyone give explain it with a suitable example?

3 comments

[ 0.30 ms ] story [ 10.2 ms ] thread
corentin
An abstract data type is the specification of an interface; it's a set of operations whose behavior is defined.

A data structure describes how data is organized in memory.

Let's imagine a stack ADT with two operations: push and pop. We can decide to implement this ADT using, say, an array or a linked list. In either case, its operation will be the same (that is, you'll get the same results; but its time and space properties may be different).

yearsinrock
does that mean in an adt the implementation is important and the the realization is hidden and in data structure the result as well as how it is obtained is important.?
corentin
You seem to imply that abstract data types and data structures are in some way similar (or related). It's not the case; an ADT is not a kind of, nor an alternative to, a data structure (and vice versa). They are different things for different purposes, just like an algorithm isn't the same thing as a data structure.

I acknowledge that their names can be confusing (both contain the word "data"). "data structure" isn't a bad name; we understand that it's about how data is organized. But "abstract data type" is less clear, indeed.

edit: I think I found what may confuse you: I guess it's a visualization problem. When you're visualizing a data structure, it probably looks like boxes connected to each other with arcs. And I think your book has nice pictures for ADTs, too (stacks, queues, etc. drawn using boxes and maybe arcs as well). Whereas it's clear that an algorithm is very different from a data structure because it's described using pseudo-code. Forget the graphical representation for ADTs; think of them instead as a list of "rules" of the form "when I dequeue something from a queue, I get the last item that was enqueued".