LINEAR DATA

STRUCTURE
Subject Code 3130702
Array
▪ An array is a linear data structure. Which is a finite collection of similar data items stored in
successive or consecutive memory locations.

▪ For example an array may contains all integer or character elements, but not both.

▪ 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.

▪ Array is the simplest data structure where each data element can be randomly accessed
by using its index number.

▪ For example, if we want to store the marks of a student in 6 subjects, then we don't need
to define different variable for the marks in different subject. instead of that, we can define
an array which can store the marks in each subject at a the contiguous memory locations
Array
▪ So far we have worked primarily with primitive variables
▪ One characteristic of primitive variables is that they hold one value at a time.
▪ int x = 100 – can only hold one integer value at a time (100 at this time)

▪ Imagine that you want to hold the names of 100 people at a time.
▪ What would you have to do?
▪ Declare 100 variables, one for each name.
▪ Better solution: Use Arrays.
▪ Arrays are complex variables that can hold multiple values of the same data type.
▪ Now we can declare a single array that holds all the names.
Array
▪ To declare an integer array:
int[] numbers;
▪ It is just like declaring any primitive variable, EXCEPT for the[] between the data type and the
identifier.
▪ Just like any other object, this does not create the array, it creates a reference variable that can point
to an array.
▪ To create an array object for this reference variable:
numbers = new int[6];
▪ The number inside of the square brackets is called the array’s size declarator.
▪ An array’s Size Declarator indicates the number of elements, or values the array can hold.
▪ Individual values inside of an array are called elements.
▪ So the numbers array can hold 6 integers.
▪ You can declare and create on the same line like any other object:
int[] numbers = new int [6];
Array
▪ Each array can be accessed by using array index and it is must be positive integer value enclosed in
square braces

▪ This is starts from the numerical value 0 and ends at 1 less than of the array index value.

▪ For example an array[n] containing n number of elements are denoted by

array[0],array[1],…..array[n-1]. where ‘0’ is called lower bound and the ‘n-1’ is called higher bound
of the array.
Properties of the Array

▪ Each element is of same data type and carries a 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 data element.
Advantages of Array

 Array provides the single name for the group of variables of the same type therefore, it is
easy to remember the name of all the elements of an array.

 Traversing an array is a very simple process, we just need to increment the base address
of the array in order to visit each element one by one.

 Any element in the array can be directly accessed by using the index.
Array
▪ Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare
one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to
represent individual variables. A specific element in an array is accessed by an index.

▪ All arrays consist of contiguous memory locations. The lowest address corresponds to the first
element and the highest address to the last element.
Declaring Arrays
▪ a programmer specifies the type of the elements and the number of elements required by
an array as follows −

▪ type arrayName [ arraySize ];

▪ This is called a single-dimensional array.

▪ The arraySize must be an integer constant greater than zero and type can be any valid C
data type.

▪ For example, to declare a 10-element array called balance of type double, use this
statement − double balance[10];

▪ Here balance is a variable array which is sufficient to hold up to 10 double numbers.

Initializing Arrays

▪ You can initialize an array in C either one by one or using a single statement as follows −
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};

▪ The number of values between braces { } cannot be larger than the number of elements
that we declare for the array between square brackets [ ].

▪ If you omit the size of the array, an array just big enough to hold the initialization is created.
Therefore, if you write double balance[] = {1000.0, 2.0, 3.4, 7.0, 50.0};

▪ You will create exactly the same array as you did in the previous example. Following is an
example to assign a single element of the array − balance[4] = 50.0;
Initializing Arrays
▪ The above statement assigns the 5th element in the array with a value of 50.0. All arrays have 0 as
the index of their first element which is also called the base index and the last index of an array will
be total size of the array minus 1. Shown below is the pictorial representation of the array we
discussed
Accessing Array Elements

▪ An element is accessed by indexing the array name. This is done by placing the index of
the element within square brackets after the name of the array. For example − double
salary = balance[9];

▪ The above statement will take the 10th element from the array and assign the value to
salary variable. The following example Shows how to use all the three above mentioned
concepts viz. declaration, assignment, and accessing arrays −

▪ Array is a container which can hold a fix 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.
 Array Representation

▪ Arrays can be declared in various ways in different languages. For illustration, let's take C array
declaration.

▪ Arrays can be declared in various ways in different languages. For illustration, let's take C array
declaration.
Array Representation
▪ As per the above illustration, following are the important points to be considered.

 Index starts with 0.

 Array length is 10 which means it can store 10 elements.

 Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9.
Types of Arrays

Array can be categorized into different types.

▪ One dimensional array

▪ Two dimensional array

▪ Multi dimensional array

One dimensional array

▪ One dimensional array is also called as linear array. It is also represents 1-D
array.
▪ the one dimensional array stores the data elements in a single row or column.
▪ The syntax to declare a linear array is as fallows Syntax:
▪ <data type> <array name> [size];
▪ Syntax for the initialization of the linear array is as fallows
▪ Syntax: <data type><array name>[size]={values};
▪ Example: int arr[6]={2,4,6,7,5,8}; Values array name
▪ Memory representation of the one-dimensional array
▪ a[0] a[1] a[2] a[3] a[4] a[5]
246758
100 102 104 106 108 110
The memory blocks a[0],a[1],a[2],a[3 ],a[4] , a[5] with base addresses
1,102,104,106,108, 110 store the values 2,4,6,7,5,8 respectively.
▪ Here need not to keep the track of the address of the data elements of an array to
perform any operation on data element.
▪ We can track the memory location of any element of the linear array by using the
base address of the array.
▪ To calculate the memory location of an element in an array by using formulae.
Loc (a[k])=base address +w(k-lower bound)
▪ Here k specifies the element whose location to find
▪ W means word length.
▪ Ex: We can find the location of the element 5, present at a[3],base address is
100, then
▪ loc(a[3]) =100+2(3-0)
=100+6
=106.
Two dimensional array
▪ A two dimensional array is a collection of elements placed in rows and columns.
▪ 2D array can be defined as an array of arrays. The 2D array is organized as
matrices which can be represented as the collection of rows and columns.
▪ The syntax used to declare two dimensional array includes two subscripts, of
which one specifies the number of rows and the other specifies the number of
columns.
▪ These two subscripts are used to reference an element in an array.
Syntax to declare the two dimensional array is as fallows

Syntax: <data type> <array name> [row size] [column size];

Syntax to initialize the two dimensional array is as fallows
Syntax: <data type> <array name> [row size] [column size]={values};
int arr[max_rows][max_columns];
▪ int num[3][2]={4,3,5,6,,8,9};
▪ or int num[3][2]={{4,3},{5,6},{8,9}};
▪ values column size row size array name data type
Representation of the 2-D array
Memory representation of 2-D array:
▪ Memory representation of a 2-D array is different from the linear array.
▪ in 2-D array possible two types of memory arrangements.
▪ They are Row major arrangement
How do we access data in a 2D array
▪ However, we can store the value stored in any particular cell of a 2D array to some
variable x by using the following syntax.
▪ int x = a[i][j];
▪ where i and j is the row and column number of the cell respectively.
▪ for ( int i=0; i<n ;i++)
▪ {
▪ for (int j=0; j<n; j++)
▪ {
▪ a[i][j] = 0;
▪ }
▪ }
Mapping 2D array to 1D array

▪ When it comes to map a 2 dimensional array, most of us might think that why this
mapping is required. However, 2 D arrays exists from the user point of view. 2D
arrays are created to implement a relational database table lookalike data
structure, in computer memory, the storage technique for 2D array is similar to
that of an one dimensional array.
▪ The size of a two dimensional array is equal to the multiplication of number of
rows and the number of columns present in the array. We do need to map two
dimensional array to the one dimensional array in order to store them in the
memory.
▪ A 3 X 3 two dimensional array is shown in the following image. However, this
array needs to be mapped to a one dimensional array in order to store it into the
memory.
There are two main techniques of storing 2D array elements into memory
• Row Major ordering
▪ In row major ordering, all the rows of the 2D array are stored into the memory
contiguously. Considering the array shown in the above image, its memory
allocation according to row major order is shown as follows.

▪ first, the 1st row of the array is stored into the memory completely, then the
2nd row of the array is stored into the memory completely and so on till the last
row.
▪ Column Major ordering

▪ According to the column major ordering, all the columns of the 2D array are
stored into the memory contiguously. The memory allocation of the array which is
shown in in the above image is given as follows.

▪ first, the 1st column of the array is stored into the memory completely, then the
2nd row of the array is stored into the memory completely and so on till the last
column of the array.
Basic Operations

Following are the basic operations supported by an array.

 Traverse − print 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.

Sparse Matrix

▪ A matrix can be defined as a two-dimensional array having 'm' columns and 'n'
rows representing m*n matrix. Sparse matrices are those matrices that have the
majority of their elements equal to zero. In other words, the sparse matrix can be
defined as the matrix that has a greater number of zero elements than the non-
zero elements.
Why do we need to use a sparse matrix instead of a simple matrix?
▪ We can also use the simple matrix to store the elements in the memory; then why
do we need to use the sparse matrix. The following are the advantages of using a
sparse matrix:
▪ Storage: As we know, a sparse matrix that contains lesser non-zero elements
than zero so less memory can be used to store elements. It evaluates only the
non-zero elements.
▪ Computing time: In the case of searching n sparse matrix, we need to traverse
only the non-zero elements rather than traversing all the sparse matrix elements.
It saves computing time by logically designing a data structure traversing non-
zero elements.
▪ Representing a sparse matrix by a 2D array leads to the wastage of lots of
memory. The zeroes in the matrix are of no use to store zeroes with non-zero
elements. To avoid such wastage, we can store only non-zero elements. If we
store only non-zero elements, it reduces the traversal time and the storage space.
Sparse Matrix Representation

▪ The non-zero elements can be stored with triples, i.e., rows, columns, and value.
The sparse matrix can be represented in the following ways:

▪ Array representation
▪ Linked list representation
Array Representation

▪ The 2d array can be used to represent a sparse matrix in which there are three
rows named as:
▪ Row: It is an index of a row where a non-zero element is located.
▪ Column: It is an index of the column where a non-zero element is located.
▪ Value: The value of the non-zero element is located at the index (row, column).
▪ Let's understand the sparse matrix using array representation through an
example.
▪ As we can observe above, that sparse matrix is represented using triplets, i.e.,
row, column, and value. In the above sparse matrix, there are 13 zero elements
and 7 non-zero elements. This sparse matrix occupies 5*4 = 20 memory space. If
the size of the sparse matrix is increased, then the wastage of memory space will
also be increased. The above sparse matrix can be represented in the tabular
form shown as below:
▪ In the above table structure, the first column is representing the row number, the
second
▪ column is representing the column number and third column represents the non-
zero value at index(row, column). The size of the table depends upon the number
of non-zero elements in the sparse matrix. The above table occupies (7 * 3) = 21
but it more than the sparse matrix. Consider the case if the matrix is 8*8 and there
are only 8 non-zero elements in the matrix then the space occupied by the sparse
matrix would be 8*8 = 64 whereas, the space occupied by the table represented
using triplets would be 8*3 = 24.
▪ In the 0th row and 1nd column, 4 value is available. In the 0th row and 3rd column,
value 5 is stored. In the 1st row and 2nd column, value 3 is stored. In the 1st row
and 3rd column, value 6 is stored. In 2nd row and 2nd column, value 2 is stored. In
the 3rd row and 0th column, value 2 is stored. In the 3rd row and 1st column, value
3 is stored.
Linked List Representation

linked list data structure is used to represent a sparse matrix. In linked list
representation, each node consists of four fields whereas, in array representation,
there are three fields, i.e., row, column, and value. The following are the fields in the
linked list:
▪ Row: It is an index of row where a non-zero element is located.
▪ Column: It is an index of column where a non-zero element is located.
▪ Value: It is the value of the non-zero element which is located at the index (row,
column).
▪ Next node: It stores the address of the next node.
In the above figure, sparse represented in the linked list form. In the node, first field represents the index
of row, second field represents the index of column, third field represents the value and fourth field
contains the address of the next node.