Page 7 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes integers, characters etc. can be directly created and manipulated in a programming language,
the responsibility of creating the structured type data items remains with the programmers
themselves. Accordingly, programming languages provide mechanism to create and manipulate
structured data items.

1.1 Abstract Data Type (ADT)

Before we move to abstract data type let us understand what data type is. Most of the languages
support basic data types viz. integer, real, character etc. At machine level, the data is stored as
strings containing 1’s and 0’s. Every data type interprets the string of bits in different ways and
gives different results. In short, data type is a method of interpreting bit patterns.

Every data type has a fixed type and range of values it can operate on. For example, an integer
variable can hold values between the min and max values allowed and carry out operations like

addition, subtraction etc. For character data type, the valid values are defined in the character
set and the operations performed are like comparison, conversion from one case to another etc.

There are fixed operations, which can be carried out on them. We can formally define data types

as a formal description of the set of values and operations that a variable of a given type may

take. That was about the inbuilt data types. One can also create user defined data types, decide

the range of values as well as operations to be performed on them. The first step towards creating
a user defined data type or a data structure is to define the logical properties. A tool to specify the

logical properties of a data type is Abstract Data Type.

Data abstraction can be defined as separation of the logical properties of the organization of
programs’ data from its implementation. This means that it states what the data should be like.
It does not consider the implementation details. ADT is the logical picture of a data type; in

addition, the specifications of the operations required to create and manipulate objects of this
data type.

While defining an ADT, we are not concerned with time and space efficiency or any other
implementation details of the data structure. ADT is just a useful guideline to use and implement
the data type.
An ADT has two parts:
1. Value defi nition

2. Operation defi nition.

Value definition is again divided into two parts:
1. Defi nition clause
2. Condition clause
As the name suggests the definition clause states the contents of the data type and condition

clause defines any condition that applies to the data type. Definition clause is mandatory while

condition clause is optional.
Example: An integer variable can contain only integer values while a character variable
can contain only a valid character value.
To understand the above clauses let us consider the ADT representation of integer data type.

In the value definition the definition clause will state that it can contain any number between

minimum integer value and the maximum integer value allowed by the computer while the
condition clause will impose a restriction saying none of the values will have a decimal point.

2 LOVELY PROFESSIONAL UNIVERSITY