1

UNIT II

………………………………………..........
LINKED LISTS
A linked list is a way to store a collection of elements. Each element in a linked list is stored in
the form of a node. A data part stores the element and a next part stores the link to the next
node.

Linked List:
 2

why need linked list :(advantages of linked list)

Linked lists are needed in certain situations where other data structures, like arrays, might not be as
efficient or practical. Here's why you might choose to use a linked list:

1. Dynamic Size:
o Linked lists allow for dynamic memory allocation. You don't need to specify the size
ahead of time, and you can easily grow or shrink the list without worrying about
running out of space or resizing like in arrays.
2. Efficient Insertions and Deletions:
o In linked lists, you can add or remove elements in constant time O(1),especially at the
beginning or middle of the list (if you have a reference to the node). This is much
faster than arrays, where shifting elements is required after insertion or deletion.
3. No Wasted Space:
o Linked lists allocate memory for each element as needed, meaning there's no wasted
space (unlike arrays, which might allocate more memory than needed, leading to
waste).
4. Flexibility:
o Linked lists are flexible in the sense that they can be used to implement other data
structures like stacks, queues, and graphs. You can easily modify the structure based
on the needs of your algorithm.
5. Efficient Memory Usage:
o Linked lists don't require contiguous memory space, so they can be useful in
situations with fragmented memory or when memory needs to be allocated on the fly.
 3

Draw backs of linked list :

While linked lists offer several advantages, they also come with certain drawbacks. Here are the
main disadvantages:

1. Memory Overhead:
o Each node in a linked list requires additional memory to store a reference (or pointer)
to the next (and possibly previous) node. This pointer overhead can be significant,
especially for small data elements.
2. Sequential Access:
o Linked lists do not support direct access to elements by index (like arrays do). To
access a particular element, you have to traverse the list from the beginning, which
can be slow for large lists. This leads to slower performance for search operations,
which typically take O(n)O(n)O(n) time.
3. Cache Locality:
o Arrays benefit from better cache locality because their elements are stored in
contiguous memory locations. In contrast, linked list nodes are scattered in memory,
making it less cache-friendly and potentially slower in terms of accessing data.
4. Complexity in Implementation:
o Linked lists require more complex implementation and management compared to
arrays. You need to handle pointer manipulation carefully, especially in operations
like insertion, deletion, and traversal. This can increase the chance of errors, like
memory leaks or null pointer exceptions.
5. No Random Access:
o With arrays, you can directly access any element using an index, but in a linked list,
you can only access elements sequentially. This makes linked lists inefficient for
certain operations where quick access to arbitrary elements is required.
6. Slower Traversal:
o Traversing a linked list is slower than traversing an array, as you need to follow
pointers from one node to the next rather than accessing elements directly via indices.
7. Overhead for Small Data:
o If the data in each node is small, the overhead of storing pointers can outweigh the
benefits. For small datasets, arrays can be more efficient both in terms of time and
space.

Linked list
Linked list is a linear data structure that includes a series of
connected nodes. Linked list can be defined as the nodes that are randomly stored in the
memory. A node in the linked list contains two parts, i.e.,

first is the data part and second is the address part. The last node of the list contains a pointer
to the null. After array, linked list is the second most used data structure. In a linked list, every
link contains a connection to another link.
 4

Representation of a Linked list

Linked list can be represented as the connection of nodes in which each node points to the
next node of the list. The representation of the linked list is shown below -
5
6
7
 8

Why use linked list over array?

Linked list is a data structure that overcomes the limitations of arrays. Let's first see some of
the limitations of arrays -

o The size of the array must be known in advance before using it in the program.
o Increasing the size of the array is a time taking process. It is almost impossible to expand
the size of the array at run time.
o All the elements in the array need to be contiguously stored in the memory. Inserting an
element in the array needs shifting of all its predecessors.
Linked list is useful because -

o It allocates the memory dynamically. All the nodes of the linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
o In linked list, size is no longer a problem since we do not need to define its size at the time
of declaration. List grows as per the program's demand and limited to the available memory
space.

How to declare a linked list?

It is simple to declare an array, as it is of single type, while the declaration of linked list is a bit
more typical than array. Linked list contains two parts, and both are of different types, i.e., one
is the simple variable, while another is the pointer variable. We can declare the linked list by
using the user-defined data type structure.

The declaration of linked list is given as follows -

1. struct node
2. {
3. int data;
4. struct node *next;
5. }
In the above declaration, we have defined a structure named
as node that contains two variables, one is data that is of integer type, and another one
is next that is a pointer which contains the address of next node.

Now, let's move towards the types of linked list.

Types of Linked list

 9

Following are the various types of linked list.

1.Singly Linked Lists

Singly linked lists contain two "buckets" in one node; one bucket holds the data
and the other bucket holds the address of the next node of the list. Traversals
can be done in one direction only as there is only a single link between two
nodes of the same list.

2. Doubly Linked Lists

Doubly Linked Lists contain three "buckets" in one node; one bucket holds the
data and the other buckets hold the addresses of the previous and next nodes
in the list. The list is traversed twice as the nodes in the list are connected to
each other from both sides.

3. Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list.

Since the last node and the first node of the circular linked list are connected,
the traversal in this linked list will go on forever until it is broken.
 10

Basic Operations in Linked List

The basic operations in the linked lists are insertion, deletion, searching,
display, and deleting an element at a given key. These operations are
performed on Singly Linked Lists as given below −

 Insertion − Adds an element at the beginning of the list.

 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.

Advantages of Linked list

The advantages of using the Linked list are given as follows -

o Dynamic data structure - The size of the linked list may vary according to the
requirements. Linked list does not have a fixed size.
o Insertion and deletion - Unlike arrays, insertion, and deletion in linked list is easier. Array
elements are stored in the consecutive location, whereas the elements in the linked list are
stored at a random location. To insert or delete an element in an array, we have to shift the
elements for creating the space. Whereas, in linked list, instead of shifting, we just have to
update the address of the pointer of the node.
o Memory efficient - The size of a linked list can grow or shrink according to the
requirements, so memory consumption in linked list is efficient.
o Implementation - We can implement both stacks and queues using linked list.

Disadvantages of Linked list

The limitations of using the Linked list are given as follows -

o Memory usage - In linked list, node occupies more memory than array. Each node of the
linked list occupies two types of variables, i.e., one is a simple variable, and another one is
the pointer variable.
o Traversal - Traversal is not easy in the linked list. If we have to access an element in the
linked list, we cannot access it randomly, while in case of array we can randomly access it
by index. For example, if we want to access the 3rd node, then we need to traverse all the
nodes before it. So, the time required to access a particular node is large.
o Reverse traversing - Backtracking or reverse traversing is difficult in a linked list. In a
doubly-linked list, it is easier but requires more memory to store the back pointer.

Applications of Linked list

The applications of the Linked list are given as follows -

o With the help of a linked list, the polynomials can be represented as well as we can perform
the operations on the polynomial.
 11

o A linked list can be used to represent the sparse matrix.

o The various operations like student's details, employee's details, or product details can be
implemented using the linked list as the linked list uses the structure data type that can hold
different data types.
o Using linked list, we can implement stack, queue, tree, and other various data structures.
o The graph is a collection of edges and vertices, and the graph can be represented as an
adjacency matrix and adjacency list. If we want to represent the graph as an adjacency
matrix, then it can be implemented as an array. If we want to represent the graph as an
adjacency list, then it can be implemented as a linked list.
o A linked list can be used to implement dynamic memory allocation. The dynamic memory
allocation is the memory allocation done at the run-time.

What is Single Linked List?

Simply a list is a sequence of data, and the linked list is a sequence of data linked with each other.
The formal definition of a single linked list is as follows...
Single linked list is a sequence of elements in which every element has link to its next element in
the sequence.
In any single linked list, the individual element is called as "Node". Every "Node" contains two fields, data
field, and the next field. The data field is used to store actual value of the node and next field is used to
store the address of next node in the sequence.
The graphical representation of a node in a single linked list is as follows...

Example:
 12

Operations on Single Linked List

The following operations are performed on a Single Linked List

 Insertion
 Deletion
 Display

Before we implement actual operations, first we need to set up an empty list. First, perform the following
steps before implementing actual operations.

 Step 1 - Include all the header files which are used in the program.
 Step 2 - Declare all the user defined functions.
 Step 3 - Define a Node structure with two members data and next
 Step 4 - Define a Node pointer 'head' and set it to NULL.
 Step 5 - Implement the main method by displaying operations menu and make suitable function
calls in the main method to perform user selected operation.

Insertion
In a single linked list, the insertion operation can be performed in three ways. They are as follows...

1. Inserting At Beginning of the list

2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
 Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.
 13

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list…

 Step 1 – Create a newNode with given value and newNode → next as NULL.
 Step 2 – Check whether list is Empty (head == NULL).
 Step 3 – If it is Empty then, set head = newNode.
 Step 4 – If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 – Keep moving the temp to its next node until it reaches to the last node in the list (until temp
→ next is equal to NULL).
 Step 6 – Set temp → next = newNode.
 14

Inserting At Specific location in the list (After

a Node)
We can use the following steps to insert a new node after a node in the single linked list…

Step 1 – Create a newNode with given value.

Step 2 – Check whether list is Empty (head == NULL)
Step 3 – If it is Empty then, set newNode →
next = NULL and head = newNode.
Step 4 – If it is Not Empty then, define a node pointer temp and initialize
with head.
Step 5 – Keep moving the temp to its next node until it reaches to the node after
which we want to insert the newNode (until temp1 → data is equal to location,
here location is the node value after which we want to insert the newNode).
Step 6 – Every time check whether temp is reached to last node or not. If it is
reached to last node then display ‘Given node is not found in the list!!!
Insertion not possible!!!’ and terminate the function. Otherwise move
the temp to next node.
Step 7 – Finally, Set ‘newNode → next = temp → next‘ and ‘temp →
next = newNode‘
 15

Deletion
In a single linked list, the deletion operation can be performed in three ways. They are as
follows…

1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list…

 Step 1 – Check whether list is Empty (head == NULL)

 Step 2 – If it is Empty then, display ‘List is Empty!!! Deletion is not possible’ and terminate the
function.
 Step 3 – If it is Not Empty then, define a Node pointer ‘temp’ and initialize with head.
 Step 4 – Check whether list is having only one node (temp → next == NULL)
 Step 5 – If it is TRUE then set head = NULL and delete temp (Setting Empty list conditions)
 Step 6 – If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list…
 16

 Step 1 – Check whether list is Empty (head == NULL)

 Step 2 – If it is Empty then, display ‘List is Empty!!! Deletion is not possible’ and
terminate the function.
 Step 3 – If it is Not Empty then, define two Node pointers ‘temp1’ and ‘temp2′ and
initialize ‘temp1‘ with head.
 Step 4 – Check whether list has only one Node (temp1 → next == NULL)
 Step 5 – If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
 Step 6 – If it is FALSE. Then, set ‘temp2 = temp1 ‘ and move temp1 to its next node.
Repeat the same until it reaches to the last node in the list. (until temp1 → next == NULL)
 Step 7 – Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list…

 Step 1 – Check whether list is Empty (head == NULL)

 Step 2 – If it is Empty then, display ‘List is Empty!!! Deletion is not possible’ and terminate the
function.
 Step 3 – If it is Not Empty then, define two Node pointers ‘temp1’ and ‘temp2‘ and initialize
‘temp1‘ with head.
 Step 4 – Keep moving the temp1 until it reaches to the exact node to be deleted or to the last node.
And every time set ‘temp2 = temp1‘ before moving the ‘temp1‘ to its next node.
 Step 5 – If it is reached to the last node then display ‘Given node not found in the list! Deletion not
possible!!!’. And terminate the function.
 Step 6 – If it is reached to the exact node which we want to delete, then check whether list is having
only one node or not
 17

 Step 7 – If list has only one node and that is the node to be deleted, then set head = NULL and
delete temp1 (free(temp1)).
 Step 8 – If list contains multiple nodes, then check whether temp1 is the first node in the list (temp1
== head).
 Step 9 – If temp1 is the first node then move the head to the next node (head = head → next) and
delete temp1.
 Step 10 – If temp1 is not first node then check whether it is last node in the list (temp1 → next ==
NULL).
 Step 11 – If temp1 is last node then set temp2 → next = NULL and delete temp1 (free(temp1)).
 Step 12 – If temp1 is not first node and not last node then set temp2 → next = temp1 → next and
delete temp1 (free(temp1)).
 18

Displaying a Single Linked List

We can use the following steps to display the elements of a single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
 Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Traversal of Singly Linked List:

Traversal of Singly Linked List is one of the fundamental operations, where we traverse or visit each node of
the linked list. In this article, we will cover how to traverse all the nodes of a singly linked list along with its
implementation.

Traversal of Singly Linked List (Iterative Approach)

The process of traversing a singly linked list involves printing the value reach
thelast node in the singly linked list, whose next node points towards the null.
Step-by-Step Algorithm:
 We will initialize a temporary pointer to the head node of the singly linked list.
 After that, we will check if that pointer is null or not null, if it is null, then
return.
 19

 While the pointer is not null, we will access and print the data of the current
node, then we move the pointer to next node.
20
 21

Doubly linked list

Doubly linked list is a complex type of linked list in
which a node contains a pointer to the previous as well as the next node in the sequence.
Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the
next node in sequence (next pointer) , pointer to the previous node (previous pointer). A
sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data
part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. }
 22

The prev part of the first node and the next part of the last
node will always contain null indicating end in each direction.
In a singly linked list, we could traverse only in one direction, because each node contains
address of the next node and it doesn't have any record of its previous nodes. However,
doubly linked list overcome this limitation of singly linked list. Due to the fact that, each
node of the list contains the address of its previous node, we can find all the details about
the previous node as well by using the previous address stored inside the previous part of
each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in
the following image. Generally, doubly linked list consumes more space for every node and
therefore, causes more expansive basic operations such as insertion and deletion. However,
we can easily manipulate the elements of the list since the list maintains pointers in both
the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The
head pointer points to the starting address 1. Since this is the first element being added to
the list therefore the prev of the list contains null. The next node of the list resides at
address 4 therefore the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next
part.
 23

Operations on Double Linked List

In a double linked list, we perform the following operations...

1. Insertion
2. Deletion
3. Display

Insertion
In a double linked list, the insertion operation can be performed in three ways as follows...

1. Inserting At Beginning of the list

2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the double linked list...

 Step 1 - Create a newNode with given value and newNode → previous as NULL.
 Step 2 - Check whether list is Empty (head == NULL)
 24

 Step 3 - If it is Empty then, assign NULL to newNode → next and newNode to head.
 Step 4 - If it is not Empty then, assign head to newNode → next and newNode to head.

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the double linked list...

 Step 1 - Create a newNode with given value and newNode → previous as NULL.
 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, assign NULL to newNode → next and newNode to head.
 Step 4 - If it is not Empty then, assign head to newNode → next and newNode to head.

Inserting At End of the list

We can use the following steps to insert a new node at end of the double linked list...

 Step 1 - Create a newNode with given value and newNode → next as NULL.
 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty, then assign NULL to newNode → previous and newNode to head.
 Step 4 - If it is not Empty, then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next is equal to NULL).
 Step 6 - Assign newNode to temp → next and temp to newNode → previous.
 25

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the double linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, assign NULL to both newNode → previous & newNode →
next and set newNode to head.
 Step 4 - If it is not Empty then, define two node pointers temp1 & temp2 and
initialize temp1 with head.
 Step 5 - Keep moving the temp1 to its next node until it reaches to the node after which we want
to insert the newNode (until temp1 → data is equal to location, here location is the node value
after which we want to insert the newNode).
 Step 6 - Every time check whether temp1 is reached to the last node. If it is reached to the last
node then display 'Given node is not found in the list!!! Insertion not possible!!!' and
terminate the function. Otherwise move the temp1 to next node.
 Step 7 - Assign temp1 → next to temp2, newNode to temp1 → next, temp1 to newNode →
previous, temp2 to newNode → next and newNode to temp2 → previous.
 26

Deletion
In a double linked list, the deletion operation can be performed in three ways as follows...

1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the double linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Check whether list is having only one node (temp → previous is equal to temp →
next)
 Step 5 - If it is TRUE, then set head to NULL and delete temp (Setting Empty list conditions)
 Step 6 - If it is FALSE, then assign temp → next to head, NULL to head → previous and
delete temp.
 27

Deleting from End of the list

We can use the following steps to delete a node from end of the double linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty, then display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Check whether list has only one Node (temp → previous and temp → next both
are NULL)
 Step 5 - If it is TRUE, then assign NULL to head and delete temp. And terminate from the
function. (Setting Empty list condition)
 Step 6 - If it is FALSE, then keep moving temp until it reaches to the last node in the list.
(until temp → next is equal to NULL)
 Step 7 - Assign NULL to temp → previous → next and delete temp.


 28

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the double linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is not Empty, then define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep moving the temp until it reaches to the exact node to be deleted or to the last
node.
 Step 5 - If it is reached to the last node, then display 'Given node not found in the list!
Deletion not possible!!!' and terminate the fuction.
 Step 6 - If it is reached to the exact node which we want to delete, then check whether list is
having only one node or not
 Step 7 - If list has only one node and that is the node which is to be deleted then
set head to NULL and delete temp (free(temp)).
 Step 8 - If list contains multiple nodes, then check whether temp is the first node in the list (temp
== head).
 Step 9 - If temp is the first node, then move the head to the next node (head = head → next),
set head of previous to NULL (head → previous = NULL) and delete temp.
 Step 10 - If temp is not the first node, then check whether it is the last node in the list (temp →
next == NULL).
 Step 11 - If temp is the last node then set temp of previous of next to NULL (temp →
previous → next = NULL) and delete temp (free(temp)).
 Step 12 - If temp is not the first node and not the last node, then
set temp of previous of next to temp of next (temp → previous → next = temp →
next), temp of next of previous to temp of previous (temp → next → previous = temp →
previous) and delete temp (free(temp)).
 29

Singly Linked List Doubly Linked List

Each node consists of a data value and a Each node consists of a data value, a pointer to the next node,
pointer to the next node. and a pointer to the previous node.

Traversal can occur in one way only (forward

Traversal can occur in both ways.
direction).

It requires less space. It requires more space because of an extra pointer.

It has multiple usages. It can be implemented on the stack, heap,

It can be implemented on the stack.
and binary tree.

Circular Linked List

What is Circular Linked List?

In single linked list, every node points to its next node in the sequence and the last node points NULL.

But in circular linked list, every node points to its next node in the sequence but the last node points to

the first node in the list.

A circular linked list is a sequence of elements in which every element has a link to its next

element in the sequence and the last element has a link to the first element.
 30

Operations
In a circular linked list, we perform the following operations...

1. Insertion
2. Deletion
3. Display

Before we implement actual operations, first we need to setup empty list. First perform the following
steps before implementing actual operations.

 Step 1 - Include all the header files which are used in the program.
 Step 2 - Declare all the user defined functions.
 Step 3 - Define a Node structure with two members data and next
 Step 4 - Define a Node pointer 'head' and set it to NULL.
 Step 5 - Implement the main method by displaying operations menu and make suitable function
calls in the main method to perform user selected operation.

Insertion
In a circular linked list, the insertion operation can be performed in three ways. They are as follows...

1. Inserting At Beginning of the list

2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the circular linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set head = newNode and newNode→next = head .
 Step 4 - If it is Not Empty then, define a Node pointer 'temp' and initialize with 'head'.
 Step 5 - Keep moving the 'temp' to its next node until it reaches to the last node (until 'temp →
next == head').
 31

 Step 6 - Set 'newNode → next =head', 'head = newNode' and 'temp → next = head'.

Inserting At End of the list

We can use the following steps to insert a new node at end of the circular linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL).
 Step 3 - If it is Empty then, set head = newNode and newNode → next = head.
 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next == head).
 Step 6 - Set temp → next = newNode and newNode → next = head.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the circular linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set head = newNode and newNode → next = head.
 32

 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the node after which we want
to insert the newNode (until temp1 → data is equal to location, here location is the node value
after which we want to insert the newNode).
 Step 6 - Every time check whether temp is reached to the last node or not. If it is reached to last
node then display 'Given node is not found in the list!!! Insertion not possible!!!' and
terminate the function. Otherwise move the temp to next node.
 Step 7 - If temp is reached to the exact node after which we want to insert the newNode then
check whether it is last node (temp → next == head).
 Step 8 - If temp is last node then set temp → next = newNode and newNode → next = head.
 Step 8 - If temp is not last node then set newNode → next = temp → next and temp →
next = newNode.

Deletion
In a circular linked list, the deletion operation can be performed in three ways those are as follows...

1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the circular linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 33

 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize both
'temp1' and 'temp2' with head.
 Step 4 - Check whether list is having only one node (temp1 → next == head)
 Step 5 - If it is TRUE then set head = NULL and delete temp1 (Setting Empty list conditions)
 Step 6 - If it is FALSE move the temp1 until it reaches to the last node. (until temp1 →
next == head )
 Step 7 - Then set head = temp2 → next, temp1 → next = head and delete temp2.

Deleting from End of the list

We can use the following steps to delete a node from end of the circular linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
 Step 4 - Check whether list has only one Node (temp1 → next == head)
 Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate from the
function. (Setting Empty list condition)
 Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat the
same until temp1 reaches to the last node in the list. (until temp1 → next == head)
 Step 7 - Set temp2 → next = head and delete temp1.
 34

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the circular linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
 Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to the last
node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.
 Step 5 - If it is reached to the last node then display 'Given node not found in the list!
Deletion not possible!!!'. And terminate the function.
 Step 6 - If it is reached to the exact node which we want to delete, then check whether list is
having only one node (temp1 → next == head)
 Step 7 - If list has only one node and that is the node to be deleted then set head = NULL and
delete temp1 (free(temp1)).
 Step 8 - If list contains multiple nodes then check whether temp1 is the first node in the list
(temp1 == head).
 Step 9 - If temp1 is the first node then set temp2 = head and keep moving temp2 to its next
node until temp2 reaches to the last node. Then set head = head → next, temp2 → next
= head and delete temp1.
 Step 10 - If temp1 is not first node then check whether it is last node in the list (temp1 → next
== head).
 Step 1 1- If temp1 is last node then set temp2 → next = head and delete temp1 (free(temp1)).
 Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 →
next and delete temp1 (free(temp1)).

Displaying a circular Linked List

We can use the following steps to display the elements of a circular linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 35

 Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
 Step 5 - Finally display temp → data with arrow pointing to head → data.

Difference between Arrays and Linked List?

Arrays Linked List
1. Arrays are used in the predictable storage 1. Linked List are used in the unpredictable
requirement ie; exert amount of data storage storage requirement ie; exert amount of data
required by the program can be determined. storage required by the program can’t be
2. In arrays the operations such as insertion determined.
and deletion are done in an inefficient 2. In Linked List the operations such as
manner. insertion and deletion are done more efficient
3. The insertion and deletion are done by manner ie; only by changing the pointer.
moving the elements either up or down. 3. The insertion and deletion are done by only
4. Successive elements occupy adjacent space changing the pointers.
on memory. 4. Successive elements need not occupy
5. In arrays each location contain DATA only adjacent space.
6. The linear relation ship between the data 5. In linked list each location contains data
elements of an array is reflected by the and pointer to denote whether the next
physical relation ship of data in the memory. element present in the memory.
7. In array declaration a block of memory 6. The linear relation ship between the data
space is required. elements of a Linked List is reflected by the
8. There is no need of storage of pointer or Linked field of the node.
lines 7. In Linked list there is no need of such
9. The Conceptual view of an Array is as thing.
follows: 8. In Linked list a pointer is stored along into
the element.
9. The Conceptual view of Linked list is as
 36

follows:

10.In array there is no need for an element to

specify whether the next is stored

10. There is need for an element (node) to

specify whether the next node is formed.

Applications of linked lists:

1. Sparse matrix Representation
2. Polynomial representation
3. Dynamic storage
management

1.Polynomial Representation

Polynomials are mathematical expressions made up of variables (often

represented by letters like x, y, etc.), constants (like numbers), and exponents
(which are non-negative integers). These expressions are combined using
addition, subtraction, and multiplication operations.
A polynomial can have one or several terms. Each term is a product of a
constant and a variable raised to an exponent.
For Example:

• 3x3 + 5x2 – 4x,

 37

Array implementation:

Linked list implementation:

Procedure
 38

Procedure to add polynomials using linked list

39
 40

2.Sparse matrix Representation:

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.

Now, the question arises: we can also use the simple matrix to store the elements,
then why is the sparse matrix required?

Why is a sparse matrix required if we can use the

simple matrix to store elements?

There are the following benefits of using the sparse matrix -

Storage - We know that a sparse matrix 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 in 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.

Representation of sparse matrix

Now, let's see the representation of the sparse matrix. The non-zero elements in the
sparse matrix can be stored using triplets that are rows, columns, and values. There
are two ways to represent the sparse matrix that are listed as follows -

o Array representation
o Linked list representation
 41

Array representation of the sparse matrix

Representing a sparse matrix by a 2D array leads to the wastage of lots of memory.

This is because zeroes in the matrix are of no use, so storing zeroes with non-zero
elements is wastage of memory. 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.

In 2D array representation of sparse matrix, there are three fields used that are
named as -

o Row - It is the index of a row where a non-zero element is located in the

matrix.
o Column - It is the index of the column where a non-zero element is located in
the matrix.
o Value - It is the value of the non-zero element that is located at the index
(row, column).
Example -

Let's understand the array representation of sparse matrix with the help of the
example given below -

Consider the sparse matrix -

 42

In the above figure, we can observe a 5x4 sparse matrix containing 7 non-zero
elements and 13 zero elements. The above matrix occupies 5x4 = 20 memory space.
Increasing the size of matrix will increase the wastage space.

The tabular representation of the above matrix is given below -

Linked List representation of the sparse matrix

In a linked list representation, the linked list data structure is used to represent the
sparse matrix. The advantage of using a linked list to represent the sparse matrix is
that the complexity of inserting or deleting a node in a linked list is lesser than the
array.

Unlike the array representation, a node in the linked list representation consists of
four fields. The four fields of the linked list are given as follows -

o Row - It represents the index of the row where the non-zero element is
located.
o Column - It represents the index of the column where the non-zero element
is located.
o Value - It is the value of the non-zero element that is located at the index
(row, column).
o Next node - It stores the address of the next node.
 43

The node structure of the linked list representation of the sparse matrix is shown in
the below image -

Example -

Let's understand the linked list representation of sparse matrix with the help of the
example given below -

Consider the sparse matrix -

In the above figure, we can observe a 4x4 sparse matrix containing 5 non-zero
elements and 11 zero elements. Above matrix occupies 4x4 = 16 memory space.
Increasing the size of matrix will increase the wastage space.

The linked list representation of the above matrix is given below -

In the above figure, the sparse matrix is represented in the linked list form. In the
node, the first field represents the index of the row, the second field represents the
index of the column, the third field represents the value, and the fourth field contains
the address of the next node.
 44

3.Dynamic memory management:

Dynamic memory management scheme is based on these principles:
• • Allocation schemes
• Deallocation schemes

Allocation schemes: how request for a node will be serviced:

• Fixed block allocation

• Variable block allocation

Deallocation schemes: how to return a node to memory bank whenever it is no more

required.

• Random deallocation
• Ordered deallocation

Uses of Linked List in Real World

Linked lists find numerous real-world applications due to their dynamic nature and
efficiency in certain scenarios. Let's explore some of these practical uses:

o Memory management: Operating systems and programming language runtimes

often utilize linked lists for dynamic memory allocation and deallocation. When you
request memory, a new node is added to the linked list, and when you free memory,
that node is removed.
o Browser history and cache: Modern web browsers use linked lists to keep track of
visited URLs and cache recently visited pages for faster loading. Each visited page is
added as a new node, and the cache management algorithm decides which nodes to
keep or remove based on factors like frequency and recency of access.
o Music playlists: Streaming services and media players represent playlists as linked
lists. Each song is a node, and the order of nodes defines the playback sequence.
Adding, removing, or rearranging songs is efficient with linked lists.
o Undo/Redo operations: Similar to stacks, linked lists can be used to implement
undo/redo functionality in text editors and other applications. Each editing operation
is stored as a node, allowing users to traverse the list in either direction to undo or
redo changes.
o Routing algorithms: Linked lists are used in routing algorithms for computer
networks and transportation systems. Each node represents a network node or a
location, and the links between nodes represent the connections or routes.
o Online multiplayer games: In real-time multiplayer games, linked lists are often
used to manage the active player list. When a new player joins, a node is added to
the list, and when a player leaves, their node is removed.
 45

o Blockchain technology: The blockchain, which underpins cryptocurrencies like

Bitcoin, is essentially a linked list. Each block (node) contains transaction data and is
linked to the previous block, forming an immutable chain of records.
o Image viewer applications: Image viewer applications may use linked lists to store
and navigate through a collection of images. Each node represents an image, and
users can move forward or backward through the list.
o Polynomial representation: In computer algebra systems, polynomials can be
efficiently represented using linked lists, where each node stores the coefficient and
exponent of a term.
o Implementing other data structures: Linked lists can be used as building blocks for
more complex data structures like stacks, queues, and hash tables, which are widely
used in various applications.

<<<<<<<<<<<<<<<<<<<UNIT-2 LINKED LIST>>>>>>>>