Page 14 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 1: Introduction to Data Structure and Arrays

1.4 Implementation of Data Structure Notes

In this unit, we will discuss the distinguish between the usage and the implementation of a data
structure. This difference is crucial in understanding the concept of the separation, defi nition and
use that should be practiced for designing good software. We then present the implementation
of a few data structures.
Our main purpose of this course is to describe important data structures and to develop algorithms
for the various operations on such data structures.

While presenting a data structure we shall discuss ways to represent it in the computer memory.
In many cases, we shall assume array to be the primitive structure to house other data structures.
In this context, we use the term array to mean a one-dimensional array having elements of a
particular type. Every high level programming language includes facilities to handle arrays and
as such implementation of a data structure housed in an array does not offer any problem. Even
in assembly or machine languages, a block of contiguous storage locations can be conveniently
considered to be an array for the said purpose. Borrowing the notation of C language, we shall
denote an array type as follows:
<base type> <array name>[<number of elements>];
Thus,

int A[50];
will denote an array of 50 elements where A is the name of the array. An individual element of
this array will be denoted by
A[i] where 0<i<50.
In general, an element will be shown as
<array name>[<index>]
where <0> <= <index> < <number of elements>
In many cases, the relations among the elements of a data structure need not be explicitly
represented because these are implicitly known. When the relations need to be explicitly
represented, there are two possible approaches. Either the relations are represented separately
(possible as another data structure) or the elements are augmented to include additional fi elds
that represent structural information. Later, we shall see many examples of both these approaches
and as such, we do not consider any example at this stage.
It is clear from the above discussion that sometimes an element will also include structural
information. In such cases, we shall call it a node to make a minor distinction between the two.
Thus the distinction between a node and an element (or a component) is that a node is an element
(or a component) plus the structural information (if any) carried into it.

Task Every high level programming language includes facilities to handle arrays
what about machine level and assembly level languages.

1.5 List ADT’s

An array is an example of list. Arrays have fixed size, which is declared and fixed at the start of
the program, and therefore cannot be changed while it is running.
Example: Suppose an array of size 5 has been declared at the start of the program.

LOVELY PROFESSIONAL UNIVERSITY 9