https://shikshamentor.

com/data-structure-
using-c-for-msbte-3k-scheme/

313301 – Data Structure (Sem III)

As per MSBTE’s K Scheme
CO / CM / IF

Unit III Linked List Marks - 16

Exam
S. N. MSBTE Board Asked Questions Marks
Year
1 Define linked list with example S -24 02
A linked list, or one-way list is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers.
Each node is divided into two pacts :
1. First part contains information of the element.
2. Second part contains address of the next node is the list, which is called as linked
field or next pointer field.
Information Next

Node structure

 Example : Suppose we want to maintain the node containing name of student and
call number. Here two data field of different types are required. Hence, we need to
use a structure. The next field is a pointer to another node of same type so node
definition will be,
Ans.
Struct node
{
Char name [15] :
int rollno ;
sturct node * next;
};
The statement :
Struct node * next ;
Means next is a pointer to the next structure node. And it can be represented as :

Name Roll No. Next

Data Link

2 Explain the concept of information, next, null pointer S -24 04

 and empty list with respect to linked list

A linked list, or one-way list is a linear collection of data elements, called nodes,
where the linear order is given by means of pointers

Information and next –

Each node is divided into two pacts :
1. First part contains information of the element.
2. Second part contains address of the next node is the list, which is called as linked
field or next pointer field.
Information Next

Node structure

 Example : Suppose we want to maintain the node containing name of student and
call number. Here two data field of different types are required. Hence, we need to
use a structure. The next field is a pointer to another node of same type so node
definition will be,
Struct node
{
Char name [15] :
int rollno ;
sturct node * next;

Ans };
The statement :
Struct node * next ;
Means next is a pointer to the next structure node. And it can be represented as :

Name Roll No. Next

Info / Data Link

Null Pointer : The pointer of the last node contains a special value, called the null
pointer, which is any invalid address. The null pointer, denoted by X in the diagram,
signals the end of list.
Empty List : The linked list also contains a list pointer variable – called START or
NAME – which contains the address of the first node in the list : hence there is an
arrow drawn from the START to the first node. We need only this address is START
to trace through the list. A special case is the list that has no nodes, such a list
called as empty list or null list and is denoted by the null pointer in the variable
START.
 Write an algorithm to insert a new node at the beginning in S - 24
3 04
linear list W - 22
Algorithm : Inserting an element at the beginning :
Suppose the original Linked list as shown in Fig

(a) Original list

Insert – first node

3 nodes are present is the given list. Now insert a new node with data 5, in the
beginning of the list :
Step 1 : Create a space for new node and P will point to this empty node.
Step 2 : Read information and to be inserted at P and store it at p
Put the value 5 in INFO field of new node.

Create a new empty node

INTO (D) = 5

Step 3 : Check whether this is the first element (i.e. START = NULL) if so then
point ‘START’ to ‘P’ (START = P)
Else
Ans
New connect ‘P’ in front of the list, so its next field should point to the beginning of
liset (P  Next = LIST)

P  Next = START

 Now the address filed or next pointer of ‘P’ is pointing to start, where START
pointing is stored in ‘P’ next field. This establishes a desired link between a new
node ‘P’ and the LIST.
 Now LIST will have 4 elements. The last step is change starting address of list (i.e.
START = P)
 4 S -24
Explain the operation on a singly linked list 04
W – 23
A linked list, or one-way list is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers.

The various operations that can be performed on the linked list are given below :

a. Traversing the list :

Visiting each node of the list is called traversing.

b. Insertion :

Adding new node in the list.

A node can be inserted at the beginning end or in between two nodes of the list.
c. Deletion :
Removing a node from the list may be done positionwise or element wise.
d. Searching :
Searching a location of a particular node is the list.
Algorithms for performing the operations on singly linked list :
Step 1 : Initialize the variable, START to point to NULL.
Step 2 : Depending on user choice (Add, delete, display, Exit) perform step 3, step 4
and step 5 respectively.
Step 3 : Call “Add ( )” to add new elements in the list, goto step 6.
Ans - Step 4 : Call “Delete ( )” to delete an element from the list, goto step 6.
Step 5 : Call “Display ( )” to print all the elements. goto step 6.
Step 6 : If you wish to perform any operation goto step 2.
Step 7 : Stop.

Add ( ) function :

Step 1 : Create new space for the node as “P”.

Step 2 : Read the information to be inserted in the new node “P” and store it in the into
at P.
Step 3 : Check whether this is the first element (i.e. START = NULL) if so then point
‘START’ to ‘P’ (START = P)
If already some elements are present. Then, travel along the list till you reach
end of the list and here attach the node ‘P’.
[q = START, while (q  next ! = NULL)]
q = q  next
q  next = P
Step 4 : Return.

Delete ( ) function :

Step 1 : Read the information which you wish to delete, say x.

Step 2 : Go on checking information field of each node, whether it matches x. if no such
match is found then print.
“Such information not present” and goto step 5. Else call this node as ‘a’.
Step 3 : If the node found is the first node (i.e. q  START), then simply move START
one position ahead and remove q.
[i.e. START = START  Next ;
q  Next = NULL ;
free (q) ;]
Else with the help of another pointer say ‘r’, point to the previous node of ‘q’.
i.e.
[r = START
while (r  Next ! = q) r = r  next]
(Note that, we want to connect previous of ‘q’ to the next node of q and by ‘r’ we
are identifying its previous node.)
Connect next field of ‘r’ to a next node to q and remove q.
[r  Next = q  Next ;
q  Next = NULL ;
free (q) ;]
Step 4 : Return.

Display ( )

Step 1 : If list is not empty, visit each node display the information.
[i.e. it (START ! = NULL)
{
q = START ;
while (q ! = NULL)
{
print (“% d”, q  into) ;
q = q  Next ;
}
}
Step 2 : Return.
 S -24
5 Compare linear list with circular list (Any four points) 04
W – 22
Sr.
Linear linked list Circular linked list
No
A linear linked list, or one-way
list is a linear collection of data A circular linked list is a list in which
elements, called nodes, where the last node pointer to the first
1 the linear order is given by node in a list.
means of pointers.

Each node is divided into two

Each node is divided into thwo parts :
parts :
1. First part contains information of
1. First part contains information
the element.
of the element.
2. Second part contains address of the
2 2. Second part contains address
next node is the list, which is called
of the next node is the list,
as linked field or next pointer field.
which is called as linked field
Ans or next pointer field.
Information Next Last node points to first node

3 It is linear in nature It is circular in nature

Linear Linked list

Circular Linked list

7 Define term pointer and null pointer S -23 02

 Pointer :
A pointer is defined as a derived data type that can store the address of other C
variables or a memory location. We can access and manipulate the data stored in
that memory location using pointers.
datatype * ptr;
Ans where
ptr is the name of the pointer.
datatype is the type of data it is pointing to.
 Null Pointer
The Null Pointer is the pointer that does not point to any location but NULL.
type pointer_name = NULL;
 Write algorithm to delete an intermediate node from a singly S -23
8 04
linked list W-23
 Traverse the list till the position of node to be deleted say P. Change the next field
of node one before P which will point to next of P.
 Free P.

P is node to be deleted

Temp  next = P  Next

Free (P)

Ans

Free (P)

After deleting the linked list

Step 1 : Read the information which you wish to delete, say x.

Step 2 : Go on checking information field of each node, whether it matches x. if no such
match is found then print.
“Such information not present” and goto step 5. Else call this node as ‘a’.
Step 3 : If the node found is the first node (i.e. q  START), then simply move START
one position ahead and remove q.
[i.e. START = START  Next ;
q  Next = NULL ;
free (q) ;]
Else with the help of another pointer say ‘r’, point to the previous node of ‘q’.
i.e.
[r = START
while (r  Next ! = q) r = r  next]
(Note that, we want to connect previous of ‘q’ to the next node of q and by ‘r’ we
are identifying its previous node.)
Connect next field of ‘r’ to a next node to q and remove q.
[r  Next = q  Next ;
q  Next = NULL ;
free (q) ;]
Step 4 : Return.
 S – 24
9 Explain the operation on a singly linked list 04
W – 23
Operations on Singly Linked List
 Traversal : Traversal involves visiting each node in the linked list
-

and performing some operation on the data. A simple traversal

function would print or process the data of each node.
 Searching : Searching in a Singly Linked List refers to the process of looking
for a specific element or value within the elements of the linked list.
Step-by-step approach:
1. Traverse the Linked List starting from the head.
2. Check if the current node's data matches the target value.
 If a match is found, return true.
3. Otherwise, Move to the next node and repeat steps 2.
4. If the end of the list is reached without finding a match, return false.

 Length : Finding Length in Singly Linked List refers to the

process of determining the total number of nodes in a singly
linked list.
Ans Step-by-step approach:
 Initialize a counter length to 0.
 Start from the head of the list, assign it to current.
 Traverse the list:
o Increment length for each node.
o Move to the next node (current = current->next).
 Return the final value of length.

 Insertion:

 Insert at the beginning : Create a new node with the

given value.
 Set the next pointer of the new node to the

current head.
 Move the head to point to the new node.

 Return the new head of the linked list.

 o Insert at the end :
 Create a new node with the given value.
 Check if the list is empty:
o If it is, make the new node the head and return.
 Traverse the list until the last node is reached.
 Link the new node to the current last node by setting the last
node's next pointer to the new node.

o Insert at a specific position : To insert a node at a

specific position, traverse the list to the desired position, link
the new node to the next node, and update the links
accordingly.

 Deletion:
 Delete from the beginning :
 Check if the head is NULL.
o If it is, return NULL (the list is empty).
 Store the current head node in a temporary variable temp.
 Move the head pointer to the next node.
 Delete the temporary node.
 Return the new head of the linked list.
o Delete from the end :
 Check if the head is NULL.
o If it is, return NULL (the list is empty).
 Check if the head's next is NULL (only one node in the
list).
o If true, delete the head and return NULL.
 Traverse the list to find the second last node
(second_last).
 Delete the last node (the node after second_last).
 Set the next pointer of the second last node to NULL.
 Return the head of the linked list.

o Delete a specific node

 Check if the list is empty or the position is invalid, return if so.
 If the head needs to be deleted, update the head and delete the
node.
 Traverse to the node before the position to be deleted.
 If the position is out of range, return.
 Store the node to be deleted.
 Update the links to bypass the node.
 Delete the stored node.
 Describe circular linked list with suitable diagram. State S – 22
10 04
advantages of circular linked list over linear linked list W - 18
 A circular linked list is a list in which the last node pointer to the first node in a list.
Circular Linked List is a type of linked list that is circular in nature. In a circular
linked list, every node has successor. In this data structure, every node points to
the next node and the last node of the linked list points to the first node. This
feature makes it circular in nature.

 Type of circular linked list :

a. Singly circular linked list

Corel 3

b. Doubly circular linked list

Corel 4

 Advantages of Circular Linked Lists over linear linked list:

Ans.  Efficient operations: Since the last node of the circular list points back to
the first node, circular linked lists can be traversed quickly and efficiently. This
makes them useful for applications that require frequent traversal, such as
queue and hash table implementations. Where as in linear linked list
sequential traversing of linear traversing is done. To visit last node all nodes
must be visited.
 Space efficiency: Circular linked lists can be more space-efficient than linear
linked lists because they do not require a separate pointer to keep track of the
end of the list. This means that circular linked lists can be more compact and
take up less memory than linear linked list.
 Flexibility: The circular structure of the list allows for greater flexibility in
certain applications. For example, a circular linked list can be used to
represent a ring or circular buffer, where new elements can be added and old
elements can be removed without having to shift the entire list. Whereas in
linear linked list node can be inserted at the end , in between and beginning.
 Dynamic size: Circular linked lists can be dynamically sized, which means
that nodes can be added or removed from the list as needed. This makes
them useful for applications where the size of the list may change frequently,
such as memory allocation and music or media players.
 Ease of implementation: Implementing circular linked lists is often simpler
than implementing linear linked list. This is because circular linked lists have a
simple, circular structure that is easy to understand and implement.
 11 Write an algorithm to count no. of nodes in singly linked list. W – 23 04
Algorithm to count number of nodes in Singly Linked List

Input: LinkedList = 1->3->1->2->1

Output: 5

 Step 1 : Initialize count as 0.

Ans.  Step 2 : Initialize a node pointer, curr = head.
 Step 3 : Do following while curr is not NULL
curr = curr -> next
Increment count by 1.
 Step 4 : Return count.

Write an algorithm to delete a node at the beginning from a

12 S – 23 04
singly linked list.

Algorithm to delete a node at the beginning from a singly linked list.

Input : head : 3 -> 12 -> 15 -> 18 -> NULL

Output : 12 -> 15 -> 18 -> NULL

To remove the first node of a linked list, store the current head in a temporary
variable (temp), move the head pointer to the next node, delete the temporary head
node and finally , return the new head of the linked list.

 Step 1 : Check if the list is empty
 if (head == NULL)
 return NULL;.
 Step 2 : Store the current head in a temporary variable
Ans  struct Node* temp = head
 Step 3 : Move the head pointer to the next node
head = head->next
 Step 4 : free (temp);
 Step 5 : Return.
 Create a singly Linked list using data fields 10,20,30,40,50 and
S – 23
13 show procedure step by step with help of diagram from start to 04
W – 23
end
 Initially liked list will be empty
Start = NULL ;
Insert node 10
Node 10 will be first node.
Start Null
10

 Insert node 20.

Start
10 20 Null

 Insert node 30.

Start Null
10 20 30

Ans.  Insert node 40

Null
Start 10 20 30 40
/Head

 Insert node 50

 Singly Linked list using data fields 10, 20, 30, 40, 50

Start 10 20 30 40 50
/Head

Create a singly Linked list using data fields 10,20,30,40,50.

14 Search a node 40 from the singly linked list and show S – 23 06
procedure step by step with help of diagram from start to end
 Singly Linked list using data fields 10, 20, 30, 40, 50
Ans
Start 10 20 30 40 50
/Head

Now search node 40. Key = 40.

Step 1 : Initially pointer Q = start
Pos = 1
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 1

Q ->data ! = Key (10 != 40)
Therefore , Q = Q-> Next
pos = pos+1

Step 2 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 2

Q ->data ! = Key (20 != 40)
Therefore , Q = Q-> Next
pos = pos+1
Step 3 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 3

Q ->data ! = Key (30 != 40)
Therefore , Q = Q-> Next
pos = pos+1

Step 4 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 4

Q ->data == Key (40 == 40)
 Therefore , the element to be found is 40 and found at location 4.
Explain node structure for single linked list. Also write
15 W – 22 04
advantages of singly list over array.

Node structure for single linked list

A linked list, or one-way list is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers.
Each node is divided into two pacts :
1. First part contains information of the element.
2. Second part contains address of the next node is the list, which is called as linked
field or next pointer field.
Information Next

: Node structure

 Example : Suppose we want to maintain the node containing name of student and
call number. Here two data field of different types are required. Hence, we need to
use a structure. The next field is a pointer to another node of same type so node
definition will be,
Struct node
{
Ans Char name [15] :
int rollno ;
sturct node * next;
};
The statement :
Struct node * next ;
Means next is a pointer to the next structure node. And it can be represented as :

Name Roll No. Next

Info / Data Link

Advantages of singly list over array.

Array: Arrays store elements in contiguous memory locations, resulting in easily

calculable addresses for the elements stored and this allows faster access to an element
at a specific index.
 Data storage scheme of an array

Linked List: Linked lists are less rigid in their storage structure and elements are usually
not stored in contiguous locations, hence they need to be stored with additional
tags giving a reference to the next element.

Advantages of Linked List over arrays :

 Easy and Efficient insertion and deletion. : By changing few pointers (or
references) to insert (or delete) an item in the middle
 Implementation of Queue and Deque is easy and straightforward Space
Efficient in Some Cases : Linked List might turn out to be more space efficient
compare to arrays in cases where we cannot guess the number of elements in
advance. In case of arrays, the whole memory for items is allocated
togetherCircular List with Deletion/Addition : Circular Linked Lists are useful to
implement CPU round robin scheduling or similar requirements in the real world
because of the quick deletion/insertion in a circular manner.

 Write the ‘C’ function for counting number of nodes in W – 22 03
16 single linked list. S – 19 06

Algorithm to count number of nodes in Singly Linked List

Input : head node of the linked list

Ans
Begin:

count ← 0
 If (head != NULL) then

temp ← head

While (temp != NULL) do

count ← count + 1

temp ← temp.next

End while

End if

write ('Total nodes in list =' + count)

End

‘C’ function for counting number of nodes in single

linked list.

int count(struct Node *p){

int count = 0;
while(p! = 0)
{
count++;
p = p -> next;
}
return (count);
}

W – 22 03
17 Write the ‘C’ function for searching a node in single linked list

bool searchLL(struct Node* head, int target)

{
// Traverse the Linked List
Ans. while (head != NULL) {

// Check if the current node's data matches the target value

 if (head->data == target) {
return true; // Value found
}

// Move to the next node

head = head->next;
}

return false; // Value not found

}
Write an algorithm to search an element in linked list.
Write an algorithm to search a particular node in the given S – 22
18 06
linked list. W–9

Step 1 : START
Step 2 : Accept linked list & data
Step 3 : Set Temp := Start
Step 4 : While link [Temp] not equal to Null [Check till end]
If Info [Temp] = data, then
Write: “Found Successfully"
EXIT [If found, Stop]
Ans.
[End of If]
Set Temp := Link [Temp] [Pointer is
incremented to next]
[End of while]
Step 5 : Write: "Not Found"
Step 6 : EXIT [stop]

Write an algorithm to count number of nodes in singly linked

W – 18 04
19 list.
S – 19 06
Algorithm to count number of nodes in Singly Linked List

Input: Linked List = 1->3->1->2->1

Output: 5

Ans.  Step 1 : Initialize count as 0.

 Step 2 : Initialize a node pointer, curr = head.
 Step 3 : Do following while curr is not NULL
curr = curr -> next
Increment count by 1.
 Step 4 : Return count.
20 Write an algorithm to traverse a linked list. S – 22 04

Traversing the linked list :

Visiting each node of the list is called traversing.

Algorithm to traverse a linked list.
The process of traversing a singly linked list involves printing the value of
each node and then going on to the next node and print that node's value also
and so on, till we reach the last node in the singly linked list, whose next node
points towards the null.
Step-by-Step Algorithm
 Step 1 : Initialize a temporary pointer to the head node of the linked list.
 Q = Head
 Step 2 : Check if Q pointer is null or not null,
 if it is null, then return.
Ans. Step 3 : While the pointer is not null, access and print the data of the current
node,
 then we move the pointer to next node.
 While ( Q != NULL)
 Print Q-> data
 Q = Q-> next
 Step 4 : STop

Input: 10->20->30->40->50->null
Output: 10 20 30 40 50
Explanation: Every element of each node from head node to last node is
printed which means we have traversed each node successfully.

W – 19 04
Write an algorithm to insert a new node at the beginning and
21 W – 18 06
end of the singly linked list.
S - 22 04
Algorithm to insert a new node at the beginning and end of the singly linked
list.

Step 1 : Create new space for the node as “P”.

Step 2 : Read the information to be inserted in the new node “P” and store it in the into
at P.
Ans Step 3 : Check whether this is the first element (i.e. START = NULL) if so then point
‘START’ to ‘P’ (START = P)
If already some elements are present. Then, travel along the list till you reach
end of the list and here attach the node ‘P’.
[q = START, while (q  next ! = NULL)]
q = q  next
q  next = P
 Step 4 : Return.

Construct a singly linked list using data fields 21, 25, 96, 58,
22 74 and show procedure step-by-step with the help of diagram W – 19 04
start to end.
 Singly Linked list using data fields 21, 25, 96, 58, 74
 Initially liked list will be empty
Start = NULL ;
Insert node 21
Node 21 will be first node.
Start Null
21

 Insert node 25. (Create node )

Create newnode 25
Start-> next = newnode

Start
21 25 Null

 Insert node 96. (Create node )

Create newnode 96
Traverse till Temp != NULL
Temp-> next = newnode
Ans

Start Null
21 25 96

 Insert node 58 (Create node )

Create newnode 58
Traverse till Temp != NULL
Temp-> next = newnode


Null
Start 21 25 96 58
/Head

 Insert node 74 (Create node )

Create newnode 74
Traverse till Temp != NULL
Temp-> next = newnode
  Singly Linked list using data fields 21, 25, 96, 58, 74

Start 21 25 96 58 74
/Head

23 Compare Linked List and Array. (any 4 points) W – 19 04

Sr. Linked List Array

A linked list, or one-way list is
a linear collection of data
elements, called nodes, where Arrays store elements in contiguous
1
the linear order is given by memory locations
means of pointers.

Arrays are static data structure in

2 Linked list is dynamic data structure. nature, it cannot be increased as
additional space is required.
it is relatively expensive to insert
delete element in an array. Insertion,
Insertion the elements in the list deletion at the end is very easy. But in
3 becomes more easier as compared order to insert an element is between
to array. is very tedious, as remaining elements
need to be shifted one by one
position.
Ans Deletion the elements in the list for the deletion, the elements have to
4 becomes more easier as compared be shifted one position before. This
to array. requires more processing time.
Data is stored in continues manner in
Pointers are used to point next Array. Indices are used to point the
5
element in the list location of any data in array . Array
starts from 0th location

Linked list
 Array

Show with suitable diagrams how to delete a node from singly

24 linked list at the beginning, in between and at the end of the W – 19 06
list.
Step 1 : Read the information which you wish to delete, say x.
Step 2 : Go on checking information field of each node, whether it matches x. if no such
match is found then print.
“Such information not present” and goto step 5. Else call this node as ‘a’.
Step 3 : If the node found is the first node (i.e. q  START), then simply move START
one position ahead and remove q.
[i.e. START = START  Next ;
q  Next = NULL ;
free (q) ;]
Else with the help of another pointer say ‘r’, point to the previous node of ‘q’.
i.e.
[r = START
while (r  Next ! = q) r = r  next]
Ans (Note that, we want to connect previous of ‘q’ to the next node of q and by ‘r’ we
are identifying its previous node.)
Connect next field of ‘r’ to a next node to q and remove q.
[r  Next = q  Next ;
q  Next = NULL ;
free (q) ;]
Step 4 : Return.

1. Deletion of a node at beginning

1. To delete the first node of a linked list, store the current head in a temporary variable
(temp),
2. move the head pointer to the next node,
3. delete the temporary head node and finally ,
4. return the new head of the linked list.
 2. Deletion of a node at End
 Check if list is empty then return NULL.
 If the list has only one node then delete it and return NULL.
 Traverse the list to find the second last node.
o Set the next pointer of second last node to NULL.

3. Deletion of a node in between

1. Traverse the list till the element to be deleted
2. Store previous and next node of the element to be deleted
3. Assign the pointer of previous node to the node pointed
by deleted node
4. Free the element to be deleted
25 Write a program to traverse a linked list. W – 19 04
#include <stdio.h>
#include <stdlib.h>

// A linked list node

struct Node
{
int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int new_data)
{
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

Ans // Function to traverse and print the singly linked list

void traverseList(struct Node* head)
{

// Loop that runs until head is NULL

while (head != NULL) {

// Printing data of current node

printf("%d ", head->data);

// Moving to the next node

head = head->next;
}
printf("\n");
}

int main() {

// Create a hard-coded linked list:

// 10 -> 20 -> 30 -> 40
struct Node* head = createNode(10);
 head->next = createNode(20);
head->next->next = createNode(30);
head->next->next->next = createNode(40);

// Call function for traversing the node and printing

traverseList(head);

return 0;
}
Create a singly linked list using data fields 15, 20, 22, 58, 60.
W – 19 04
26 Search a node 22 from the SLL and show procedure step-by-
S – 24 06
step with the help of diagram from start to end.

 Singly Linked list using data fields 15, 20, 22, 58, 60

Start 15 20 22 58 60
/Head

Now search node 22. Key = 22.

Step 1 : Initially pointer Q = start
Pos = 1
Start 15 20 22 58 60
/Head

Q ! = NULL && pos = 1

Q ->data ! = Key (15 != 22)
Ans
Therefore , Q = Q-> Next
pos = pos+1

Step 2 :
Start 15 20 22 58 60
/Head

Q ! = NULL && pos = 2

Q ->data ! = Key (20 != 22)
Therefore , Q = Q-> Next
pos = pos+1
Step 3 :
Start 15 20 22 58 60
/Head
 Q

Q ! = NULL && pos = 3

Q ->data = = Key (22 == 22)

Therefore , the element to be found is 22 and found at location 3.

Write an algorithm to delete a node from the beginning of a

27 S – 19 04
circular linked list.

To delete the first node of a circular linked list, we first check if the list is
empty. If it is then we print a message and return NULL. If the list
contains only one node (the head is the same as the last) then we delete
that node and set the last pointer to NULL. If there are multiple nodes
then we update the last->next pointer to skip the head node and
effectively removing it from the list. We then delete the head node to
free the allocated memory. Finally, we return the updated last pointer,
which still points to the last node in the list.

Algorithm
Step 1 : Check if List is Empty:
Ans If last is nullptr, print “List is empty” and return nullptr.
Else goto step 2
Step 2 : Get Head Node (Start)
Set Start = q
Start = start-> next
q->next = Null
last - > next = start
Step 3 Return q

Delete ( ) :

Corel 9

Move start to next node

Corel 10
 Move r to the last node and connect back to start.

Corel 11

Create a singly linked list using data fields 90, 25, 46, 39, 56.
28 Search a node 40 from the SLL and show procedure step-by- S – 19 06
step with the help of diagram from start to end.
 Singly Linked list using data fields 10, 20, 30, 40, 50

Start 10 20 30 40 50
/Head

Now search node 40. Key = 40.

Step 1 : Initially pointer Q = start
Pos = 1
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 1

Q ->data ! = Key (10 != 40)
Therefore , Q = Q-> Next
pos = pos+1
Ans
Step 2 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 2

Q ->data ! = Key (20 != 40)
Therefore , Q = Q-> Next
pos = pos+1
Step 3 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 3

Q ->data ! = Key (30 != 40)
Therefore , Q = Q-> Next
 pos = pos+1

Step 4 :
Start 10 20 30 40 50
/Head

Q ! = NULL && pos = 4

Q ->data == Key (40 == 40)

Therefore , the element to be found is 40 and found at location 4.

Describe procedure to delete an element from singly linked list
29 W – 18 06
using diagram.

Delete ( ) function :

Step 1 : Read the information which you wish to delete, say x.

Step 2 : Go on checking information field of each node, whether it matches x. if no
such match is found then print.
“Such information not present” and goto step 5. Else call this node as ‘a’.
Step 3 : If the node found is the first node (i.e. q  START), then simply move
START one position ahead and remove q.
[i.e. START = START  Next ;
q  Next = NULL ;
free (q) ;]
Else with the help of another pointer say ‘r’, point to the previous node of
‘q’.
i.e.
Ans
[r = START
while (r  Next ! = q) r = r  next]
(Note that, we want to connect previous of ‘q’ to the next node of q and by ‘r’
we are identifying its previous node.)
Connect next field of ‘r’ to a next node to q and remove q.
[r  Next = q  Next ;
q  Next = NULL ;
free (q) ;]
Step 4 : Return.

4. Deletion of a node at beginning

5. To delete the first node of a linked list, store the current head in a temporary variable
(temp),
6. move the head pointer to the next node,
7. delete the temporary head node and finally ,
 8. return the new head of the linked list.

5. Deletion of a node at End

 Check if list is empty then return NULL.
 If the list has only one node then delete it and return NULL.
 Traverse the list to find the second last node.
o Set the next pointer of second last node to NULL.

6. Deletion of a node in between

5. Traverse the list till the element to be deleted
6. Store previous and next node of the element to be deleted
7. Assign the pointer of previous node to the node pointed by deleted
node
8. Free the element to be deleted

Describe advantages of circular link list over linear link list with
30 W – 23 04
example
  Advantages of Circular Linked Lists over linear linked list:
 Efficient operations: Since the last node of the circular list points back to
the first node, circular linked lists can be traversed quickly and efficiently. This
makes them useful for applications that require frequent traversal, such as
queue and hash table implementations. Where as in linear linked list
sequential traversing of linear traversing is done. To visit last node all nodes
must be visited.
 Space efficiency: Circular linked lists can be more space-efficient than linear
linked lists because they do not require a separate pointer to keep track of the
end of the list. This means that circular linked lists can be more compact and
take up less memory than linear linked list.
 Flexibility: The circular structure of the list allows for greater flexibility in
Ans certain applications. For example, a circular linked list can be used to
represent a ring or circular buffer, where new elements can be added and old
elements can be removed without having to shift the entire list. Whereas in
linear linked list node can be inserted at the end , in between and beginning.
 Dynamic size: Circular linked lists can be dynamically sized, which means
that nodes can be added or removed from the list as needed. This makes
them useful for applications where the size of the list may change frequently,
such as memory allocation and music or media players.
 Ease of implementation: Implementing circular linked lists is often simpler
than implementing linear linked list. This is because circular linked lists have a
simple, circular structure that is easy to understand and implement.

Thank You
https://shikshamentor.com/data-structure-
using-c-for-msbte-3k-scheme/

Visit
https://shikshamentor.com/