Is my understanding of abstract data-types correct (ADTs)?

After reading lots of pages on various sites, I came to the conclusion that abstract data-type (ADT) helps to separate the use of a data-structure from its implementation. We can easily map the data into a data-structure by using an already available abstraction. And this abstraction is called ADT. Please tell me if I have understood this correctly. Also if you can give a small example, it will be very helpful. If you prefer to give any code in your example, C or Python would be helpful for me.

Addition: They are a very special implementation of data abstraction. What separates them from other instances of abstractions is that ADTs are theoretical constructs. Theoretical constructs that help map or represent data in a desired data structure. They have attributes or operations associated with them. These operations may be applied on the data that has been mapped into the ADT. How the data is actually stored inside the ADT or how the operations work are kept hidden.

EDIT: I had previously said, “ADT is like the blueprint of a data-structure”. A few of the answers have explained why it’s not. I didn’t have a clear comprehension of what a ‘blueprint’ is and that was the reason for using the term. So, I’ve now removed it from my original text.

4

This is just a gist on the subject, I strongly suggest following the links herein.

An abstract data type defines a class of abstract objects which is completely characterized by the operations available on those objects. This means that an abstract data type can be defined by defining the characterizing operations for that type.” Liskov, Zilles: Programming with abstract data types

Given the informal definition above, the following pseudo-code can be seen as an ADT:

type stack;
stack stack_create();
void stack_push(stack, T);
T stack_pop(stack);

One point is that nothing is known about stack objects, except what can be inferred by the operations available for it — in the case above, stack_create, stack_push and stack_pop. Every single bit of implementation and structure detail is left to the implementation side.

Now, take an OO/python class called Stack with the methods push and pop.

class Stack:

    def __init__(self):
       ...
    def push(self, element):
       ...
    def pop(self):
       ...

If its clients know that there is a class called Stack and they have access to it, one way to see it is that the objects are characterized by the fact that they are instances of the class Stack whose structure contains push and pop fields — regardless of the fact that they are callable. Clients also know that they can inherit from Stack to create something else and so on.

That is, much more is known/exposed to clients. Therefore, this Stack type is much less abstract than the previous one (it is exposed as a concrete structure with two fields, has a class with which you can do inheritance, etc). Consequently, one could argue this Stack type is not an Abstract Data Type conforming to the given definition. To be more strict, one would have to write something like this:

def create_stack():
   ...
def stack_push(stack, element):
   ...
def stack_pop(stack):
   ...

And here is a possible implementation of it (in the case below, if you already have the class above and just want to make it an ADT, it is just a wrapper):

def create_stack():
   retur Stack()
def stack_push(stack, element):
   return stack.push(element)
def stack_pop(stack):
   return stack.pop()

Now the client only knows the operations and their interfaces and use them (and only them) to infer what is the type “stack”. From outside, nothing is known about the actual implementation and structure of a stack (unless they breach the abstraction by inspecting the structure of the result of create_stack).

Similarly, in C, you could mimic this by putting these function declarations on a .h header file (using a forward declaration standing as the stack type, or simply void*), and then, putting the struct definition and function implementations in the .c file.

Note on type systems: All the above, of course, are not in the context of languages with static type checking and good type systems — such language may need to provide certain instruments to make reasonable ADTs possible. Furthermore, the way this theme is exposed in the paper cited above, “strong” type checking appears to be a matter of author preference alone; I did not see them being discussed or shown to be a requirement of ADTs — the text actually seems to be careful in discussing type checking as something related but not essential. Plus, the explanation of a “C approach to ADT” (see above) was given by William Cook, the researcher who wrote Object-Oriented Programming Versus Abstract Data Types. [edit] On the other hand, Cook writes:

Abstract data types depend upon a static type system to enforce type abstraction. It is not an accident that dynamic languages use objects instead of user-defined abstract data types. Dynamic languages typically support built-in abstract data types for primitive types; the type abstraction here is enforced by the runtime system.

You have understood this correctly. ADTs are portable, theoretical constructs that can then be implemented in most any given programming language.

Example: Stack

A Stack as an ADT is a list of some type that provides Last In, First Out (LIFO) access to its data members. Thus it can only be accessed at one point, the “top” of the stack.

In Python that’d look something like:

class Stack:

    def __init__(self): # initializes the stack with an empty list to hold stuff
        self.list = []

    def push(n): # pushes item n onto the stack
        stack.list.append(n)

    def pop: # removes the "top" item from the stack
        del stack.list[-1]

    def peek: # looks at the top item of the stack
        view = stack.list[-1]
        return view

And that should about do it for one way to implement a basic stack. I’ve not tested this code so use at your own risk. Python in fact expects you to use lists as stacks by default so it’s covered in the tutorial documentation. There’s even a built in “pop” method.

Generally, you’d implement a stack as either an array or a linked list. The array can be useful if you want a little bit less memory overhead and it’s generally easier to code. However, a list based stack can expand much more easily and quickly.

8

Unfortunately there is a lot of confusion about Abstract Data Types and Objects.

I think that the OP is using the phrase “abstract datatype” as if it meant “data abstraction” or just in the general sense of defining abstract data.

Abstract Data Types are a very specific implementation of Data Abstraction, and is best realized in the language ML. Objects are another form of Data Abstraction.

You can read more about it in my papers here:
http://www.cs.utexas.edu/~wcook/publications.htm#oo

2

An abstract data type is a mathematical abstraction used to describe
algorithms and prove them. The idea of an algorithm or of an abstract
data type is thus rather independant from any computer language or
even from the availability of a computer. (I am not sure if this is your idea of a blueprint.)

Of course, computers and programming language are a very important
application field of algorithms, and it is quite common to implement
an algorithm in a given computer language. (Lines are even blurrier
since many programmers will not even make a strong distinction between
an abstract algorithm and its implementation in a given computer
language.) So, in order to implement these abstract algorithms
described in terms of abstract data types, programmers need to
implement abstract data types.

It is a common case, that am implementation of an abstract data type
has more properties than required, and one may accidentally use one in
a program, which leads to a bug if the implementation is modified.

While formally proving a complex program is typically not worth the
effort, it is important to get a confidence that a program
accomplishes its purpose and functions correctly. (There is a
parallel with mathematics, since mathematical proofs can be written at
various levels of details, depending of the audience or the purpose.)
The use of appropriate abstract data types is very important for this,
because by introducing the adequate abstractions, one makes not only
the program easier to reason about or to describe but one also
demonstrates its good understanding of the problem and the solution
brought by the program.

The computer language OCaml has the ability to expose abstract data
types,
which are types whose definition is kept private to some
module, which helps understanding and using abstract data types.

I’ll disagree with everyone else and say that you don’t have it quite right. 🙂

It is like the blueprint of the datastructure.

No, it’s actually the opposite of that: it’s a photograph from the outside of a device or a building showing the doors and knobs with instructions on what to expect when you use them.

Secondly, ADT’s are a lingua franca: a common language for discussing one kind of frequently used software component.

IMO the best lesson on ADT’s and their potential implementations is the Javadocs for the container classes. Look at the interfaces and abstract classes. These are the ADT’s. For example, the Queue.

2

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật