Chapter 3

Array in Data Structure

What is an Array?

 An array is defined as the collection of similar type of data items stored at

contiguous memory locations.
 Arrays are the derived data type in C programming language which can store
the primitive type of data such as int, char, double, float, etc.
 It also has the capability to store the collection of derived data types, such as
pointers, structure, etc.
 The array is the simplest data structure where each data element can be
randomly accessed by using its index number.

Properties of Array

The array contains the following properties.

 Each element of an array is of same data type and carries the same size, i.e.,
int = 4 bytes.
 Elements of the array are stored at contiguous memory locations where the
first element is stored at the smallest memory location.
 Elements of the array can be randomly accessed since we can calculate the
address of each element of the array with the given base address and the size
of the data element.
Advantage of C Array

1) Code Optimization: Less code to the access the data.

2) Ease of traversing: By using the for loop, we can retrieve the elements of an
array easily.

3) Ease of sorting: To sort the elements of the array, we need a few lines of code
only.

4) Random Access: We can access any element randomly using the array.

Disadvantage of C Array

1) Fixed Size: Whatever size, we define at the time of declaration of the array, we
can't exceed the limit. So, it doesn't grow the size dynamically like LinkedList
which we will learn later.

Declaration of C Array

We can declare an array in the c language in the following way.

data_type array_name[array_size];

Now, let us see the example to declare the array.

int marks[5];

Here, int is the data_type, marks are the array_name, and 5 is the array_size.
Initialization of C Array

The simplest way to initialize an array is by using the index of each element. We
can initialize each element of the array by using the index. Consider the following
example.

marks[0]=80;//initialization of array

marks[1]=60;

marks[2]=70;

marks[3]=85;

marks[4]=75;

Representation of an array
We can represent an array in various ways in different programming languages.

As an illustration, let's see the declaration of array in C language

As per the above illustration, there are some of the following important points -

 Index starts with 0.

 The array's length is 10, which means we can store 10 elements.
 Each element in the array can be accessed via its index
Types of Array
In c programming language, arrays are classified into two types. They are as follows...

 Single Dimensional Array/One Dimensional Array

 Multi Dimensional Array

1.Single Dimensional Array

 In c programming language, single dimensional arrays are used to store list of values of
same data type.
 In other words, single dimensional arrays are used to store a row of values.
 In single dimensional array, data is stored in linear form. Single dimensional arrays are
also called as one-dimensional arrays, Linear Arrays or simply 1-D Arrays.

Declaration of Single Dimensional Array

We use the following general syntax for declaring a single dimensional array...

data_type array_name[array_size];

Initialization of Single Dimensional Array

Accessing Elements of Single Dimensional Array

 In c programming language, to access the elements of single dimensional

array we use array name followed by index value of the element that to be
accessed.
 Here the index value must be enclosed in square braces.
 Index value of an element in an array is the reference number given to each
element at the time of memory allocation.
  The index value of single dimensional array starts with zero (0) for first
element and incremented by one for each element. The index value in an
array is also called as subscript or indices.

We use the following general syntax to access individual elements of single

dimensional array...

arrayName[indexvalue]

example

marks[2] =80;

Finding Address of an element in One Dimensional Array

Consider the array declaration A[Lb……………..Ub], base address is BA, C-size

of an array and Lb and Ub are the lower and upper bound of an array.

Then address of the ith element can be find out using following formulas

Loc(a[i]) = BA + (i – Lb) * C

Example: Suppose following array with its base address 1000 is given then
address of the element at a[4] will be 1008,

int a [5] = {10,20,30,40,50}

Loc (a4) = BA + ( i – Lb) * c

= 1000 + ( 4 – 0 )*2

= 1000 + 8

= 1008

Multi Dimensional Array

In simple words, an array created with more than one dimension (size) is called as
multi dimensional array.
Multi dimensional array can be of two dimensional array or three dimensional
array or four dimensional array or more...

Most popular and commonly used multi dimensional array is two dimensional
array.

The 2-D arrays are used to store data in the form of table. We also use 2-D arrays
to create mathematical matrices.

Declaration of Two Dimensional Array

We use the following general syntax for declaring a two dimensional array.

datatype arrayname[rowsize][columnsize];
Example

int matrix[2][3]

Initialization of Two Dimensional Array

We use the following general syntax for declaring and initializing a two dimensional array with
specific number of rows and columns with initial values.

datatype arrayName [rows][colmns] = {{r1c1value, r1c2value, ...},{r2c1, r2c2,...}...} ;

Example

int matrix[2][3] = { {1, 2, 3},{4, 5, 6} } ;

Accessing Individual Elements of Two Dimensional Array

In a c programming language, to access elements of a two-dimensional array we use array name
followed by row index value and column index value of the element that to be accessed. Here the
row and column index values must be enclosed in separate square braces. In case of the two-
dimensional array the compiler assigns separate index values for rows and columns.
We use the following general syntax to access the individual elements of a two-dimensional
array...

arrayName[rowindex][colindex];

Example

matrix[0][1] = 2 ;

Address of an element of any array say “A[ I ][ J ]” is calculated in two forms as given:
(1) Row Major System (2) Column Major System

Row Major System:

The address of a location in Row Major System is calculated using the following formula:

Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]

Column Major System:

The address of a location in Column Major System is calculated using the following formula:

Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]

Where,

B = Base address

I = Row subscript of element whose address is to be found

J = Column subscript of element whose address is to be found

W = Storage Size of one element stored in the array (in byte)

Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)

Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)

M = Number of row of the given matrix

N = Number of column of the given matrix

Example for Row Major Order

Operations on Data Structure
1) Traversing: Every data structure contains the set of data elements. Traversing the data
structure means visiting each element of the data structure in order to perform some specific
operation like searching or sorting.

Example: If we need to calculate the average of the marks obtained by a student in 6 different
subject, we need to traverse the complete array of marks and calculate the total sum, then we will
devide that sum by the number of subjects i.e. 6, in order to find the average.
2) Insertion: Insertion can be defined as the process of adding the elements to the data structure
at any location.

If the size of data structure is n then we can only insert n-1 data elements into it.

3) Deletion: The process of removing an element from the data structure is called Deletion. We
can delete an element from the data structure at any random location.

If we try to delete an element from an empty data structure then underflow occurs.

4) Searching: The process of finding the location of an element within the data structure is
called Searching. There are two algorithms to perform searching, Linear Search and Binary
Search. We will discuss each one of them later in this tutorial.

5) Sorting: The process of arranging the data structure in a specific order is known as Sorting.
There are many algorithms that can be used to perform sorting, for example, insertion sort,
selection sort, bubble sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of similar type of
elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is
called merging

1) Traversing an Array
Traversal operation in array or simply traversing an array means, Accessing or printing each
element of an array exactly once so that the data items (values) of the array can be checked or
used as part of some other operation or process (This accessing and processing is sometimes
called “visiting” the array).

Accessing or printing of elements always takes place one by one.

Algorithm for Traversing an Array

Step 01: Start

Step 02: [Initialize counter variable. ] Set i = LB.

Step 03: Repeat for i = LB to UB.

Step 04: Apply process to arr[i].

Step 05: [End of loop. ]

Step 06: Stop

Program for Traversing

#include<stdio.h>

void main()

int i ;

int arr[5]={1, 9, 17, 4, 3}; //declaring and initializing array

printf("The array elements are: ");

for(i=0;i<5;i++)

printf("\narr[%d]= %d", i, arr[i]);

2) Insertion in Array

Insertion in the operation in which a new value is added at a particular place in an array.

Algorithm to insert an element in Array

Input

int arr[5] = {10, 20, 30, 40, 50}

Element = 100 position = 2.

Output

{10, 20, 100, 30, 40, 50}

Input

int arr[5] = {10, 20, 30, 40, 50}

Element = 100 index = -1 or 10.

Output

"Invalid Position"

Algorithm

1. Get the element value which needs to be inserted.

2. Get the position value.

3. Check whether the position value is valid or not.

4. If it is valid,

Shift all the elements from the last index to position index by 1 position to the right.

insert the new element in arr[position]

5. Otherwise,

Invalid Position

Algo

A is an array N is number of elements (size)

Element is a data element

Pos is the location of the element to be inserted.

Insertion (A, N, Element, Pos)

Step 1: for i = N-1(index of last element in array) down to Pos repeat step 2

Step 2: A[i+1] = A[i] End for

Step 3: A [Pos] = Element

Step 4: N = N + 1

Example
1. We need to insert element 100 at position 2.

2. Move all the elements from the last index(4) to the position(2) to one position right.

arr[4] (30) will be placed in arr[5].

arr[3] (78) will be placed in arr[4].

arr[2] (5) will be placed in arr[3].

3. Finally, the element 100 is placed at the position 2.

3) Deletion in Array

Deletion operation in Array or delete an element from an Array simply means, Removing an
existing element from a specific position of an array.

Algorithm to Delete an element in Array

a : Name of the array.

N : total number of elements in the array

i : Loop counter or counter variable for the for loop.

pos : The position from where we wish to delete the element.

The following algorithm deletes a data element from a specific position pos (position specified
by the programmer) of a linear array „a„.

Step 01: Start

Step 02: [Initialize counter variable] Set i = pos

Step 03: Repeat Step 04 and 05 for i = pos to i <= N

Step 04: [Move ith element backward (left). ] set a[i] = a[i+1]

Step 05: [Increase counter. ] Set i = i + 1

Step 06: [End of step 03 loop. ]

Step 07: [Reset size of the array. ] set N = N - 1

Step 08: Stop

Algorithm

1. Find the given element in the given array and note the index.
2. If the element found,
Shift all the elements from (index + 1) by 1 position to the left.
Reduce the array size by 1.
3. Otherwise, print "Element Not Found"

Example
Let's take an array of 5 elements.
1, 20, 5, 78, 30.
If we remove element 20 from the array, the execution will be
Note – Merging, Searching and sorting operations are discussed in separate chapter