Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: Dec 2013

ADT

• ADT stands for Abstract Data Type.
• An abstract data type is a type with associated operations, but whose representation is hidden.
• The idea of an ADT is to separate the notions of specification (what kind of thing we're working with and what operations can be performed on it) and implementation (how the thing and its operations are actually implemented).
• There are two views of an abstract data type in a procedural language like C. One is the view that the rest of the program needs to see: the names of the routines for operations on the data structure, and of the instances of that data type. The other is the view of how the data type and its operations are implemented.
• The advantages of ADT are that the code becomes more readable, its implementation can be changed for better efficiency without affecting the rest of the code and they can be reused in different programs.

• Common ADTs are stacks, queues, binary trees, etc.

  For example, a stack uses the LIFO mechanism for storing and removing the data. The last element that is inserted is the first element to be removed from the stack. Common operations are pushing an element on top of the stack, popping the last element inserted, finding/seeking the current top of the stack, etc. These functions or operations can be defined first and then these operations can be used whenever required in the program.

• The implementation of a stack can be by either an array or a linked list. It doesn't affect the logic of the rest of the program.