Data Structures

A data structure is basically a group of data elements that are put together under one name, and
which defines a particular way of storing and organizing data in a computer so that it can be
used efficiently.

Data structures are used in almost every program or software system. Some common examples
of data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Data
structures are widely applied in the following areas:

• Compiler design
• Operating system
• Statistical analysis package
• DBMS
• Artificial intelligence
• Graphics

Data structures are generally categorized into two classes: Linear and Non Linear data
structures. If the elements of a data structure are stored in a linear or sequential order, then it is
a linear data structure. Examples include arrays, linked lists, stacks, and queues. Linear data
structures can be represented in memory in two different ways. One way is to have to a linear
relationship between elements by means of sequential memory locations. The other way is to
have a linear relationship between elements by means of links. However, if the elements of a
data structure are not stored in a sequential order, then it is a non-linear data structure. The
relationship of adjacency is not maintained between elements of a non-linear data structure.
Examples include trees and graphs.
 Figure 1: Types of data Structures

Linear Data Structures Non-linear Data Structures

In linear data structure, data elements are In non-linear data structure, data elements
sequentially connected and each element is are hierarchically connected and are present
traversable through a single run. at various levels.

Linear data structures can be traversed Non-linear data structures are not easy to
completely in a single run. traverse and needs multiple runs to be
traversed completely.

Linear data structures are not very memory Non-linear data structures uses memory
friendly and are not utilizing memory very efficiently.
efficiently.
Time complexity of linear data structure often Time complexity of non-linear data
increases with increase in size. structure often remain with increase in size.

Array, List, Queue, Stack. Graph, Map, Tree.

Comparison of Linear and Non Linear Data Structures
ABSTRACT DATA TYPE(ADT)

An abstract data type (ADT) is the way we look at a data structure, focusing on what it does
and ignoring how it does its job. For example, stacks and queues are perfect examples of an
ADT. We can implement both these ADTs using an array or a linked list. This demonstrates
the ‘abstract’ nature of stacks and queues.
LIST ADT:
List is a linear data structures which consists of sequential collection of elements of same
data type. List can be implemented using arrays and Linked List

LIST USING ARRAYS

An array is a collection of similar data elements. These data elements have the same data type.
The elements of the array are stored in consecutive memory locations and are referenced by an
index (also known as the subscript). The subscript is an ordinal number which is used to
identify an element of the array.

Basic Operations

• Creation
• Insert
• Delete
• Find/Search
• Display/Traversal

Creation:

# define maxsize 10
int lst[maxsize];
int size=0
The variable maxsize denotes the size of the array and size represents the number of elements
in the List. Since the list is empty, size is 0.
Insert Operation

Inserting an element into list requires the position to be inserted. To insert an element at
intermediate position requires movement of element after the position to be inserted by one
position to its right. Insertion into the list cannot be done it the list is already full.
void insert(int pos, int val)
{
if(size<maxsize-1)
{
if( ( pos>=0) && (pos<=size ) )
{
for (int k=size-1;k>=pos;k--)
lst[k+1]=lst[k];
lst[pos]= val;
size++;
printf(“ %d has been inserted”, val);
}
else
printf(“\n Invalid position”);
}
else
printf(“\n List is full”);
}
Delete Operation:

Deletion of an element from the list requires to find the position of the element to be deleted.
Deleting an element at intermediate position requires movement of element after deletion to be
moved by one position to its left.
 void remove(int pos)
{
if(pos>=0 && pos<size)
{
printf(“%d is removed", lst[pos]);
for(int k=pos;k<size;k++)
{
lst[k]=lst[k+1];
}
size--;
}
else
printf(“\n Element Cannot be Removed”);
}
Search/Find Operation:

Searching an element in list is based on linear search. It sequentially checks each element of
the list until a match is found or the whole list has been searched

void search(int val)

{
for(int k=0;k<size;k++)
{
if(lst[k]==val)
printf(“\n Element found at the position: %d”,k);
 return;
}
printf(“\n Element Not found”);
}
Display/Traverse

Traversing the element is done by iterating from first to last element directly by using the index
of the list
void display()
{
printf(“\n List Elements are..”);
for(int i=0;i<size;i++)
printf(“\n %d”,lst[i]);
}
Disadvantages:

• Size of the array is fixed.

• Insertion and deletion requires movement of element and is time consuming
• Wastage of memory if allotted memory is not used.

LINKED LIST
A linked list, in simple terms, is a linear collection of data elements. These data elements are
called nodes. Linked list is a data structure which in turn can be used to implement other data
structures. Thus, it acts as a building block to implement data structures such as stacks, queues,
and their variations. A linked list can be perceived as a train or a sequence of nodes in which
each node contains one or more data fields and a pointer to the next node. Every node has two
parts: Data and a pointer (link)
Types of Linked List

• Singly Linked List

• Doubly Linked List
• Circular Linked List

SINGLY LINKED LIST

A singly linked list is a type of linked list that is unidirectional, can be traversed in only one
direction from head to the last node (tail). A single node contains data and a pointer to the next
node.
Structure of Node:

Every node has a data part and a pointer that links to the next node

struct node
{
int data;
struct node *next;
}*head=NULL;
Basic Operations:

• Insertion
• Deletion
• Traverse/Display
• Search/Find

Insert Operation

Insertion is process of adding elements into the list. Based on the position to be inserted
insertion is classified as:

• Insert at First
• Insert at Last
• Insert after a specific element

Insert at First

Inserting an element at beginning requires creation of new node and changing the pointer
assignment of head pointer
 Before Insertion

After Inserting 7

void insertfirst(int val)

{
struct node *n1=(struct node *)malloc(sizeof(struct node));
n1->data=val;
n1->next=head;
head=n1;
}
Insert at Last

Inserting an element at last requires creation of new node, traversing the list to the last node
and changing the pointer assignment of last node to point to the new node.

Before Insertion

After Inserting 100

void insertlast(int val)

struct node *n1=(struct node *)malloc(sizeof(struct node));

struct node *temp;

 n1->data=val;

n1->next=NULL;

temp=head;

while(temp->next!=NULL)

temp=temp->next;

temp->next=n1;

The pointer temp starts from the first element and iterates through every element to find
the last element and the newnode n1 is assigned as the next node of the last node temp.

Insert after a specific element

Inserting an element after a specific element needs to find the element, creation of new node
and changing the pointer assignment accordingly.

Before Insertion

After Inserting 75

void insertafter(int after,int val)

{
struct node *n1=(struct node *)malloc(sizeof(struct node));
struct node *temp;
n1->data=val;
temp=head;
while(temp!=NULL)
 {
if(temp->data==after)
{
n1->next=temp->next;
temp->next=n1;
return;
}
else
temp=temp->next;
}
printf("\nSpecified element not found");

}
In the above code, the pointer temp searches for the specified element from the starting
of the list. On finding the specified element as temp, the next pointer of temp and n1 is
changed accordingly.
Deletion

Deletion of a node in singly linked list needs to find the element to be deleted and tracking its
previous element in the list and changing the pointer of the previous node accordingly.

Before Deletion

After Deleting 50

void remov(int val)

{
struct node *temp,*before;
if(head->data==val)
{
head=head->next;
 }
else
{
temp=head->next;
before=head;
while(temp!=NULL)
{
if(temp->data==val)
{
before->next=temp->next;
free(temp);
return;
}
else
{
temp=temp->next;
before=before->next;
}
}
printf("\nElement cannot be deleted");
}
}
Find/Search Operation

Searching an element in list is based on linear search. It sequentially checks each element of
the list until a match is found or the whole list has been searched.
void search(int val)
{
struct node *temp;
temp=head;
while(temp!=NULL)
{
if(temp->data==val)
{
printf("\nElement found in the list");
return;
}
else
 temp=temp->next;
}
printf("\nElement not found");
}
Display/Traverse

Traversing the element is done by iterating from first to last element directly by using the head
pointer.

void display()
{
struct node *temp;
temp=head;
printf("\nThe elements of linked list are....");
while(temp!=NULL)
{
printf("\%d->",temp->data);
temp=temp->next;
}
}

DOUBLY LINKED LIST

Doubly linked list is a type of linked list in which each node apart from storing its data has
two links. The first link points to the previous node in the list and the second link points to
the next node in the list

Basic Operations:

• Insertion
• Deletion
• Traverse/Display
• Search/Find

Structure of Node
Every node has a data part, a pointer that links to the next node and a pointer that refers to the
previous node.

struct node

struct node * prev;

int data;

struct node *next;

}*head=NULL;

Insert Operation

Insertion is process of adding elements into the list. Based on the position to be inserted
insertion is classified as:

• Insert at First
• Insert at Last
• Insert after a specific element

Insert at First

Inserting an element at beginning requires creation of new node and changing the pointer
assignment of head pointer

Before Insertion

After Inserting 5

void insertfirst(int val)

{
 struct node *n1=(struct node *)malloc(sizeof(struct node));
n1->data=val;
n1->prev=NULL;
if(head==NULL)
{
n1->next=NULL;
head=n1;
}
else
{
n1->next=head;
head->prev=n1;
head=n1;
}
}
Insert at Last

Inserting an element at last requires creation of new node, traversing the list to the last node
and changing the next pointer assignment of last node to point to the new node, prev pointer
of new node to point to the existing last node

Before Insertion

After Inserting 50

void insertlast(int val)

{
struct node *n1=(struct node *)malloc(sizeof(struct node));
n1->data=val;
 n1->next=NULL;
struct node *temp;
if(head==NULL)
{
n1->prev=NULL;
head=n1;
}
else
{
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=n1;
n1->prev=temp;
}
}
Insert after a specific element

Inserting an element after a specific element needs to find the element, creation of new node
and changing the next and prev pointer assignment accordingly.

Before Insertion

Inserting 25 after 30

void insertafter(int after, int val)

struct node *n1=(struct node *)malloc(sizeof(struct node));

 n1->data=val;

struct node *temp,*aft;

temp=head;

while(temp!=NULL)

if(temp->data==after)

n1->next=temp->next;

n1->prev=temp;

aft=temp->next;

aft->prev=n1;

temp->next=n1;

return;

else

temp=temp->next;

In the above code, the pointer temp searches for the specified element from the starting
of the list. On finding the specified element as temp, the next pointer of temp and n1 is
changed accordingly. The prev pointers of n1 and after is assigned accordingly where
after is the next node of specified node.

Delete Operation

Deleting an element in the list requires finding the element, changing the next and prev
pointer of its adjacent nodes accordingly.

Before deletion
 After deleting 30

void remov(int val)

{
struct node *temp, *bef, *aft;
temp=head;
while(temp!=NULL)
{
if(temp->data==val)
{
if(temp->prev==NULL)
{
head=temp->next;
(temp->next)->prev=NULL;
free(temp);
return;
}
else if (temp->next==NULL)
{
(temp->prev)->next=NULL;
free(temp);
return;
}
else
{
(temp->prev)->next=temp->next;
(temp->next)->prev=temp->prev;
free(temp);
return;
}
}
else
temp=temp->next;
 }
}
Find/Search Operation

Searching an element in list is based on linear search. It sequentially checks each element of
the list until a match is found or the whole list has been searched

void search(int val)

{
struct node *temp;
temp=head;
while(temp!=NULL)
{
if(temp->data==val)
{
printf("Element found in the list");
return;
}
else
temp=temp->next;
}
printf("\nElement not found");
}
Display/Traverse

Traversing the element is done by iterating from first to last element directly by using the
head pointer.

void display()
{
struct node *temp;
temp=head;
printf(“List Elements are....”);
while(temp!=NULL)
{
printf(“%d->”,temp->data);
temp=temp->next;
}
}
Applications of linked list:
A linked list is a linear data structure, in which the elements are not stored at contiguous
memory locations. The elements in a linked list are linked using pointers as shown in the
below image:

Applications of linked list in computer science:

1. Implementation of stacks and queues

2. Implementation of graphs: Adjacency list representation of graphs is the most popular
which uses a linked list to store adjacent vertices.
3. Dynamic memory allocation: We use a linked list of free blocks.
4. Maintaining a directory of names
5. Performing arithmetic operations on long integers
6. Manipulation of polynomials by storing constants in the node of the linked list
7. Representing sparse matrices
Applications of linked list in the real world:
1. Image viewer – Previous and next images are linked and can be accessed by the next and
previous buttons.
2. Previous and next page in a web browser – We can access the previous and next URL
searched in a web browser by pressing the back and next buttons since they are linked as
a linked list.
3. Music Player – Songs in the music player are linked to the previous and next songs. So
you can play songs either from starting or ending of the list.
4. GPS navigation systems- Linked lists can be used to store and manage a list of locations
and routes, allowing users to easily navigate to their desired destination.
5. Robotics- Linked lists can be used to implement control systems for robots, allowing
them to navigate and interact with their environment.
6. Task Scheduling- Operating systems use linked lists to manage task scheduling, where
each process waiting to be executed is represented as a node in the list.
7. Image Processing- Linked lists can be used to represent images, where each pixel is
represented as a node in the list.
8. File Systems- File systems use linked lists to represent the hierarchical structure of
directories, where each directory or file is represented as a node in the list.
9. Symbol Table- Compilers use linked lists to build a symbol table, which is a data structure
that stores information about identifiers used in a program.
10. Undo/Redo Functionality- Many software applications implement undo/redo
functionality using linked lists, where each action that can be undone is represented as a
node in a doubly linked list.
11. Speech Recognition- Speech recognition software uses linked lists to represent the
possible phonetic pronunciations of a word, where each possible pronunciation is
represented as a node in the list.
12. Polynomial Representation- Polynomials can be represented using linked lists, where
each term in the polynomial is represented as a node in the list.
13. Simulation of Physical Systems- Linked lists can be used to simulate physical systems,
where each element in the list represents a discrete point in time and the state of the
system at that time.

CIRCULAR LINKED LIST

The circular linked list is a linked list where all nodes are connected to form a circle. In a
circular linked list, the first node and the last node are connected to each other which forms a
circle. There is no NULL at the end.

Circular singly linked list: In a circular Singly linked list, the last node of the list contains a
pointer to the first node of the list. We traverse the circular singly linked list until we reach the
same node where we started. The circular singly linked list has no beginning or end. No null
value is present in the next part of any of the nodes.
Basic Operations:

• Insertion
• Deletion
• Traverse/Display
• Search/Find

Representation of node

struct node
{
int data;
struct node *next;
}*head=NULL;
Insert Operation

Insertion is process of adding elements into the list. Based on the position to be inserted
insertion is classified as:

• Insert at First
• Insert at Last
• Insert after a specific element

Insert at First

Inserting an element at beginning of circular linked list requires creation of new node and
changing the pointer assignment of head pointer to the newnode n1and the next pointer of last
node to n1.

Before Insertion
 After Inserting 40

void insertfirst(int val)

{
struct node *n1= (struct node *)malloc(sizeof(struct node));
struct node *temp;
n1->data=val;
if(head==NULL)
{
n1->next=n1;
head=n1;
}
else
{
temp=head;
while(temp->next!=head)
temp=temp->next;
n1->next=head;
head=n1;
temp->next=n1;
}
}
If the list is empty, the newnode n1 is inserted as the first node and next pointer refers to itself.
Insert at Last

Inserting an element at last requires creation of new node, traversing the list to the last node
and changing the pointer assignment of last node to point to the new node. The next pointer of
newnode refers to the first node.
 Before Insertion

After Inserting 40
void insertlast(int val)
{
struct node *n1= (struct node *)malloc(sizeof(struct node));
struct node *temp;
n1->data=val;
if(head==NULL)
{
n1->next=n1;
head=n1;
}
else
{
temp=head;
while(temp->next!=head)
temp=temp->next;
temp->next=n1;
n1->next=head;
}
}
If the list is empty, the newnode n1 is inserted as the first node and next pointer refers to itself.
If the list is not empty, the next pointer of last is changed to refer to newnode n1 and the next
pointer of n1 refers to the first node.
Insert after a specific element

Inserting an element after a specific element needs to find the element, creation of new node
and changing the pointer assignment accordingly.

Before Insertion

void insertafter(int after, int val)

{
struct node *n1= (struct node *)malloc(sizeof(struct node));
struct node *temp;
n1->data=val;
temp=head;
do
{
if(temp->data==after)
{
n1->next=temp->next;
temp->next=n1;
return;
}
else
temp=temp->next;
 }while(temp!=head);
printf("\nSpecified element not found");
}
In the above code, the pointer temp searches for the specified element from the starting of the
list. On finding the specified element as temp, the next pointer of temp and n1 is changed
accordingly.
Deletion:
Deletion of a node in circular singly linked list needs to find the element to be deleted and
tracking its previous element in the list and changing the pointer of the previous node
accordingly.

Before Deletion

After deleting 30
void remov(int val)
{
struct node*temp, *before, *last;
temp=head;
if(temp->data==val)
{
if(temp->next==head)
{
free(temp);
head=NULL;
return;
}
else
{
 last=head->next;
while(last->next!=head)
last=last->next;
head=head->next;
last->next=head;
free(temp);
return;
}
}
else
{
temp=head->next;
before=head;
while(temp!=head)
{
if(temp->data==val)
{
before->next=temp->next;
free(temp);
return;
}
else
{
temp=temp->next;
before=before->next;
}
}
}
}
If the element to be deleted is the first node, the next pointer of the last node should be
updated. If the intermediate element is deleted the next pointer of previous node is updated
with the address of the nest node after specified node.
Find/Search Operation

Searching an element in circular linked list is based on linear search. It sequentially checks
each element of the list until a match is found or the whole list has been searched.
void search( int val)
{
 struct node *temp;
temp=head;
do
{
if(temp->data==val)
{
printf("\nElement found in the circular list");
return;
}
else
temp=temp->next;
}while(temp!=head);
printf("\nElement not found in the circular list");
}
Display/Traverse

Traversing the element is done by iterating from first to last element directly by using the head
pointer.

void display()
{
struct node * temp;
temp=head;
printf("\n Elements in the circular liked list are...");
do
{
printf("%d->",temp->data);
temp=temp->next;
}while(temp!=head);
}
POLYNOMIAL MANIPULATION
Polynomial manipulations are one of the most important applications of linked lists.
Polynomials are an important part of mathematics not inherently supported as a data type by
most languages. A polynomial is a collection of different terms, each comprising coefficients,
and exponents. It can be represented using a linked list. This representation makes polynomial
manipulation efficient.
While representing a polynomial using a linked list, each polynomial term represents a node in
the linked list. To get better efficiency in processing, we assume that the term of every
polynomial is stored within the linked list in the order of decreasing exponents. Also, no two
terms have the same exponent, and no term has a zero coefficient and without coefficients. The
coefficient takes a value of 1.

Each node of a linked list representing polynomial constitute three parts:

o The first part contains the value of the coefficient of the term.
o The second part contains the value of the exponent.
o The third part, LINK points to the next term (next node).

The structure of a node of a linked list that represents a polynomial is shown below:

struct poly

int coeff;

int power;

struct poly *next;

};

Consider a polynomial P(x) = 7x2 + 15x3 - 2 x2 + 9. Here 7, 15, -2, and 9 are the coefficients,
and 4,3,2,0 are the exponents of the terms in the polynomial. On representing this polynomial
using a linked list, we have
Observe that the number of nodes equals the number of terms in the polynomial. So we have 4
nodes. Moreover, the terms are stored to decrease exponents in the linked list. Such
representation of polynomial using linked lists makes the operations like subtraction, addition,
multiplication, etc., on polynomial very easy.

Creation of polynomial:

struct poly * insert(struct poly *p, int c,int pw)

{
struct poly *n1=(struct poly *)malloc(sizeof(struct poly));
struct poly *temp;
n1->coeff=c;
n1->power=pw;
n1->next=NULL;
if(p==NULL)
{
p=n1;
return p;
}
else
{
temp=p;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=n1;
return p;
}
}
Polynomial is created by performing repeated insertion of nodes at the end of the linked
list.

Addition of Polynomials:

To add two polynomials, we traverse the list P and Q. We take corresponding terms of the list
P and Q and compare their exponents. If the two exponents are equal, the coefficients are added
to create a new coefficient. If the new coefficient is equal to 0, then the term is dropped, and if
it is not zero, it is inserted at the end of the new linked list containing the resulting polynomial.
If one of the exponents is larger than the other, the corresponding term is immediately placed
into the new linked list, and the term with the smaller exponent is held to be compared with the
next term from the other list. If one list ends before the other, the rest of the terms of the longer
list is inserted at the end of the new linked list containing the resulting polynomial.

Example: 1

Let us consider an example an example to show how the addition of two polynomials is
performed,

P(x) = 3x4 + 2x3 - 4 x2 + 7

Q (x) = 5x3 + 4 x2 - 5

These polynomials are represented using a linked list in order of decreasing exponents as
follows:

Creation of Polynomial

To generate a new linked list for the resulting polynomials that is formed on the addition of
given polynomials P(x) and Q(x), we perform the following steps,

1. Traverse the two lists P and Q and examine all the nodes.
2. We compare the exponents of the corresponding terms of two polynomials. The first
term of polynomials P and Q contain exponents 4 and 3, respectively. Since the
exponent of the first term of the polynomial P is greater than the other polynomial Q,
the term having a larger exponent is inserted into the new list. The new list initially
 looks as shown below:

3. We then compare the exponent of the next term of the list P with the exponents of the
present term of list Q. Since the two exponents are equal, so their coefficients are added
and appended to the new list as follows:

4. Then we move to the next term of P and Q lists and compare their exponents. Since
exponents of both these terms are equal and after addition of their coefficients, we get
0, so the term is dropped, and no node is appended to the new list after this,

5. Moving to the next term of the two lists, P and Q, we find that the corresponding terms
have the same exponents equal to 0. We add their coefficients and append them to the
 new list for the resulting polynomial as shown below:

Example: 2

10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.

struct poly * addpoly(struct poly *p1, struct poly *p2)

{
struct poly *p3=NULL;
while(p1!=NULL&&p2!=NULL)
{
if(p1->power==p2->power)
{
p3=insert(p3,p1->coeff+p2->coeff,p1->power);
p1=p1->next;
p2=p2->next;
}
 else if (p1->power>p2->power)
{
p3=insert(p3,p1->coeff,p1->power);
p1=p1->next;
}
else
{
p3=insert(p3,p2->coeff,p2->power);
p2=p2->next;
}
}
while(p1!=NULL)
{
p3=insert(p3,p1->coeff,p1->power);
p1=p1->next;
}
while(p2!=NULL)
{
p3=insert(p3,p2->coeff,p2->power);
p2=p2->next;
}
return p3;
}

Display of polynomial

void display(struct poly *p)

{
printf("\nThe polynomial is...");
struct poly *temp;
temp=p;
while(temp!=NULL)
{
printf("%dx%d+",temp->coeff,temp->power);
temp=temp->next;
}
}
If linked lists are required and pointers are not available, then an alternate implementation
must be used. The alternate method we will describe is known as a cursor implementation.
The two important items present in a pointer implementation of linked lists are
1. The data is stored in a collection of structures. Each structure contains the data and a
pointer to the next structure.
2. A new structure can be obtained from the system's global memory by a call to malloc
and released by a call to free. Our cursor implementation must be able to simulate this.
The logical way to satisfy condition 1 is to have a global array of structures. For any cell
in the array, its array index can be used in place of an address.

typedef unsigned int node_ptr;

struct node
{
element_type element;
node_ptr next;
};
typedef node_ptr LIST;
typedef node_ptr position;
struct node CURSOR_SPACE[ SPACE_SIZE ];
To perform a free, we place the cell at the front of the freelist. Figure shows the cursor
implementation of malloc and free. Notice that if there is no space available, our routine
does the correct thing by setting p = 0. This indicates that there are no more cells left,
and also makes the second line of cursor_new a nonoperation (no-op).
position cursor_alloc( void )
{
position p;
p = CURSOR_SPACE[O].next;
CURSOR_SPACE[0].next = CURSOR_SPACE[p].next;
return p;
}
void cursor_free( position p)
{
CURSOR_SPACE[p].next = CURSOR_SPACE[O].next;
CURSOR_SPACE[O].next = p;
}
Given this, the cursor implementation of linked lists is straightforward. For consistency,
we will implement our lists with a header node. As an example, if the value of L is 5 and
the value of M is 3, then L represents the list a, b, e, and M represents the list c, d, f.
SPARSE MATRIX

A sparse matrix in data structures is a matrix where most of the elements are zero. It's
characterized by a significantly higher proportion of zero values compared to non-zero
values. Representing a sparse matrix efficiently is crucial, as storing all zero elements would
be wasteful in terms of memory and computation.

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.

Sparse Matrix Representations can be done in many way,s following are two common
representations:

1. Array representation

2. Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as

• Row: Index of row, where non-zero element is located

• Column: Index of column, where non-zero element is located

• Value: Value of the non zero element located at index - (row,column)

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:
• Row: Index of row, where non-zero element is located

• Column: Index of column, where non-zero element is located

• Value: Value of the non zero element located at index - (row,column)

• Next node: Address of the next node