Unit- I

INTRODUCTION TO DATA STRUCTURES

Representation of arrays
Array
An array is a type of linear data structure that is defined as a collection of elements
with same or different data types. They exist in both single dimension and multiple
dimensions.

 Element- Each item stored in an array is called an element

 Index – Each location of an element in an array, used to identify an element
Syntax
data_type array_name[array_size]={elements separated by commas}
or,
data_type array_name[array_size];
Representation of Arrays in Data Structures
The representation of an array can be defined by its declaration. A declaration
means allocating memory for an array of a given size.
 Index starts with 0.

Array length is 6 which means it can store 6 elements.

Each element can be accessed via its index. For example, we can fetch an element
at index 2 as 10.
Operations of Arrays in Data Structure

1.Creation and Initialization:

 Arrays are created with a specified size, determining the number of elements it can
hold.
 Initialization involves assigning initial values to the array's elements.
2. Insertion:
 Adding a new element to an array.
 This may involve shifting existing elements to accommodate the new element if
the array is full.
3. Deletion:
 Removing an element from an array.
 This may involve shifting subsequent elements to fill the gap left by the deleted
element.
4. Traversal:
 Accessing each element of the array sequentially.
 This is commonly done using loops to iterate through the array's indices.
5. Searching:
 Finding a specific element within the array.
 Linear search involves checking each element sequentially, while binary search
requires a sorted array.
6. Sorting:
 Arranging the elements of an array in a specific order (e.g., ascending or
descending).
 Common sorting algorithms include bubble sort, insertion sort, and merge sort.
7. Updating:
 Modifying the value of an existing element at a specific index.
8. Copying:
 Creating a new array with the same elements as an existing array.
9. Length Determination:
 Finding the number of elements currently stored in the array.
10. Resizing:
 Changing the capacity of the array, often involving creating a new array and
copying elements.

Applications of Array Data Structure:

Arrays mainly have advantages like random access and cache friendliness over
other data structures that make them useful.
Below are some applications of arrays.
 Storing and accessing data: Arrays store elements in a specific order and
allow constant-time O(1) access to any element.
 Searching: If data in array is sorted, we can search an item in O(log n) time.
We can also find floor(), ceiling(), kth smallest, kth largest, etc efficiently.
 Matrices: Two-dimensional arrays are used for matrices in computations like
graph algorithms and image processing.
 Implementing other data structures: Arrays are used as the underlying data
structure for implementing stacks and queues.
 Dynamic programming: Dynamic programming algorithms often use arrays
to store intermediate results of subproblems in order to solve a larger problem.
 Data Buffers: Arrays serve as data buffers and queues, temporarily storing
incoming data like network packets, file streams, and database results before
processing.
Advantages of Array Data Structure:
 Efficient and Fast Access: Arrays allow direct and efficient access to any
element in the collection with constant access time, as the data is stored in
contiguous memory locations.
 Memory Efficiency: Arrays store elements in contiguous memory, allowing
efficient allocation in a single block and reducing memory fragmentation.
 Versatility: Arrays can be used to store a wide range of data types, including
integers, floating-point numbers, characters, and even complex data structures
such as objects and pointers.
 Compatibility with hardware: The array data structure is compatible with
most hardware architectures, making it a versatile tool for programming in a
wide range of environments.
 Disadvantages of Array Data Structure:
 Fixed Size: Arrays have a fixed size set at creation. Expanding an array
requires creating a new one and copying elements, which is time-consuming
and memory-intensive.
 Memory Allocation Issues: Allocating large arrays can cause memory
exhaustion, leading to crashes, especially on systems with limited resources.
 Insertion and Deletion Challenges: Adding or removing elements requires
shifting subsequent elements, making these operations inefficient.
 Limited Data Type Support: Arrays support only elements of the same type,
limiting their use with complex data types.
 Lack of Flexibility: Fixed size and limited type support make arrays less
adaptable than structures like linked lists or trees.

Sparse Matrix Representation and Operations

Matrix types having most of their elements set to zero are called sparse matrices. In
other terms, the definition of a sparse matrix is one in which the number of 0
entries is greater than the number of non-zero elements.
What is a Sparse matrix?
A sparse matrix is defined as a 2-D matrix representing the total values of m x n
and is composed of n columns and m rows. A matrix is referred to as sparse if the
majority of its elements have a value of 0.
The use of a sparse matrix over a basic matrix is executed as
 Storage: Since fewer non-zero elements exist than zeroes, fewer elements can
be stored in a given amount of memory.
 Computing time: By logically creating a data structure that only traverses non-
zero components, computation time can be minimized.
The basic representation of a sparse matrix is given below:

Representatio
n of Sparse Matrix
 The triplets—columns, rows, and values—can be used to store the non-zero
elements of a sparse matrix. The following list includes two ways to express the
sparse matrix:
 Array representation
 Linked list representation

Array Representation of Sparse Matrix

It wastes a lot of memory to represent a sparse matrix using a 2D array. This is due
to the fact that 0s in a matrix are useless, making it wasteful to store them with
non-zero elements. To keep non-zero elements to prevent this kind of waste. The
storage space and traversal time decrease if it saves non-zero elements.
There are basically 3 fields utilized in the 2D array form of the sparse matrix, and
they are as follows:
 Row: The index of the row in the matrix where a non-zero component is
present.
 Column: It is defined as the index of the matrix column containing the non-0
element.
 Value: It refers to the non-0 value element at the index.

Let’s use the example below to illustrate how an array represents a sparse
matrix:

A 5×4 sparse matrix with 7 non-zero along with 13 – zero elements can be seen in
the image above. The above matrix requires 5×4 = 20 bytes of memory. The
wastage of space will rise as the matrix size increases.
 The representation of the matrix in tabular form will be:

The first column in the above picture denotes the rows, and the 2nd and the 3rd
columns will be the non-zero values. These triplets are shown in the table’s first
row. The initial triplet indicates that value four is kept in the first column and the
first row. Similar to the first triplet, the second shows that value 5 is kept in the
first row and third column. The triplets will represent the non-zero matrix
elements’ stored locations similarly.
The total non-zero items in the specified sparse matrix define the table size. The
memory space required by the above table, 8×3 = 24, is greater than that required
by a sparse matrix.
Linked List Representation of Sparse Matrix
The sparse matrix represented by a linked list provides the benefit of using a linked
list instead of an array for representing a sparse matrix is that it’s simpler to add or
remove nodes from a linked list than from an array.
A node present in the representation of a sparse matrix via a linked list has four
fields as opposed to three in the array representation. The linked list’s four fields
are listed as follows:
 Row: It depicts the representation of the position of the non-zero elements in the
row at the specified index.
 Column: It serves as a placeholder for the non-zero element’s column index.
 Value: This term refers to the non-zero element at the index (row as well as
column).
 Next node: It is defined as the address of the following node once it is stored.

The node is represented by each row in the output. In each row, the first element
denotes the non-zero element’s row index location, the second element denotes its
column index location, and the 3rd element denotes the actual non-zero element.
Operations on Sparse Matrix
Addition
In order to combine the matrices, a user can simply go over each element of each
matrix, one at a time, and insert the smaller element—the one with the smaller row
and column values—into the resulting matrix. If an element has the same column
and row values as another element, we add their values and insert the new data into
the final matrix.
Transpose
To make our comparisons easier and keep the sorted order, firstly calculate the
transpose of the 2nd matrix before multiplying the matrices. In order to obtain the
resultant matrix, the length of both matrices must be traversed, and the relevant
multiplied values must be added.
Any row in the 1st matrix with a value equal to x and any row in the 2nd matrix
(the transposed one) with a value equal to y will contribute to the result[x][y]. The
result [x][y] is derived by multiplying all elements with col values in both matrices
and only adding those with row values of x in the original matrix and y in the 2nd
transposed matrix.
Multiplication
To make our comparisons easier and keep the sorted order, first calculate the
transpose of the 2nd matrix before multiplying the matrices. In order to obtain the
resultant matrix, the length of matrices must be traversed, and the relevant
multiplied values must be added.

Linked List
A linked list is a linear collection of data elements whose order is not given
by their physical placement in memory
Linked lists are similar to arrays as they both are used to store a collection of data.
The drawbacks of using arrays are:
1. Once the elements are stored, it becomes difficult to insert or delete an element
at any position in a list.
2. Arrays have fixed size

Each node consists of two fields:

1. Data Field: It is a field that stores the element value of a specific data type in
the list.
2. Link Field: It is a pointer field used to point to the next consecutive node thereby
establishing a link between two nodes
Representation of Linked List in Memory
The representation of a linked list in the memory is shown in figure

The linked list consists of three nodes. Each node contains a data field and a link
field. The data field consists of any data item that is stored in a list such as,
numbers, characters, strings, and so on. The link field holds the address of the next
element.
A linked list can be represented in memory with the following declaration: struct
new_list {
int element_value;
struct new_list *next_element;
}; node1, node2, node3
Here, a linked list named “new_list” is created. In “new_list” the data field named
“element value” is declared.
Types of Linked Lists
The various types of linked list are:
1. Singly-linked list
2. Doubly-linked list
3. Circular singly-linked list
4. Circular doubly-linked list
Singly-Linked List
a singly-linked list consists of only one pointer that points to another node. It is
also known as a linear list because the last node in a singly-linked list is assigned a
NULL value and hence does not point to any other node. The first node in the list
is known as a HEAD or first node

The program flow is depicted below:

struct new_list {
int value;
struct new_list *next_element;
} n1, n2, n3, n4; //Creates four nodes of type new_list
void main() {
int j;
n1.value = 200; //Assigning value to node1
n2.value = 400; //Assigning value to node2
n3.value = 600; //Assigning value to node3
n4.value = 800; //Assigning value to node4
n1.next_element = &n2; //Assigning address of node2 to node1 n2.next_element =
&n3; //Assigning address of node3 to node2 n3.next_element = &n4; //Assigning
address of node4 to node3 n4.next_element = 0; //Assigning 0 to node4 to indicate
the end of the list
j=n1.next_element->value; //Storing the value of node1 in variable j
}
Doubly-Linked List
Doubly-linked list contains two pointers for each node in the list. The first pointer
points to the next element and the second pointer points to the previous element.
The previous pointer for the HEAD node points to NULL and the next pointer for
the last node points to NULL. Doubly-linked list is also known as a two-way list as
both forward and backward traversal is possible.
Figure depicts a doubly-linked list. The HEAD Node is a dummy node pointing to
Node1. Node1 has two pointers, the first pointer points to Node2 and the second
pointer points to HEAD Node. Likewise, Node2 and Node3 also have two pointers
to point to the next and the previous element in the list.
The program displays the value present in each node.
struct list {
int value;
struct list *next; //Creating a pointer to point to the next element
struct list *previous;//Creating a pointer to point to the previous element
} n1, n2, n3; //Creating three nodes of type list
void main() {
int j;
n1.value = 20; //Assigning value to node1
n2.value = 40; //Assigning value to node2
n3.value = 60; //Assigning value to node3
n1.next = &n2; //Assigning address of node2 to node1
n2.next = &n3; //Assigning address of node3 to node2
n2.previous = &n1; //Assigning address of node1 to node2
n3.previous = &n2; //Assigning address of node2 to node3
n3.next = 0; //Assigning 0 to node3 to indicate the end of the list
n1.previous = 0; //Assigning 0 to node1 to indicate there are no elements present
before node1
j = n1.next->value; //Storing the value of node1 in variable j
}
Circular Linked List
In a circular linked list, only one pointer is used to point to another node or next
element. It is known as a circular list because the last node’s pointer points to the
HEAD node.
Figure depicts a circular linked list. The linked list consists of four nodes like,
Node1, Node2, and Node3 with values 35, 65, and 85 respectively. The last node
which is Node3 points to the first node (Node1) and hence, the list continues to
form a loop.
The program shows the implementation of a circular linked list
Struct list {
int value;
struct list *next_element;
} n1, n2, n3; //Creates four nodes of type new_list
void main() {
int j; n1.value = 35; // Assigning value to node1
n2.value = 65; // Assigning value to node2
n3.value = 85; //Assigning value to node3
n1.next_element = &n2; //Assigning address of node2 to node1
n2.next_element = &n3; //Assigning address of node3 to node2
n3.next_element = &n1; //Assigning address of node3 to node1
j = n1.next_element->value; //Storing the value of node1 in variable j
}
Circular Doubly-Linked List
In a circular doubly-linked list, the previous pointer of the first node and the next
pointer of the last node point to the HEAD node. The HEAD node can have a
dummy data or it can store the total number of nodes present in the list.
Figure depicts a circular doubly-linked list. The linked list consists of four nodes
such as, HEAD node, Node1, Node2, and Node3 with values 3, 10, 15 and 20
respectively. Each node has two pointers to point to the next and previous
elements. The last node (Node3) points to the HEAD node and the HEAD node in
turn points to the first node (Node1).
The program shows the implementation of a circular doubly-linked list
struct list {
int value;
struct list *next; //Creating a pointer to point to the next element
struct list *previous; //Creating a pointer to point to the previous element
} n1, n2, n3, h; //Creates four nodes of type list
void main() {
int j;
n1.value = 10; //Assigning value to node1
n2.value = 15; //Assigning value to node2
n3.value = 20; //Assigning value to node3
h.value = 3; //Assigning value to HEAD node
n1.next = &n2; ; //Assigning address of node2 to node1
n2.next = &n3; //Assigning address of node3 to node2
n3.next = &h; //Assigning address of HEAD node to node3
h.next = &n1; //Assigning address of node1 to HEAD node
n1.previous = &h; //Assigning address of node1 to HEAD node
n2.previous = &n1; //Assigning address of node1 to node2
n3.previous = &n2 //Assigning address of node2 to node3
h.previous = &n3; //Assigning address of node3 to HEAD node
j = n1.next_element->value; //Storing the value of node1 in variable j
}
Linked List Operations
The elements are stored in a list that contains a field called a link or a pointer. The
pointer contains the address of the next element in the list. In linked list, it is not
essential that consecutive elements occupy contiguous space in memory. Hence it
is easy to traverse and insert and delete items in the linked list.
The Linked list Operations are:
1. Traversing a Linked List
2. Searching a Linked List
3. Inserting a Node into a Linked List
4. Deleting a Node from a Linked List

1. Traversing a Linked List

Traversing a linked list involves processing every node present in a list. It is useful
to perform various operations such as, reversing the order of elements present in a
list, sorting the elements in ascending or descending order, and so on.

Figure depicts the traversal of a list. The figure shows a list consisting of HEAD
or the START node pointing to the first node (Node1). The last node (Node4)
points to NULL indicating the end of the list. It also includes a pointer variable
named current to point to the next node.
The program shows the implementation of a traversal of a linked list
HEAD=11;
PTR=HEAD;
cout<<“Initially entered list”;
while(PTR!=-1) {
cout<< LIST[PTR];
PTR=LIST1[PTR];
}
PTR=HEAD;
while(PTR!=-1) {
MULT(PTR);
PTR=LIST1[PTR];
}
PTR=HEAD;
cout<<”List after traversal:”;
while(PTR!=-1) {
cout<< LIST[PTR];
PTR=LIST1[PTR];
}
 An integer pointer named PTR is declared to point to the next element.
 An integer variable named HEAD is declared to specify the current position
of the PTR.
 A list of values are assigned for LIST[ ] and LIST1[ ].
 The PTR is set at position 11 in the list.
 The first while loop, prints the value present in LIST[11] (6) and then
traverses to the eleventh element of LIST1[11] whose value is 16. The list
then traverses back to LIST[16] and prints its value (79) as shown in the
output.
2. Searching a Linked List
The search operation involves traversing through the list to search for a specific item. Several
iterations may be performed until the desired number is found or until the end of the list is
reached.
The element is searched in the list by using a key.
Program
cout<<”Enter the number to search”;
cin>>NUM;
NUM_LOC=SEARCH(NUM);
if(NUM_LOC==-1)
cout<<” number is not present in the list”;
else
cout<<“ number %d is present at index location %d in the list”<< NUM, NUM_LOC;
int SEARCH(int I){
int p=HEAD;
int L=-1;
while(p!=-1) {
If(I==LIST[p]) {
 L=p; break;
}
else p=LIST1[p];
}
return(L);
}
Example
Traversed List:
75 55 19 10 45 60 20 8 80 35 12 68
Enter the number to search
8
Number 8 is present at index location 9 in the list
1. Two integer lists named LIST[ ] and LIST1[ ] are declared with an element storage capacity
of 20.
2. An integer pointer named PTR is declared to point to the next element
3. An integer variable named HEAD is declared to specify the current position of the PTR.
4. A list of values are assigned for LIST[ ] and LIST1[ ].
5. The PTR is set at position 16 in the list.
6. The first while loop prints the value present in LIST[16] which is (75) and traverses to the
third element of LIST1[16] whose value is 0. The list then traverses back to LIST[0] and
then prints its value (55) as shown in the output.
7. Steps 5 and 6 are repeated for each element until the PTR is not equal to -1, which depicts
the end of the elements in a list.
8. The program prompts the input from the user to search a specific number in the list.
9. If the number entered is equal to HEAD, then the while loop is terminated. Otherwise, the
LIST1[p] is stored in p. The while loop iterates again and again until p reaches the end of the
list.
10. If the NUM_LOC has not reached the end of the list, then the NUM and NUM_LOC will be
printed. Otherwise, a message saying “number not present in the list” is displayed

3. Inserting a Node into a Linked List

Insertion is one of the basic operations in linked lists. There are three types of insertions that
can be carried out:
1. Inserting a node at the beginning of a list
2. Inserting a node at the end of the list
3. Inserting a node after a given node
Figure depicts the insertion of a new node
The linked list consists of five nodes such as, HEAD node, Node1, Node2, Node3, and
Node4 respectively. Suppose, insert node N between Node2 and Node3, then Node2 will
point to new node N and node N will point to Node3
1 Inserting a Node at the Beginning of a List
Let us consider HEAD as the initial position in a linked list, num as the input entered by the
user, PTR as the pointer pointing to the next node address, and newnode as the node being
inserted in the list.
Algorithm to insert a new node at the beginning of a list is as follows:
1. Input the value to be inserted
2. Create a new node N
3. Store the DATA in the data field of the node
4. If HEAD is equal to NULL, then assign link field of newnode to NULL. Otherwise, assign
HEAD to link field of newnode. The new node now points to HEAD.
5. Exit
Program
void insert_beg(int num) {
newnode=(struct list*)malloc(sizeof(struct list));
newnode->value=num;
if(HEAD==NULL) {
HEAD=newnode;
newnode->next=NULL;
} else {
newnode->next=HEAD;
HEAD=newnode;
}}
Example
Enter the number to be inserted:
60
After insertion at the beginning, the list is:
Node1: 60
Node2: 40
Node3: 50
In this example:
1. A list is created with a data field named value and link field named *next.
2. Three pointers are created namely, HEAD, PTR and newnode. HEAD points to the first
node, PTR points to the next element, and newnode signifies the new node yet to be created.
Inserting a Node after a Given Node
Let us consider START as the initial position in a list, data as the input entered by a user,
pos as any position in the list where the data will be inserted, and q and temp as the
temporary pointers to hold the node address.
Algorithm to insert a new node after a given node is as follows:
1. Input the data
2. Specify the pos where the data is to be inserted
3. Initialize q to START.
4. If q is equal to NULL, then print “there are less elements present in the list than the
entered position number”
5. for (i=0;ilink; temp=(struct node*)malloc(sizeof (struct node)); temp->link=q->link; temp-
>value=data; q->link=temp;
6. Repeat step 5 until i value is not less than pos-1
7. Exit.
Program
cout<<"Enter the element:";
cin>>m;
cout<<”Enter the position after which you want to insert the element:";
cin>>position;
add_after(m,position);
void add_after(int data,int pos) {
struct node *temp,*q; int i;
q=START;
for(i=0;i<pos-1;i++){
q=qlink;
if(q==NULL) {
cout<<"There are less than %d elements"<<pos;
 The function add_after() prompts the user to enter the input for the element data and
the position number where the data is to be stored.
 The for statement in the add_after() function searches for the position to insert the
new element.
  If the user enters a position that is less than the actual elements, then a message
saying “there are less elements present than the entered position number” is
displayed.
Deleting a Node from a Linked List
Figure depicts the deletion of a node from the linked list

The linked list consists of five nodes such as, START, Node1, Node2, Node3, and Node4
respectively. If Node3 has to be deleted from the list, then assign the address of Node4 to
Node2.
This is represented as:
Node2->next=&Node4
Program
cout<<" Enter the element for deletion:";
cin>>m;
delete(m);
void delete(int data) {
struct node *temp,*q;
if (START->value == data) {
temp=START;
START=START->link; //to delete first element free(temp);
return;
}
q=START;
while(q->link->link != NULL) {
if(q->link->value == data) //to delete element in between
{
temp=q->link;
q->link=temp->link;
free(temp);
return;
}
q=q->link;
}
if(q->link->value==data) //to delete last element
{
temp=q->link;
free(temp);
q->link=NULL;
return;
}
The delete() function compares the data entered by the user with the START element if both
are equal then the first element is deleted. Otherwise, the elements in the other nodes are
verified with the entered data and the deletion of the element takes place accordingly