Welcome to Day 10 of my 100 Days of DSA challenge! Today, I'll be tackling five problems focused on linked lists. Linked lists are an essential data structure that offers efficient insertions and deletions by dynamically allocating memory. They provide an excellent foundation for understanding more complex structures.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into today’s problems and explore the versatility of linked lists!
1. Implement a Singly Linked List
This program implements a singly linked list with various operations such as insertion, deletion, and traversal. It uses a Node structure to represent each element and a singly_linked_list class to manage the operations. Users can insert nodes at the beginning, end, before, or after a specific node. Deletion options include removing the first, last, or a specific node, as well as nodes relative to others. A menu-driven program with a switch statement provides an interactive interface for users to choose and perform these operations. The display function shows the current state of the linked list after every operation.
Code:
#include <iostream>
using namespace std;
// Define a Node structure
struct Node {
int data;
Node *next;
// Constructor to initialize a node
Node(int val) {
data = val;
next = nullptr;
}
};
// Singly Linked List class
class singly_linked_list {
private:
Node *start;
public:
// Constructor to initialize an empty list
singly_linked_list() {
start = nullptr;
}
// Function to insert a node at the beginning
void insert_at_beginning(int data) {
Node *newNode = new Node(data);
newNode->next = start;
start = newNode;
display();
}
// Function to insert at the end
void insert_at_end(int data) {
Node *newNode = new Node(data);
if (start == nullptr)
start = newNode;
else {
Node *temp = start;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
}
display();
}
// Function to insert after a particular element
void insert_after_element(int data1, int data2) {
Node *temp = start;
while (temp != nullptr && temp->data != data2)
temp = temp->next;
if (temp != nullptr) {
Node *newNode = new Node(data1);
newNode->next = temp->next;
temp->next = newNode;
}
else
cout << "Element " << data2 << " not found!" << endl;
display();
}
// Function to insert before a particular element
void insert_before_element(int data1, int data2) {
if (start == nullptr) {
cout << "List is empty!" << endl;
return;
}
if (start->data == data2) {
insert_at_beginning(data1);
return;
}
Node *temp = start;
while (temp->next != nullptr && temp->next->data != data2)
temp = temp->next;
if (temp->next != nullptr) {
Node *newNode = new Node(data1);
newNode->next = temp->next;
temp->next = newNode;
}
else
cout << "Element " << data2 << " not found!" << endl;
display();
}
// Function to delete at the beginning
void delete_at_beginning() {
if (start == nullptr) {
cout << "LinkedList is already empty!" << endl;
return;
}
Node *temp = start;
start = start->next;
delete temp;
display();
}
// Function to delete at the end
void delete_at_end() {
if (start == nullptr) {
cout << "LinkedList is already empty!" << endl;
return;
}
if (start->next == nullptr) {
delete start;
start = nullptr;
return;
}
Node *temp = start;
while (temp->next != nullptr && temp->next->next != nullptr)
temp = temp->next;
delete temp->next;
temp->next = nullptr;
display();
}
// Function to delete after a particular element
void delete_after_element(int data) {
Node *temp = start;
while (temp != nullptr && temp->data != data)
temp = temp->next;
if (temp != nullptr && temp->next != nullptr) {
Node *nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
}
else
cout << "Element " << data << " not found or no node after it!" << endl;
display();
}
// Function to delete before a particular element
void delete_before_element(int data) {
if (start == nullptr || start->next == nullptr) {
cout << "LinkedList is too short to delete before the element!" << endl;
return;
}
if (start->data == data) {
cout << "No element before " << data << " to delete!" << endl;
return;
}
Node *temp = start;
while (temp->next != nullptr && temp->next->data != data)
temp = temp->next;
if (temp->next != nullptr && temp->next->next != nullptr) {
Node *nodeToDelete = temp;
temp->next = temp->next->next;
delete nodeToDelete;
}
else
cout << "Element " << data << " not found!" << endl;
display();
}
// Function to delete a particular element
void delete_element(int data) {
if (start == nullptr) {
cout << "LinkedList is empty!" << endl;
return;
}
if (start->data == data) {
Node *temp = start;
start = start->next;
delete temp;
display();
return;
}
Node *temp = start;
while (temp->next != nullptr && temp->next->data != data)
temp = temp->next;
if (temp->next != nullptr) {
Node *nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
}
else
cout << "Element " << data << " not found!" << endl;
display();
}
// Function to display the linked list
void display() {
if (start == nullptr) {
cout << "LinkedList is empty!" << endl;
return;
}
Node *temp = start;
while (temp != nullptr) {
cout << " --> " << temp->data;
temp = temp->next;
}
cout << endl;
}
// Destructor to free memory
~singly_linked_list() {
while (start) {
Node *temp = start;
start = start->next;
delete temp;
}
}
};
int main() {
singly_linked_list list;
int choice, data, data1, data2;
do {
cout << "\n--- Singly Linked List Menu ---\n";
cout << "1. Insert a node\n";
cout << "2. Delete a node\n";
cout << "3. Display the list\n";
cout << "4. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Where would you like to insert:\n";
cout << "1. At the beginning\n";
cout << "2. At the end\n";
cout << "3. After an element\n";
cout << "4. Before an element\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the data: ";
cin >> data;
list.insert_at_beginning(data);
break;
case 2:
cout << "Enter the data: ";
cin >> data;
list.insert_at_end(data);
break;
case 3:
cout << "Enter the data of the node after which you want to insert your node: ";
cin >> data2;
cout << "Enter the data: ";
cin >> data1;
list.insert_after_element(data1, data2);
break;
case 4:
cout << "Enter the data of the node before which you want to insert your node: ";
cin >> data2;
cout << "Enter the data: ";
cin >> data1;
list.insert_before_element(data1, data2);
break;
default:
cout << "Invalid choice!" << endl;
break;
}
break;
case 2:
cout << "Which element would you like to delete:\n";
cout << "1. First\n";
cout << "2. Last\n";
cout << "3. After an element\n";
cout << "4. Before an element\n";
cout << "5. By data\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
list.delete_at_beginning();
break;
case 2:
list.delete_at_end();
break;
case 3:
cout << "Enter the element whose next element you want to delete: ";
cin >> data;
list.delete_after_element(data);
break;
case 4:
cout << "Enter the element whose previous element you want to delete: ";
cin >> data;
list.delete_before_element(data);
break;
case 5:
cout << "Enter the data of the node you want to delete: ";
cin >> data;
list.delete_element(data);
break;
default:
cout << "Invalid choice!" << endl;
break;
}
break;
case 3:
cout << "Linked List: ";
list.display();
break;
case 4:
cout << "Exiting program." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
break;
}
} while (choice != 4);
return 0;
}
Output:
2. Reverse a Linked List
The program implements a singly linked list with functionalities to insert nodes at the end, reverse the list, and display its elements. The Node structure holds the data and a pointer to the next node. The insert_at_end function adds a new node to the end of the list. The reverse_list function iteratively reverses the list by changing the next pointers of each node. The display_list function traverses and prints the list. A menu-driven interface allows the user to perform these operations interactively.
Code:
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
};
// Function to insert a new node at the end of the list
void insert_at_end(Node*& head, int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
}
// Function to reverse the linked list
void reverse_list(Node*& head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next; // Store the next node
current->next = prev; // Reverse the current node's link
prev = current; // Move prev to the current node
current = next; // Move current to the next node
}
head = prev; // Update head to the new first node
}
// Function to display the linked list
void display_list(Node* head) {
if (head == nullptr) {
cout << "The list is empty!" << endl;
return;
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = nullptr;
int choice, data;
while (true) {
cout << "\nMenu:\n1. Insert at End\n2. Reverse List\n3. Display List\n4. Exit\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the value to insert: ";
cin >> data;
insert_at_end(head, data);
break;
case 2:
reverse_list(head);
cout << "The list has been reversed." << endl;
break;
case 3:
cout << "The linked list is: ";
display_list(head);
break;
case 4:
cout << "Exiting program." << endl;
return 0;
default:
cout << "Invalid choice! Please try again." << endl;
}
}
return 0;
}
Output:
3. Detect a Cycle in a Linked List using Floyd’s Cycle Detection Algorithm
This program implements a linked list with a function to detect a cycle using Floyd’s Cycle Detection Algorithm and a function to display the list while handling cycles. A linked list is created with nodes, and a cycle is intentionally introduced for testing. The detect_cycle function uses two pointers (slow and fast) to determine if there is a cycle. The display_list function traverses and prints the list, stopping appropriately if a cycle is detected to avoid an infinite loop.
Code:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to create a new node
Node* create_node(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
return newNode;
}
// Function to detect a cycle in the linked list using Floyd’s Cycle Detection Algorithm
bool detect_cycle(Node* head) {
Node* slow = head; // Slow pointer
Node* fast = head; // Fast pointer
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // Move slow pointer by 1 step
fast = fast->next->next; // Move fast pointer by 2 steps
if (slow == fast) { // If both pointers meet, a cycle is detected
return true;
}
}
return false; // If no cycle is detected
}
// Function to print the linked list
void display_list(Node* head) {
Node* slow = head;
Node* fast = head;
bool cycleDetected = false;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
cycleDetected = true;
break;
}
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
// Break if the node is revisited
if (cycleDetected && temp == slow) {
cout << "(cycle detected)";
break;
}
}
if (!cycleDetected) {
cout << "NULL";
}
cout << endl;
}
int main() {
Node* head = create_node(1);
head->next = create_node(2);
head->next->next = create_node(3);
head->next->next->next = create_node(4);
head->next->next->next->next = create_node(5);
// Creating a cycle in the linked list
head->next->next->next->next->next = head->next->next;
cout << "Linked List: ";
display_list(head);
if (detect_cycle(head)) {
cout << "Cycle detected in the linked list." << endl;
} else {
cout << "No cycle detected in the linked list." << endl;
}
return 0;
}
Output:
4. Merge Two Sorted Linked Lists
This program defines a linked list structure and implements a function to merge two sorted linked lists. Nodes are created dynamically, and linked lists are constructed using user inputs. The merge_sorted_lists function recursively compares the heads of the two input lists to build a merged sorted linked list. It handles edge cases like empty lists. The display_list function prints the contents of a linked list.
Code:
#include <iostream>
using namespace std;
// Node structure for the linked list
struct Node {
int data;
Node* next;
};
// Function to create a new node
Node* create_node(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
return newNode;
}
// Function to insert a node at the end of the linked list
void insert_at_end(Node*& head, int data) {
Node* newNode = create_node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to merge two sorted linked lists
Node* merge_sorted_lists(Node* list1, Node* list2) {
// Base cases
if (!list1) return list2;
if (!list2) return list1;
Node* mergedHead = nullptr;
if (list1->data < list2->data) {
mergedHead = list1;
mergedHead->next = merge_sorted_lists(list1->next, list2);
} else {
mergedHead = list2;
mergedHead->next = merge_sorted_lists(list1, list2->next);
}
return mergedHead;
}
// Function to display a linked list
void display_list(Node* head) {
while (head != nullptr) {
cout << head->data << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
Node* list1 = nullptr;
Node* list2 = nullptr;
int n1, n2, data;
// Input for the first linked list
cout << "Enter the number of elements in the first sorted linked list: ";
cin >> n1;
cout << "Enter elements of the first sorted linked list: ";
for (int i = 0; i < n1; ++i) {
cin >> data;
insert_at_end(list1, data);
}
// Input for the second linked list
cout << "Enter the number of elements in the second sorted linked list: ";
cin >> n2;
cout << "Enter elements of the second sorted linked list: ";
for (int i = 0; i < n2; ++i) {
cin >> data;
insert_at_end(list2, data);
}
// Display the input linked lists
cout << "First Sorted Linked List: ";
display_list(list1);
cout << "Second Sorted Linked List: ";
display_list(list2);
// Merge the two sorted linked lists
Node* mergedList = merge_sorted_lists(list1, list2);
// Display the merged linked list
cout << "Merged Sorted Linked List: ";
display_list(mergedList);
return 0;
}
Output:
5. Find the Middle Element of a Linked List
This program creates a singly linked list where the user provides the number of nodes and the corresponding data. It then traverses the list using the slow and fast pointer technique to find the middle element. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.
Code:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to create a new node
Node* create_node(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
return newNode;
}
// Function to find the middle element of the linked list
int find_middle(Node* head) {
if (head == nullptr) {
cout << "The list is empty." << endl;
return -1;
}
Node* slow = head; // Slow pointer moves one step
Node* fast = head; // Fast pointer moves two steps
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // Move slow pointer by 1 step
fast = fast->next->next; // Move fast pointer by 2 steps
}
return slow->data; // Slow pointer will be at the middle
}
// Function to display the linked list
void display_list(Node* head) {
if (head == nullptr) {
cout << "The list is empty." << endl;
return;
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
int n, data;
Node* head = nullptr;
Node* tail = nullptr;
cout << "Enter the number of nodes: ";
cin >> n;
cout << "Enter the elements of the linked list: " << endl;
for (int i = 0; i < n; ++i) {
cin >> data;
Node* newNode = create_node(data);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
cout << "The linked list is: ";
display_list(head);
int middle = find_middle(head);
if (middle != -1) {
cout << "The middle element of the linked list is: " << middle << endl;
}
return 0;
}
Output:
Day 10 was a great dive into the world of linked lists, which are crucial for efficiently handling dynamic data. By implementing key operations like insertion, deletion, and traversal, I gained a deeper understanding of how to manipulate linked structures. These exercises have sharpened my skills for solving real-world problems involving linked lists. Excited for the challenges ahead as I continue to explore more advanced topics! 🚀