DATA STRUCTURES

Unit : I Introduction to Algorithm

Algorithm - Definition, Structures and Properties – Efficiency of Algorithm -

Asymptotic Notations. Data Structure – Definition - Classification – Array -
Representation - Operations. Applications: Sparse Matrices.

Dr. NGPASC
COIMBATORE | INDIA 1
 HISTORY OF ALGORITHM

The word algorithm originates from the Arabic word algorism which is linked to the
name of the Arabic mathematician Abu Jafar Mohammed Ibn Musa Al Khwarizmi (825
A.D.).
Al Khwarizm is considered to be the first algorithm designer for adding numbers.
The algorithm designed by him and followed till today, calls for summing up the digits
occurring at specific positions and the previous carry digit, repetitively moving from the
least significant digit to the most significant digit until the digits have been exhausted.

Dr. NGPASC
COIMBATORE | INDIA 2
 DEFINITION, STRUCTURE AND PROPERTIES OF ALGORITHM

DEFINITION:
An algorithm may be defined as a finite sequence of instructions each of which has a clear
meaning and can be performed with a finite amount of effort in a finite length of time.
STRUCTURE AND PROPERTIES:
An algorithm has the following structure:
(i) Input step
(ii) Assignment step
(iii) Decision step
(iv) Repetitive step
(v) Output step
Dr. NGPASC
COIMBATORE | INDIA 3
 DEFINITION, STRUCTURE AND PROPERTIES OF ALGORITHM

DEFINITION:
An algorithm may be defined as a finite sequence of instructions each of which has a clear
meaning and can be performed with a finite amount of effort in a finite length of time.
STRUCTURE AND PROPERTIES:
An algorithm has the following structure:
(i) Input step
(ii) Assignment step
(iii) Decision step
(iv) Repetitive step
(v) Output step
Dr. NGPASC
COIMBATORE | INDIA 4
 DEFINITION, STRUCTURE AND PROPERTIES OF ALGORITHM

An algorithm is endowed with the following properties:

Finiteness an algorithm must terminate after a finite number of steps.
Definiteness the steps of the algorithm must be precisely defined or unambiguously
specified.
Generality an algorithm must be generic enough to solve all problems of a particular
class.
Effectiveness the operations of the algorithm must be basic enough to be put down on
pencil and paper. They should not be too complex to warrant writing another
algorithm for the operation!
Input-Output the algorithm must have certain initial and precise inputs, and outputs
that may be generated both at its intermediate and final steps.
Dr. NGPASC
COIMBATORE | INDIA 5
 DEVELOPMENT OF ALGORITHM

The steps involved in the development of an algorithm are as follows:

(i) Problem statement
(ii) Model formulation
(iii) Algorithm design
(iv) Algorithm correctness
(v) Implementation
(vi) Algorithm analysis
(vii) Program testing
(viii) Documentation

Dr. NGPASC
COIMBATORE | INDIA 6
 DEVELOPMENT OF ALGORITHM

● Once a clear statement of the problem is done, the model for the solution of the problem
is to be formulated.
● The next step is to design the algorithm based on the solution model that is formulated.
● It is here that one sees the role of data structures. The right choice of the data structure
needs to be made at the design stage itself since data structures influence the efficiency of
the algorithm.
● Once the correctness of the algorithm is checked and the algorithm implemented, the
most important step of measuring the performance of the algorithm is done. This is what
is termed as algorithm analysis.
● It can be seen how the use of appropriate data structures results in a better performance
of the algorithm.
● Finally the program is tested and the development ends with proper documentation.
Dr. NGPASC
COIMBATORE | INDIA 7
 EFFICIENCY OF ALGORITHM

● When a problem needs to be solved, there may be many possible algorithms to

solve it. This can make it difficult to decide which algorithm is the best.
● Therefore, we need a way to compare the algorithms and choose the most suitable
one.
An algorithm’s performance is measured based on time and space.
● Time refers to how fast the algorithm works. The algorithm that completes the task
in the least time is preferred. This measure is called time complexity.
● Time complexity is the function that shows how the running time of an algorithm
or program depends on the input size.

Dr. NGPASC
COIMBATORE | INDIA 8
 EFFICIENCY OF ALGORITHM

● For space, it would mean looking for an algorithm that consumes or needs limited memory space for its
execution. The performance measure in such a case is termed space complexity.
● The space complexity of an algorithm or a program is a function of the space needed by the algorithm or
program to run to completion.
The time complexity of an algorithm can be computed either by an empirical or theoretical approach.
● The empirical or posteriori testing approach calls for implementing the complete algorithms and executing them
on a computer for various instances of the problem.
● The time taken by the execution of the programs for various instances of the problem are noted and compared.
● That algorithm whose implementation yields the least time, is considered as the best among the candidate
algorithmic solutions
Disadvantage of posteriori testing:
● The disadvantage of posteriori testing is that it is dependent on various other factors such as the machine on
which the program is executed, the programming language with which it is implemented and why, even on the
skills of the programmer who writes the program code
Dr. NGPASC
COIMBATORE | INDIA 9
 EFFICIENCY OF ALGORITHM

The Theoretical or Apriori approach:

● The theoretical or apriori approach calls for mathematically determining the resources such
as time and space needed by the algorithm, as a function of a parameter related to the
instances of the problem considered.
● A parameter that is often used is the size of the input instances. For example, for the
problem of searching for a name in the telephone directory, an apriori approach could
determine the efficiency of the algorithm used, in terms of the size of the telephone directory
(i.e.) the number of subscribers listed in the directory.
● There exist algorithms for various classes of problems which make use of the number of
basic operations such as additions or multiplications or element comparisons, as a
parameter to determine their efficiency
● The advantage of apriori analysis is that it is entirely machine, language and program
independent.
Dr. NGPASC
COIMBATORE | INDIA 10
 APRIORI ANALYSIS

Consider a program statement: x = x + 2 in a sequential programming environment. In apriori

analysis, the efficiency of this statement is studied by considering the following:
(i) the number of times the statement is executed in the program, known as the frequency count
of the statement, and
(ii) the time taken for a single execution of the statement.

Let us estimate the frequency count of the statement x = x + 2 occurring in the following three
program segments (A, B, C):

Dr. NGPASC
COIMBATORE | INDIA 11
APRIORI ANALYSIS – FREQUENCY COUNT OF PROGRAM SEGMENT A

Dr. NGPASC
COIMBATORE | INDIA 12
APRIORI ANALYSIS – FREQUENCY COUNT OF PROGRAM SEGMENT B

Dr. NGPASC
COIMBATORE | INDIA 13
APRIORI ANALYSIS – FREQUENCY COUNT OF PROGRAM SEGMENT C

Dr. NGPASC
COIMBATORE | INDIA 14
APRIORI ANALYSIS – FREQUENCY COUNT OF PROGRAM SEGMENT C

● The total frequency counts of the program segments A, B and C given

by 1, (3n + 1) and 3n2 + 3n + 1 respectively, are expressed as O (1), O
(n) and O (n2) respectively.
● These notations mean that the orders of the magnitude of the total
frequency counts are proportional to 1, n and n2 respectively.
● These are referred to as the time complexities of the program segments
since they are indicative of the running times of the program segments.

Dr. NGPASC
COIMBATORE | INDIA 15
 ASYMPTOTIC NOTATION

● Apriori analysis employs the following notations to express the time complexity of
algorithms. These are termed asymptotic notations since they are meaningful
approximations of functions that represent the time or space complexity of a
program.
● Definition 2.1: f(n) = O(g(n)) (read as f of n is big oh of g of n), if there exists a
positive integer n0 and a positive number C such that |f(n)| £ C|g (n)|, for all n ≥
n0.

Dr. NGPASC
COIMBATORE | INDIA 16
 ASYMPTOTIC NOTATION

● Definition 2.2: f(n) = W(g(n)) (read as f of n is omega of g of n), if there exists a

positive integer n0 and a positive number C such that |f(n)| ≥ C | g (n)|, for all n
≥ n0.

Dr. NGPASC
COIMBATORE | INDIA 17
 ASYMPTOTIC NOTATION

● Definition 2.3: f (n) = Q( g (n)) (read as f on n is theta of g of n) if there exist

two positive constants c1 and c2, and a positive integer n0 such that c1| g (n)| £ |
f(n)| £ c2 | g (n)| for all n ≥ n0.

Dr. NGPASC
COIMBATORE | INDIA 18
 ASYMPTOTIC NOTATION

● Definition 2.4: f(n) = o (g(n)) (read as f of n is little oh of g of n) if f(n) = O

(g(n)) and f(n) π W(g(n)).

Dr. NGPASC
COIMBATORE | INDIA 19
 DATA STRUCTURE – DEFINITION AND CLASSIFICATION

● A Data Structure is a way of organizing, storing, and managing data in a

computer so that it can be accessed and modified efficiently.
● It helps in performing operations such as insertion, deletion, searching, and
sorting of data easily.
● For example, let us consider the problem of searching for a telephone number of a
person, in the telephone directory. It is well known that searching for the telephone
number in the directory is an easy task since the data is sorted according to the
alphabetical order of the subscriber’s name.

Dr. NGPASC
COIMBATORE | INDIA 20
 ABSTRACT AND PRIMITIVES DATA TYPES

● A data type refers to the type of values that variables in a programming

language hold. Thus the data types of integer, real, character, Boolean which are
inherently provided in programming languages are referred to as primitive data
types.
● A list of elements is called as a data object. For example, we could have a list of
integers or list of alphabetical strings as data objects.
● The data objects which comprise the data structure, and their fundamental
operations are known as Abstract Data Type (ADT). In other words, an ADT is
defined as a set of data objects D defined over a domain L and supporting a list
of operations O.

Dr. NGPASC
COIMBATORE | INDIA 21
 CLASSIFICATION OF DATA TYPES

● The data structures are broadly classified as linear data structures and non-linear data structures.
Linear data structures are unidimensional in structure and represent linear lists. These are further
classified as sequential and linked representations. On the other hand, non-linear data structures are
two-dimensional representations of data lists.

Dr. NGPASC
COIMBATORE | INDIA 22
 LINEAR DATA STRUCTURES

1. Linear Data Structures

● In linear data structures, elements are arranged in a sequence, one after another. Each element
(except the first and last) has a unique predecessor and successor.
● Linear data structures are further divided into:
A) Sequential Representation
● In this method, elements are stored in contiguous (continuous) memory locations.
i) Arrays
● Collection of elements of the same data type.
● Stored in continuous memory.
● Accessed using index.
● Example: A[5] = {10,20,30,40,50}
● Used in searching and sorting operations.
Dr. NGPASC
COIMBATORE | INDIA 23
 LINEAR DATA STRUCTURES

ii) Stacks
● Follows LIFO (Last In First Out) principle.
● Insertion (push) and deletion (pop) occur at the top.
● Example: Stack of plates, undo operation in editors.
iii) Queues
● Follows FIFO (First In First Out) principle.
● Insertion at rear and deletion from front.
● Example: Queue at a ticket counter.
iv) Priority Queues
● Elements are processed based on priority.
● Highest priority element is removed first.
● Example: Emergency patients in a hospital.
Dr. NGPASC
COIMBATORE | INDIA 24
 LINEAR DATA STRUCTURES

B) Linked Representation
● In this method, elements are stored in non-contiguous memory locations and are connected
using links (pointers).
i) Linked Lists
● Collection of nodes where each node contains data and a link to the next node.
● Dynamic in size.
● Example: Playlist of songs.
ii) Linked Stacks
● Stack implemented using linked list.
● No fixed size limitation.
iii) Linked Queues
● Queue implemented using linked list.
Dr. NGPASC ● Efficient memory utilization.
COIMBATORE | INDIA 25
 LINEAR DATA STRUCTURES

2. Non-Linear Data Structures

● In non-linear data structures, elements are not arranged sequentially. A single element
can be connected to multiple elements.
● i) Trees
● Hierarchical structure with a root and child nodes.
● Represents parent-child relationship.
● Example: File directory system, organization chart.
ii) Graphs
● Consists of vertices (nodes) and edges (connections).
● Represents complex relationships.
● Example: Road maps, social networks.
Dr. NGPASC
COIMBATORE | INDIA 26
 ARRAYS

● An array is an ADT whose objects are sequence of elements of the same type and
the two operations performed on it are store and retrieve.
● Thus if a is an array the operations can be represented as STORE (a, i, e) and
RETRIEVE (a, i) where i is termed as the index and e is the element that is to be
stored in the array.
● These functions are equivalent to the programming language statements a[i ]: = e
and a[i ] where i is termed subscript and a the array variable name in
programming language parlance.

Dr. NGPASC
COIMBATORE | INDIA 27
 ARRAYS

● Arrays could be of one-dimension, two dimension, three-dimension or in general

multidimension.
● Figure 3.1 illustrates a one and two dimensional array. It may be observed that
while one-dimensional arrays are mathematically likened to vectors, two-
dimensional arrays are likened to matrices.
● In this regard, two-dimensional arrays also have the terminologies of rows and
columns associated with them.

Dr. NGPASC
COIMBATORE | INDIA 28
 ARRAYS

● A[1:5] refers to a one-dimensional array where 1, 5 are referred to as the lower

and upper indexes or the lower and upper bounds of the index range respectively.
● Similarly, B[1:3, 1:2] refers to a two-dimensional array with 1, 3 and 1, 2 being
the lower and upper indexes of the rows and columns respectively.
● Also, each element of the array viz., A[i ] or B[i, j ] resides in a memory location
also called a cell. Here cell refers to a unit of memory and is machine dependent.

Dr. NGPASC
COIMBATORE | INDIA 29
 ARRAY OPERATIONS

An array when viewed as a data structure supports only two operations viz.,
(i) storage of values (i.e.) writing into an array (STORE (a, i, e) ) and,
(ii) retrieval of values (i.e.) reading from an array ( RETRIEVE (a, i) )
For example, if A is an array of 5 elements then Fig. 3.2 illustrates the operations
performed on A.

Dr. NGPASC
COIMBATORE | INDIA 30
 NUMBER OF ELEMENTS IN AN ARRAY

One-dimensional array:
Let A[1:u] be a one-dimensional array. The size of the array, as is evident is u and
the elements are A[1], A[2], A[u 1], A[u]. In the case of the array A[l : u] where l
is the lower bound and u is the upper bound of the index range, the number of
elements is given by (u l + 1).
The number of elements in
(i) A[1:26] = 26
(ii) A[5:53] = 49 (Q 53 5 + 1)
(iii) A[1:26] = 28

Dr. NGPASC
COIMBATORE | INDIA 31
 NUMBER OF ELEMENTS IN AN ARRAY

Two-dimensional array:
Let A[1 : u1, 1 : u2] be a two-dimensional array where u1 indicates the number of
rows and u2 the number of columns in the array. Then the number of elements in A
is u1.u2 Generalizing, A[l1 : u1, l2 : u2] has a size of (u1 l1 + 1) (u2 l2 + 1)
elements. Figure 3.3 illustrates a two dimensional array and its size.

Dr. NGPASC
COIMBATORE | INDIA 32
 NUMBER OF ELEMENTS IN AN ARRAY

Multi-dimensional array:
A multi-dimensional array A[1 : U1, 1 : U2,….1:Un] has a size of U1 . U2…Un
elements.

Dr. NGPASC
COIMBATORE | INDIA 33
 REPRESENTATION OF ARRAYS IN MEMORY

A multi-dimensional array can be understood as a collection of lower-

dimensional arrays:
● Two-dimensional array A[1:u1, 1:u2] can be seen as u1 one-dimensional arrays
, each of size u2.
● Three-dimensional array A[1:u1, 1:u2, 1:u3] can be viewed as u1 two-
dimensional arrays, each of size u2 × u3.
● General case: An n-dimensional array A[1:u1, 1:u2, …, 1:un] is a collection of
u1 arrays, each of dimension [1:u2, 1:u3, …, 1:un].
Memory storage:
● Arrays can be stored in memory using:
● Row-major order (elements of a row stored consecutively)
● Column-major order (elements of a column stored consecutively)
Dr. NGPASC
COIMBATORE | INDIA 34
 REPRESENTATION OF ARRAYS IN MEMORY

Dr. NGPASC
COIMBATORE | INDIA 35
 ONE DIMENSIONAL ARRAY

● Consider the array A(1 : u1) and let α be the address of the starting memory location
referred to as the base address of the array.
● Here as is evident, A[1] occupies the memory location whose address is α, A(2) occupies α +
1 and so on.
● In general, the address of A[i] is given by α + (i-1).
● In general, for a one-dimensional array A(l1 : u1) the address of A[i] is given by α + (i -
l1), where α is the base address.
● Example - For the array given below with base address α = 100, the addresses of the array
elements specified are computed as given below:

Dr. NGPASC
COIMBATORE | INDIA 36
 REPRESENTATION OF ONE DIMENSIONAL ARRAY

Dr. NGPASC
COIMBATORE | INDIA 37
 REPRESENTATION OF TWO DIMENSIONAL ARRAY

● Consider the array A[1 : u1, 1 : u2] which is to be stored in the

memory. It is helpful to imagine this array as u1 number of one-
dimensional arrays of length u2.
● Thus if A[1, 1] is stored in address a, the base address, then A[i, 1]
has address α + (i -1)u2, and A[i, j ] has address α + (i -1)u2 +
( j -1).

Dr. NGPASC
COIMBATORE | INDIA 38
 REPRESENTATION OF TWO DIMENSIONAL ARRAY

● In general, for a two-dimensional array A[l 1 : u1, l 2 : u2 ] the address of

A[i, j ] is given by α + (i -l1)(u2- l2 + 1) + ( j- l2)

Dr. NGPASC
COIMBATORE | INDIA 39
 THREE DIMENSIONAL ARRAY

Three-Dimensional Array
● Consider a 3D array A[1:u1, 1:u2, 1:u3].
● It can be thought of as u1 two-dimensional arrays, each of size u2 × u3.
● Analogy: Imagine buildings (i = building), each with u2 floors (j = floor), and each
floor has u3 rooms (k = room).
[Link] an element A[i, j, k]:
To reach A[i, 1, 1] (first room of first floor of the ith building), you must skip:
● (i - 1) × u2 × u3 rooms from previous buildings.
● Then move to the first floor of the ith building.

Dr. NGPASC
COIMBATORE | INDIA 40
 THREE DIMENSIONAL ARRAY

Dr. NGPASC
COIMBATORE | INDIA 41
 THREE DIMENSIONAL ARRAY

Dr. NGPASC
COIMBATORE | INDIA 42
 THREE DIMENSIONAL ARRAY

● In general for a three-dimensional array A[l 1 : u1, l 2 : u2, l 3 :

u3] the address of A[i, j, k] is given by
α + (i -l1)(u2-l2 + 1)(u3-l3 + 1) + (j-l2 )(u3-l3 + 1) + (k-l3)

Dr. NGPASC
COIMBATORE | INDIA 43
 APPLICATIONS - SPARSE MATRIX

● A matrix is a mathematical object which finds its applications in various

scientific problems.
● A matrix is an arrangement of m.n elements arranged as m rows and n
columns.
● The Sparse matrix is a matrix with zeros as the dominating elements.
● There is no precise definition for a sparse matrix. In other words, the sparseness
is relatively defined.

Dr. NGPASC
COIMBATORE | INDIA 44
 SPARSE MATRIX

● A matrix consumes a lot of space in memory. Thus, a 1000 * 1000 matrix needs
1 million storage locations in memory. Imagine the situation when the matrix is
sparse! To store a handful of non-zero elements, voluminous memory is allotted
and thereby wasted.
● In such a case to save valuable storage space, we resort to a triple representation
viz., (i, j, value) to represent each non-zero element of the sparse matrix.
● In other words, a sparse matrix A is represented by another matrix B [0 : t, 1 :
3] with t + 1 rows and 3 columns. Here t refers to the number of non-zero
elements in the sparse matrix.
● While rows 1 to t record the details pertaining to the non-zero elements as triple
(that is 3 columns), the zeroth row viz. B[0, 1], B[0, 2] and B[0, 3] record the
number of non-zero elements of the original sparse matrix A.
Dr. NGPASC
COIMBATORE | INDIA 45
 SPARSE MATRIX
Applications: Sparse Matrices.
Sparse matrix:
A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the
matrix have 0 value, then it is called a sparse matrix.

Definition
A sparse matrix is a matrix in which most of the elements are zero, with only a few non-zero values. In other words, the number of zero
elements is much greater than the number of non-zero elements.

Why to use Sparse Matrix instead of simple matrix ?

Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements.
Example

Dr. NGPASC 46 46

COIMBATORE | INDIA
 SPARSE MATRIX
Sparse Matrix Representations
Sparse Matrix Representations can be done in many ways following are two common representations:

Array representation

Linked list representation

a)Triplet Representation(Array Representation)

A data structure that can store all information about non-zero elements namely row number i, column number j, and the value itself.
The most naive thought is a 2-d matrix having rows equal to the number of non-zero elements and three columns for storing the element and its position
coordinates as shown below.

Dr. NGPASC 47

COIMBATORE | INDIA
 SPARSE MATRIX
b)Linked List Representation
A linear data structure that can store all information about all non-zero elements namely row number i, column number j, and the value itself.

Besides array, a linked list can also be a good choice for storing the sparse matrix in a compressed form where each node of the linked list
has exactly four entries containing row number, column number, the value of the non-zero element along with the pointer of the next node i.e.
(i, j, value, next-pointer) as shown below.

The corresponding transformation from 2-d matrix to linked list representation is as follows:

Dr. NGPASC 48

COIMBATORE | INDIA
 SPARSE MATRIX
Triplet representation is a method to store a sparse matrix by keeping only non-zero elements.
Instead of storing all elements, we store three values for each non-zero element:
Define the terminologies for each triplet:

a) Row:
It is defined as the row number of the non-zero element counted from top to
bottom when it is present in the 2-d array representation.
b) Column:
It is defined as the column number of the element counted from left to right
when it is present in the 2-d array representation.
c) Value:
It is defined as the value of the non-zero element present at the (row, column)
cell of the 2-d array representation.
Dr. NGPASC 49
COIMBATORE | INDIA
 SPARSE MATRIX
Transformation of Sparse Matrix to Triplet Representation

Example
Convert the following matrix into Triplet Representation.

0 0 0 6
0 0 8 0
0 0 0 0
5 0 0 4

Dr. NGPASC 50

COIMBATORE | INDIA
 SPARSE MATRIX
Step 1: Find matrix size Step 4: Form Triplet Table
Rows = 4
Columns = 4

Step 2: Find non-zero elements

Step 3: Write Triplet rules

First row header
(rows, columns, non-zero count)
Remaining rows
(row, column, value)

Dr. NGPASC 51

COIMBATORE | INDIA
 SPARSE MATRIX
Triplet(Array) implementation of sparse matrix

Triplet implementation is similar to the original sparse matrix i.e. it is also a matrix but of order 3xP where P represents the number of non-
zero elements in the original matrix and 3 columns where the first column represents the row number, the second column represents the
column number corresponding to the original sparse matrix which is of the order say M x N.
● The number of non-zero elements i.e. P in the sparse matrix is calculated by traversing the original matrix in O(MxN).
● Thus, the idea is to declare a 3 x P matrix, let's call it tripletMatrix[3][P], then traverse the original sparse matrix and for some ith non-
zero element of the sparse matrix, tripletMatrix[0][i] is its row number , tripletMatrix[1][i] is its column number ,tripletMatrix[2][i] is its value
considering 0-based indexing.
● filling the tripletMatrix while traversing the original sparse matrix in O(MxN).

● Initialize a variable k to zero which keeps track of the non-zero element count hence 0 <= k < P and while
traversing the original matrix whenever a non-zero element is encountered then asssign it to the tripleMatrix as
(tripletMatrix[0][k] = row number, tripletMatrix[1][k] = column number, tripletMatrix[2][k] = value) represents the kth
non-zero element in the sparse matrix and increment k by 1.

Dr. NGPASC 52

COIMBATORE | INDIA
 SPARSE MATRIX
C++ implementation of the tripletMatrix.

//C++ program for sparse matrix representation

//Using triplets
#include<iostream>

using namespace std;

int main()
{
// sparse matrix of order 5x6 with 6 non-zero values
int sparseMatrix[5][6] =
{
{0 , 8 , 0 , 0 , 9, 0 },
{0 , 0 , 0 , 3 , 0, 0 },
{4 , 0 , 0 , 0 , 0, 5 },
{0 , 6 , 9 , 2 , 0, 0 },
{0 , 0 , 0 , 0 , 0, 0 }
};

// Finding total non-zero values in the sparse matrix

int nonZeroValues = 0;
for (int row = 0; row < 5; row++)
for (int column = 0; column < 6; column++)
Dr. NGPASC if (sparseMatrix[row][column] != 0) 53
COIMBATORE | INDIA
 SPARSE MATRIX
// Defining triplet Matrix
int tripletMatrix[3][nonZeroValues];

// Generating triplet matrix

int k = 0;
for (int row = 0; row < 5; row++)
for (int column = 0; column < 6; column++)
if (sparseMatrix[row][column] != 0)
{
tripletMatrix[0][k] = row;
tripletMatrix[1][k] = column;
tripletMatrix[2][k] = sparseMatrix[row][column];
k++;
}

// Displaying triplet matrix

cout<<"Triplet Representation : "<<"\n";
for (int row=0; row<3; row++)
{
for (int column = 0; column<nonZeroValues; column++)
cout<<tripletMatrix[row][column]<<" ";

cout<<"\n";
}
return 0;
Dr. NGPASC 54
}
COIMBATORE | INDIA
 SPARSE MATRIX
Linked list Representation of the Sparse Matrix
This representation is another linear representation of the sparse matrix besides triplet representation in which each non-zero element of the sparse matrix
is represented by a linked list node where the information about the non-zero element of sparse matrix namely row number i counted from left to right in
the sparse matrix, column number j counted from top to down in the sparse matrix, the value of the element and the pointer to the next non-zero element
i.e. next node of linked list is stored in the linked list node.
Thus, the sparse matrix is transformed into a linked list where each node contains a non-zero element.
define the terminologies for the linked list node: a) Row:
It is defined as the row number of the non-zero element counted from
top to bottom when it is present in the 2-d array representation.
b) Column:
It is defined as the column number of the element counted from left to
right when it is present in the 2-d array representation.
c) Value:
It is defined as the value of the non-zero element present at the (row,
column) cell of the 2-d array representation.
d) Next pointer:
It is defined as the address of the next node in the linked list storing
the next non-zero value.

Dr. NGPASC 55

COIMBATORE | INDIA
 SPARSE MATRIX
Transformation of Sparse Matrix to Linked List Representation

Dr. NGPASC 56

COIMBATORE | INDIA
 SPARSE MATRIX
Linked list Implementation of Sparse Matrix
Linked list implementation is also another compressed representation of the sparse matrix where each non-zero element is represented by each node
of the linked list containing row number, column number, the value of the element, next pointer.
● The number of non-zero elements i.e. P in the sparse matrix is calculated by traversing the original matrix in O(MxN).
● Thus, the idea is to create a class of Node that stores the row, column, value, and a pointer of type Node which points to the next node.
● Thus, using this class objects i.e. nodes of the linked list are created and each node is filled with the non-zero element of sparse matrix, and
nodes are linked by the next pointer. // Using Linked list
#include<iostream>
using namespace std;

// Node class to represent linked list

class Node
{
public:
int row;
int col;
int value;
Node *nextPointer;
};

// Function to create new node

void createNewNode(Node **p, int rowIndex,
int colIndex, int nonZeroValue)
{
Dr. NGPASC Node *temp = *p; 57
COIMBATORE | INDIA
 SPARSE MATRIX
// If link list is empty then
// create first node and assign value.
if (temp == NULL)
{
temp = new Node();
temp->row = rowIndex;
temp->col = colIndex;
temp->value = nonZeroValue;
temp->nextPointer = NULL;
*p = temp;
}
// If link list is already created
// then append newly created node
else
{
while (temp->nextPointer != NULL)
temp = temp->nextPointer;

r = new Node();
r->row = rowIndex;
r->col = colIndex;
r->value = nonZeroValue;
r->nextPointer = NULL;
temp->nextPointer = r;
}
}
Dr. NGPASC 58
COIMBATORE | INDIA
 SPARSE MATRIX
// Function prints contents of linked list
// starting from startNode
void printList(Node *startNode)
{
Node *ptr = startNode;
cout << "Row position:";
while (ptr != NULL)
{
cout << ptr->row << " ";
ptr = ptr->nextPointer;
}
cout << endl;
cout << "Column position:";

ptr = startNode;
while (ptr != NULL)
{
cout << ptr->col << " ";
ptr = ptr->nextPointer;
}
cout << endl;
cout << "Value:";
ptr = startNode;
Dr. NGPASC 59
COIMBATORE | INDIA
 SPARSE MATRIX
while (ptr != NULL)
{
cout << ptr->value << " ";
ptr = ptr->nextPointer;
}
}

// Driver Code
int main()
{
// sparse matrix of order 5x6 with 6 non-zero values
int sparseMatrix[5][6] =
{
{0 , 8 , 0 , 0 , 9, 0 },
{0 , 0 , 0 , 3 , 0, 0 },
{4 , 0 , 0 , 0 , 0, 5 },
{0 , 6 , 9 , 2 , 0, 0 },
{0 , 0 , 0 , 0 , 0, 0 }
};

Dr. NGPASC 60

COIMBATORE | INDIA
 SPARSE MATRIX

// Creating head/first node of list as NULL

Node *first = NULL;
for(int i = 0; i < 5; i++)
for(int j = 0; j < 6; j++)
{
// Pass only those values which
// are non - zero
if (sparseMatrix[i][j] != 0)
createNewNode(&first, i, j,
sparseMatrix[i][j]);
}
}
printList(first);
return 0;
}
● Generating the linked list while traversing the original sparse matrix in O(MxN).
● While traversing, when a non-zero element is encountered then, a new node object is created using the Node class and the row number, column number, value of
element are assigned to it then already created linked list is traversed up to the last node and this node is attached at the end, hence, this node is the new last
node of the linked list which points to none.

Dr. NGPASC 61

COIMBATORE | INDIA
 SPARSE MATRIX
● Advantages & Disadvantages of Using Sparse Matrices

Here are the advantages and disadvantages of using sparse matrices in data structure:

Advantages

● Stores only non-zero elements, reducing memory usage.

● Operations on sparse matrices are faster because of non-zero elements.

● Sparse matrices can handle much larger datasets.

Disadvantages

● Not all problems can be represented as sparse matrices.

● Sparse matrices may lose information since many elements are zero.

● Choosing the right algorithms and libraries for sparse matrix operations can be challenging.

Dr. NGPASC 62

COIMBATORE | INDIA