Data Structures and Algorithms

(DSAs)

Arrays, Pointers and Structures

Lecture 2
Outline
As derived Data types
Arrays
Array representation
Array Operations
 Traverse
 Insertion
 Deletion
 Search
 Update

Array Assignment Data types.

Pointers
Structures
As Derived data types
These data types implementation is
independent as they can be implemented in
one or the other way. They are normally built
by the combination of primary or built-in data
types and associated operations on them.
Some include;
Queue
Array
Stack
List
Arrays
Array is a container which can hold a fixed
number of items and these items should be of
the same type.
Most of the data structures make use of
arrays to implement their algorithms.
Following are the important terms to
understand the concept of Array.
Element : Each item stored in an array is
called an element.
Index : Each location of an element in an
array has a numerical index, which is used to
identify the element.
Arrays
In computer science, the obvious way to store
an ordered collection of items is as an array.
Array items are typically stored in a sequence of
computer memory locations, but to discuss
them, we need a convenient way to write them
down on paper. We can just write the items in
order, separated by commas and enclosed by
square brackets.
Thus,
[2, 5, 6, 89, 0, 5, 3, 25, 76]
Is an example of an array of integers.
 Arrays
If we call the above array K, we can write it as:

K = [2, 5, 6, 89, 0, 5, 3, 25, 76]

This array K has 9 items, and hence we say that
its size is 9.
In everyday life, we usually start counting from 1.
When we work with arrays in computer science,
however, we more often (though not always) start
from 0. Thus, for our array K, its positions are 0;
1; 2; : : : ; 7; 8.
The element in the 8th position is 25, and we use
the notation K[8] to denote this element.
Arrays
Generally, for any integer i denoting a position,
we write K[i] to denote the element in the ith
position.
This position i is called an index (or indices).
Then, in the above example,
K[0] = 2,
K[1] = 5,
K[2] = 6,
K[3] = 89,
K[4] = 0,
K[5] = 5 , and so on.
Arrays Representation
Arrays can be declared in various ways in
different languages. For illustration, let's take
C array declaration.

Hence,
Array Operations
Following are the basic operations supported by an
array;
Traverse − Prints all the array elements one by one.

Insertion − Adds an element at the given index.

Deletion − Deletes an element at the given index.

Search − Searches an element using the given

index or by the value.

Update − Updates an element at the given index.

 Array assignment data types
In C, when an array is initialized with size, then
it assigns defaults values to its elements in
following order.
Insertion Operation
Insert operation is to insert one or more data
elements into an array.

Based on the requirement, a new element can

be added at the beginning, end, or any given
index of array.

On the next slide, we see a practical

implementation of insertion operation, where
we add data at the end of the array
Array insertion Algorithm
Let Array be a linear unordered array of MAX
elements.
Let LA be a Linear Array (unordered) with N
elements and K is a positive integer such that
K<=N. Following is the algorithm where ITEM
is inserted into the Kth position of LA
 Array insertions
In the previous section, we have learnt how the
insertion operation works. It is not always
necessary that an element is inserted at the end
of an array.

Following can be a situation with array

insertion;
Insertion at the beginning of an array
Insertion at the given index of an array
Insertion after the given index of an array
Insertion before the given index of an array
Insertion at the beginning of an Array
When the insertion happens at the beginning,
it causes all the existing data items to shift
one step downward.

On the next slide, we design and implement

an algorithm to insert an element at the
beginning of an array.
 Algorithm – insertion at the beginning
We assume A is an array with N elements. The
maximum numbers of elements it can store is
defined by MAX. We shall first check if an array
has any empty space to store any element and
then we proceed with the insertion process.
Insertion at a given Index of Array
In this scenario, we are given the exact location
(index) of an array where a new data element
(value) needs to be inserted.
First we shall check if the array is full, if it is
not, then we shall move all data elements from
that location one step downward.
This will make room for a new data element.
Algorithm
We assume A is an array with N elements.
The maximum numbers of elements it can
store is defined by MAX.
Insertion After a Given Index
In this scenario we are given a location
(index) of an array after which a new data
element (value) has to be inserted.

Only the seek process varies, the rest of the

activities are the same as in the previous
example.
Algorithm
We assume A is an array with N elements. The
maximum numbers of elements it can store is
defined by MAX.
Insertion Before a given Index
In this scenario we are given a location
(index) of an array before which a new data
element (value) has to be inserted.

This time we seek till index-1, i.e., one

location ahead of the given index.

Rest of the activities are the same as in the

previous example.
Algorithm
We assume A is an array with N elements. The
maximum numbers of elements it can store is
defined by MAX.
Deletion Operation
Deletion refers to removing an existing
element from the array and re-organizing all
elements of that array.

Algorithm:
Consider LA is a linear array with N elements
and K is a positive integer such that K<=N.

On the next slide is the algorithm to delete an

element available at the Kth position of LA.
Algorithm – deletion operation
Search Operation
You can perform a search for an array
element based on its value or its index.

Algorithm:
Consider LA is a linear array with N
elements and K is a positive integer such that
K<=N.

On the next slide is the algorithm to find an

element with a value of ITEM using
sequential search.
Algorithm – Search Operation
Update Operation
Update operation refers to updating an existing
element from the array at a given index.

Algorithm:
Consider LA is a linear array with N elements
and K is a positive integer such that K<=N.

On the next slide is the algorithm to update an

element available at the Kth position of LA.
Algorithm – Update Operation
Pointers
Any variable we deal with has memory location(address)
to store its value, and the pointer is something like a
variable that holds that memory address of the variable.
If we have variable “a”, its address will be represented as
“&a”.
so if we have a pointer “p” to points to the address of a
variable “a”.
p=&a; //the variable p stores the address of variable a
and if we want to access the value of the variable “a”
using the address, this will be as the following:-
*(&a) or *p
the strike (*) is used to access the value found in the
address of the variable (a)
Pointers
Pointers
In C language, when we declare a pointer, it
follows the following format:

type *var-name;

where:-
type is the type of data accessed by the
pointer.
var_name is the name of the pointer
the strike (*) means we will access the value
that the address stored in the pointer has
Pointer
Null Pointer:-
It’s better to assign null to the pointer when
we initialize it, and the value that can be
accessed by this pointer will be zero.
int *p = null;
What we do with Pointers
We can use pointers as arguments of a
function or as a return from the function.

We can create an array of pointers, this array

will be like normal arrays but its elements are
from type pointer.

we can use pointer of the pointer, which

means:
Structures
Most of the operators we have been using on other
types, like mathematical operators ( +, %, etc.) and
comparison operators (==, >, etc.), do not work on
structures. Actually, it is possible to define the
meaning of these operators for the new type.

On the other hand, the assignment

operator does work for structures. It can be used in
two ways: to initialize the instance variables of a
structure or to copy the instance variables from one
structure to another. An initialization looks like this:
Point blank = { 3.0, 4.0 };
Structures
The values in squiggly braces get assigned to the
instance variables of the structure one by one, in
order. So in this case, x gets the first value
and y gets the second.

Unfortunately, this syntax can be used only in an

initialization, not in an assignment statement. So
the following is illegal.

Point blank;
blank = { 3.0, 4.0 }; // WRONG !!
Structures
You might wonder why this perfectly
reasonable statement should be illegal; I’m not
sure, but I think the problem is that the
compiler doesn’t know what type the right
hand side should be. If you add a typecast:
Point blank; blank = (Point){ 3.0, 4.0 };
It is legal to assign one structure to another.
For example:
Point p1 = { 3.0, 4.0 };
Point p2 = p1;
cout << p2.x << ", " << p2.y << endl;
The output of this program is 3, 4.
Questions