Sign in to follow this  

Abstract Data Types (Primarily in Java)

This topic is 3312 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. One of my units for Uni is centred on Data Structures (in Java). It discusses Abstract Data Types (ADTs). The meaning of an ADT seem to vary between lecture slides and the text book, even though the lecture slides are derived from the text book. The text book says that an Abstract Data Type has a set of values and operations, and that: "data representation plays no part in the characterization of an ADT. Of course, the ADT must have a data representation, but it is private." Then, in the lecture slides, a java interface class is used to illustrate a possible "contract" for a Stack class. So on one hand I'm being told that an ADT must have a private data representation, and on the other hand an interface (which cannot contain mutable data members) is an ADT. This frustrates me, because if I was to walk into an exam and be asked "What is an ADT?", I wouldn't know. I thought that an ADT would be an interface, but apparently it can be a concrete class as well... so I'm curious what an ADT really is? Cheers.

Share this post


Link to post
Share on other sites
As I understand it, an ADT is a a data type that isn't necessarily defined by a concrete instance.

These data types may have private members associated with them, and an interface to manipulate (mutators, accessors) those private members, but they aren't defined by what private members they have or how their interface is implemented.

they are defined only by their behavior.

ie, a stack is a first in, first out data structure

Thusly, a stack is defined by its behavior, not by what kind of data it holds, or what methods are available to use it.

Hope that helped.

Share this post


Link to post
Share on other sites
Quote:
Original post by nolsen01
As I understand it, an ADT is a a data type that isn't necessarily defined by a concrete instance.

These data types may have private members associated with them, and an interface to manipulate (mutators, accessors) those private members, but they aren't defined by what private members they have or how their interface is implemented.

they are defined only by their behavior.

ie, a stack is a first in, first out data structure

Thusly, a stack is defined by its behavior, not by what kind of data it holds, or what methods are available to use it.

Hope that helped.
Hmmm... not really the kind of answer I was looking for. I'm curious to know the concise, universal meaning of an abstract data type.

The lecture slides say that a Set, String, etc is an ADT.. but they are concrete instances.

I do agree with you, but it's still too fuzzy to put into a sentence. (Note I'm not looking for exam answers, I'm just trying to find a definition that is widely agreed upon).

Share this post


Link to post
Share on other sites
A Set and a String are ADT's because they have certain defined behaviors.

If I created a String class, and you created a String class, chances are we would have designed them quite differently.

But as long as they have the same basic behaviors, they are still Strings.

If I were to try and formulate a formal definition of an ADT, I would say:

An ADT is a general set of rules, treated as an object, for how data is stored and manipulated.

Under that definition, a String is an ADT just like a Stack is an ADT.

Share this post


Link to post
Share on other sites
An abstract data type is not a language-level concept. It's not even an object-oriented concept. Therefore, attempting to describe it in terms of "interface", "class" or other similar language-level building blocks is bound to fail.

An abstract data type is a language-independent data type, defined not by its implementation in any particular language but rather by the theoretical operations it supports.

For instance, if you say that a stack allows pushing and popping values, where popping yields the last value pushed but not yet popped, as well as querying whether the stack is empty or not, then you have described the Stack ADT.

On the other hand, if you were to write:
interface Stack<E> 
{
void Push(E);
E Pop();
boolean Empty();
}
Then your code would not be an ADT, it would be a representation of that ADT in the Java programming language, just like this other one:
class Stack<E>
{
public Stack(Stack<E> pop, E top) { this.pop = pop ; this.top = top ; }
public final Stack<E> pop;
public final E top;
}


In practice, Java provides several implementations of various ADTs (such as lists or dictionaries) which are called "Abstract Data Types" because it's shorter than "Java Standard Library Representations of Abstract Data Type", but this is a derived meaning, not a primary one.

Share this post


Link to post
Share on other sites
Ok cheers for that guys... gives me more of an understanding of the true meaning and how I can now word my understanding of it.

Edit: The text I'm reading says that an ADT is also the values that comprise it... read:
Quote:
An ADT is characterized by:
- a set of values
- a set of operations [...]


what do you think about that statement?

Share this post


Link to post
Share on other sites
Basically they mean collections.

Factory.getType("something"); would give you a some structure which can do "something".

Think about it as about Abstract data classes and be done with. (Hopefully they explained to you the difference between a worker class and a data class)

Share this post


Link to post
Share on other sites
Quote:
Original post by Mybowlcut
Edit: The text I'm reading says that an ADT is also the values that comprise it... read:
Quote:
An ADT is characterized by:
- a set of values
- a set of operations [...]


what do you think about that statement?
This statement is a bit confusing, because "a set of values" could be taken to mean different things.

A mathematical definition of an Abstract Data Type is that it is first and foremost a Type. A type is a set of values (every value in that set is said to be "of that type") with several operations that either transform a value into another or map every value to an element of another set.

If you were looking for the mathematical definition of a stack over set E, then you would define it as the set S and operations (PUSH,POP,TOP,SIZE) such that:
  • Set S contains a single element, called ∅, such that SIZE(∅) = 0.
  • For every element s ∈ S, e ∈ E, there is a single s' = PUSH(s,e) ∈ S.
  • For every such s', the following are well-defined: POP(s') = s, TOP(s') = e and SIZE(s') = 1 + SIZE(s).


This would be the complete mathematical definition of a stack as an ADT. It is said to be abstract because the actual nature of S is not specified, only its properties.

The other possible meaning of set is that every implementation of the ADT contains values, which is again quite correct—for any but the most trivial ADT (the singleton) you need to represent state, and state is represented with values.

Share this post


Link to post
Share on other sites
One source of confusion is the traditional description of abstract data types as parametric types: for example not simply completing implementations of a "queue" but a "queue of T" ADT whose different possible implementations can be adapted to, and works in the same way for, any payload type T.

Strings are an unusual ADT in that they have a specific content (characters) and specific uses that imply easy but specialized operations (e.g. anything involving Unicode databases, such as lexicographical sorting), whole categories of sophisticated algorithms (e.g. search of substrings), peculiar performance issues (e.g. optimizing for large or small sizes or for common characters).

Share this post


Link to post
Share on other sites
The contents of strings are not specified—in formal theory, a string over an alphabet A is the Kleene closure of that alphabet (with the appropriate operators defined over it). So, you could define a string of 3D vertices if you wanted (and this often happens in computational topology programs, for instance).

Share this post


Link to post
Share on other sites

This topic is 3312 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this