SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Experiment: 5
PART A
(PART A: TO BE REFERRED BY STUDENTS)
Aim . Implementation of Singly Linked list structure operations using CPP
Pre-reading: Concept and operations of Linked list from class/study material.
Pre-requisite :
1. Basic knowledge of Programming with classes and objects in CPP.
2. Knowledge of pointers and dynamic memory allocation.
3. Familiarity with data structures and algorithms.
Learning Outcomes: The learner would be able to
1. Ability to implement a singly linked list in C++.
2. Proficiency in performing insertion, deletion, and traversal operations on a
singly linked list.
3. Understanding of the practical applications of linked lists in computer science.
Theory:
A singly linked list is a linear data structure where each element, called a node, points
to the next node in the sequence. It consists of a series of nodes, each containing data
and a pointer to the next node.
1. Node Structure
A node is the fundamental building block of a linked list. In C++, it can be defined
using a struct or a class. Each node contains:
● Data: The value stored in the node.
● Next Pointer: A pointer to the next node in the list.
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
2. Dynamic Memory Allocation
Linked lists use dynamic memory allocation to create nodes at runtime. This allows
the list to grow and shrink as needed. In C++, the new keyword is used to allocate
memory for a new node.
3. Insertion Operations
Insertion operations add new nodes to the list. Common insertion operations include:
● At the Beginning: Adding a new node at the start of the list.
● At the End: Adding a new node at the end of the list.
● At a Specific Position: Adding a new node at a specified position in the list.
● Before a given node : Adding a new node before a given node value.
● After a given node : Adding a new node after a given node value.
4. Deletion Operations
Deletion operations remove nodes from the list. Common deletion operations include:
● From the Beginning: Removing the first node of the list.
● From the End: Removing the last node of the list.
● From a Specific Position: Removing a node from a specified position in the
list.
5. Traversal
Traversal involves visiting each node in the list to perform operations such as
displaying the data. This is typically done using a loop that starts at the head of the list
and follows the next pointers until the end of the list is reached.
6. Time Complexity
Understanding the time complexity of linked list operations is crucial for analyzing
their efficiency. For example:
● Insertion at the Beginning: O(1)
● Insertion at the End: O(n) (if no tail pointer is used)
● Deletion from the Beginning: O(1)
● Deletion from the End: O(n) (if no tail pointer is used)
● Traversal: O(n)
Algorithms:
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
1. Algorithm for traversing a linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXIT
2. Algorithms to insert a new node at the beginning
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE->NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT
3. Algorithms to insert a new node at the end of the list
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL-> NEXT
Step 4: SET NEWNODE->DATA = VAL
Step 5: SET NEW_NODE-> NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR-> NEXT != NULL
Step 8: SET PTR = PTR->NEXT
[END OF LOOP]
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXIT
4. Algorithm to insert a new node after a node that has value NUM
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Step 3: SET AVAIL = AVAIL-> NEXT
Step 4: SET NEW_NODE->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps a and b while PREPTR->DATA != NUM
a. SET PREPTR = PTR
b. SET PTR = PTR-> NEXT
[END OF LOOP]
Step 8 : PREPTR-> NEXT = NEWNODE
Step 9: SET NEW_NODE-> NEXT = PTR
Step 10: EXIT
5. Algorithm to insert a new node before a node that has value NUM
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL-> NEXT
Step 4: SET NEW_NODE->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps a and b while PTR->DATA != NUM
a. SET PREPTR = PTR
b. SET PTR = PTR-> NEXT
[END OF LOOP]
Step 8 : PREPTR-> NEXT = NEWNODE
Step 9: SET NEW_NODE-> NEXT = PTR
Step 10: EXIT
6. Algorithm to delete the first node from a linked list.
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START-> NEXT
Step 4: FREE PTR
Step 5: EXIT
7. Algorithm to delete the last node
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR-> NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR-> NEXT
[END OF LOOP]
Step 6: SET PREPTR-> NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
8. Algorithm to delete the node after a given node.
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 10
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR-> DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR-> NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR-> NEXT = PTR->NEXT
Step 9: FREE TEMP
Step 10 : EXIT
Tasks: Implement a menu driven program to various algorithms, given above, for
insertion and deletion operation on Singly Linked List.
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
PART B
(PART B: TO BE COMPLETED BY STUDENTS)
Students must implement the code in Laboratory. The soft copy must be uploaded on the
portal. The filename should be DSA_batch_rollno_experimentno Example:
DSA_A1_A001_P1
Roll No.: J065 Name: Manthan Singh
Prog/Yr/Sem: BTech DS / 2 / Sem 3 Batch: J2
Date of Experiment: 28 Aug 2025 Date of Submission: 28 Aug 2025
Code :
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = NULL;
void traverse() {
if (head == NULL) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
cout << "Linked List: ";
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
void insertAtBeginning(int val) {
Node* newNode = new Node();
newNode->data = val;
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
newNode->next = head;
head = newNode;
}
void insertAtEnd(int val) {
Node* newNode = new Node();
newNode->data = val;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
void insertAfterValue(int num, int val) {
Node* temp = head;
while (temp != NULL && temp->data != num) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Value " << num << " not found!\n";
return;
}
Node* newNode = new Node();
newNode->data = val;
newNode->next = temp->next;
temp->next = newNode;
}
void insertBeforeValue(int num, int val) {
if (head == NULL) {
cout << "List is empty!\n";
return;
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
}
if (head->data == num) { // before head
insertAtBeginning(val);
return;
}
Node* temp = head;
Node* prev = NULL;
while (temp != NULL && temp->data != num) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
cout << "Value " << num << " not found!\n";
return;
}
Node* newNode = new Node();
newNode->data = val;
newNode->next = temp;
prev->next = newNode;
}
void deleteFromBeginning() {
if (head == NULL) {
cout << "List Underflow!\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
void deleteFromEnd() {
if (head == NULL) {
cout << "List Underflow!\n";
return;
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
}
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* temp = head;
Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
delete temp;
}
void deleteAfterValue(int num) {
if (head == NULL) {
cout << "List Underflow!\n";
return;
}
Node* temp = head;
while (temp != NULL && temp->data != num) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
cout << "No node exists after " << num << "!\n";
return;
}
Node* delNode = temp->next;
temp->next = delNode->next;
delete delNode;
}
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
int main() {
int choice, val, num;
while (true) {
cout << "\n--- Singly Linked List Menu ---\n";
cout << "1. Traverse\n";
cout << "2. Insert at Beginning\n";
cout << "3. Insert at End\n";
cout << "4. Insert After Value\n";
cout << "5. Insert Before Value\n";
cout << "6. Delete from Beginning\n";
cout << "7. Delete from End\n";
cout << "8. Delete After Value\n";
cout << "9. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
traverse();
break;
case 2:
cout << "Enter value: ";
cin >> val;
insertAtBeginning(val);
break;
case 3:
cout << "Enter value: ";
cin >> val;
insertAtEnd(val);
break;
case 4:
cout << "Enter existing value after which to
insert: ";
cin >> num;
cout << "Enter new value: ";
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
cin >> val;
insertAfterValue(num, val);
break;
case 5:
cout << "Enter existing value before which to
insert: ";
cin >> num;
cout << "Enter new value: ";
cin >> val;
insertBeforeValue(num, val);
break;
case 6:
deleteFromBeginning();
break;
case 7:
deleteFromEnd();
break;
case 8:
cout << "Enter value after which to delete node:
";
cin >> num;
deleteAfterValue(num);
break;
case 9:
cout << "Exiting.\n";
return 0;
default:
cout << "Invalid choice!\n";
}
}
return 0;
}
Output :
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 1
List is empty!
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 2
Enter value: 19
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 3
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Enter value: 20
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 4
Enter existing value after which to insert: 19
Enter new value: 21
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 5
Enter existing value before which to insert: 20
Enter new value: 22
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 6
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 7
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 1
Linked List: 21 -> 22 -> NULL
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 8
Enter value after which to delete node: 22
No node exists after 22!
Singly Linked List Menu
1. Traverse
2. Insert at Beginning
3. Insert at End
4. Insert After Value
5. Insert Before Value
6. Delete from Beginning
7. Delete from End
8. Delete After Value
9. Exit
Enter your choice: 9
Exiting.
=== Code Execution Successful ===
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
Questions of Curiosity:
● Write a function to insert a node at a specific position in a singly linked list.
void insertAt(Node*& head, int pos, int val) {
Node* newNode = new Node{val, NULL};
if (pos == 0) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 0; temp && i < pos - 1; i++) temp = temp->next;
if (!temp) return;
newNode->next = temp->next;
temp->next = newNode;
}
● Write a function to delete a node at a specific position in a singly linked list.
void deleteAt(Node*& head, int pos) {
if (!head) return;
if (pos == 0) {
Node* t = head;
head = head->next;
delete t;
return;
}
Node* temp = head;
for (int i = 0; temp->next && i < pos - 1; i++) temp =
temp->next;
if (!temp->next) return;
Node* del = temp->next;
temp->next = del->next;
delete del;
}
SVKM’s NMIMS
Mukesh Patel School of Technology Management & Engineering /
School of Technology Management & Engineering
MBA Tech/ B. Tech CE Lab Manual Academic Year- 2025-26
Year:-Second Subject:- Data Structures and Algorithms Semester: - Third
● Write a function to reverse a singly linked list.
void reverseList(Node*& head) {
Node *prev = NULL, *curr = head, *next = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
● Write a function to remove duplicate elements from a sorted singly linked list.
void removeDuplicates(Node*& head) {
Node* temp = head;
while (temp && temp->next) {
if (temp->data == temp->next->data) {
Node* dup = temp->next;
temp->next = dup->next;
delete dup;
} else temp = temp->next;
}
}
