#include <iostream> // Includes the iostream library for input/output operations

using namespace std; // Allows us to use standard library names like cout without
needing the std:: prefix

// Definition of the Node structure (used for creating nodes in a linked list)
struct Node {
// Data part of the node
int data;

// Pointer to the next node

Node* next;

// Constructor to initialize the node with a given data value

// When a new node is created, it stores the provided data, and
// the next pointer is initialized to nullptr (end of list).
Node(int data) {
this->data = data; // Assign the given data to the node's data field
this->next = nullptr; // Set the next pointer to nullptr (no next node
yet)
}
};

// Function to traverse and print the linked list

void traverseList(Node* head) {

// Initialize 'current' with the head of the linked list

Node* current = head;

// Traverse the linked list until the end (when current becomes nullptr)
while (current != nullptr) { // Loop continues as long as 'current' is not
nullptr

// Print the current node's data followed by a space

cout << current->data << " ";

// Move 'current' to the next node in the list

current = current->next;
}
cout << endl; // Print a new line at the end of the traversal
}
// Function to search for a key in the linked list
bool searchKey(Node* head, int key) {

// Initialize a pointer 'current' with the head of the linked list

Node* current = head;

// Traverse the linked list

while (current != nullptr) { // Loop until 'current' becomes nullptr (end of
list)

// If the current node's data matches the key, return true

if (current->data == key) {
return true; // Key found
}

// Move to the next node

current = current->next;
}

// If the key is not found after traversing the list, return false
return false;
}

// Function to find the length of the linked list

int lengthOfList(Node* head) {

// Initialize a pointer 'current' with the head of the linked list

Node* current = head;

// Variable to store the count of nodes in the list

int count = 0;

// Traverse the linked list until the end (when current becomes nullptr)
while (current != nullptr) { // Loop continues as long as 'current' is not
nullptr

// Increment the count for each node encountered

count++;

// Move 'current' to the next node in the list

current = current->next;
}

// Return the total number of nodes (length of the list)

return count;
}
// Function to insert a new node at the beginning of the linked list
Node* insertAtBeginning(Node* head, int dataToAdd) {

// Create a new node with the given data

Node* newNode = new Node(dataToAdd);

// Point the new node's 'next' to the current head of the linked list
newNode->next = head;

// Return the new node, which now becomes the new head of the list
//VIMP - you need to save this in the head now
return newNode;
}

// Function to insert a new node at the end of the linked list

Node* insertAtEnd(Node* head, int dataToAdd) {

// Initialize 'current' to traverse the list starting from the head

Node* current = head;

// Create a new node with the given data

Node* newNode = new Node(dataToAdd);

// If the list is empty (head is nullptr), the new node becomes the head
if (head == nullptr) {
return newNode; // Return the new node as the new head
}

// Traverse the linked list to find the last node

// (current->next != nullptr) basically means that the node current 's pointer
called next
// is not a nullptr yet and as soon as it is we know we have reached to end of
list
while (current->next != nullptr) { // Loop until 'current->next' is nullptr
(end of the list)
current = current->next; // Move to the next node
}

// Once we reach the last node, link it to the new node

current->next = newNode;

// Return the original head of the list (unchanged)

return head;
}
// Function to insert a new node after a given node with a specific key
Node* insertAfterGivenNode(Node* head, int key, int dataToAdd) {

// Initialize 'current' to start at the head of the list

Node* current = head;

// Create a new node with the data to add

Node* newNode = new Node(dataToAdd);

// Iterate through the list to find the node with the specified key
while (current != nullptr) {
if (current->data == key) {
break; // Break the loop if the node with the key is found
// this ennsures that current has the details of the key node
}
current = current->next; // Move to the next node
}

// If 'current' is nullptr, the key was not found in the list

if (current == nullptr) {
return head; // Return the original head (no insertion done)
}

// Insert the new node after the node with the specified key
newNode->next = current->next; // Point the new node to the next node after
'current'
current->next = newNode; // Link 'current' to the new node

// Return the head of the list

return head;
}
// Function to insert a new node before a given node with a specific key
Node* insertBeforeGivenNode(Node* head, int key, int dataToAdd) {

// Initialize 'current' to point to the head of the list

Node* current = head;

// Pointer to keep track of the previous node during traversal

Node* prev = nullptr;

// Create the new node to be inserted with the provided data

Node* newNode = new Node(dataToAdd);

// If the list is empty (head is nullptr), return nullptr (nothing to insert

before)
if (head == nullptr) {
return nullptr;
}

// Special case: if the key is in the head node, insert before the head
if (head->data == key) {
newNode->next = head; // Point the new node to the current head
return newNode; // Return the new node as the new head
}

// Traverse the list to find the node with the specified key
while (current != nullptr) {
if (current->data == key) {
break; // Key found, exit the loop
}
prev = current; // Store the previous node
current = current->next; // Move to the next node
}

// If the key was found (current is not nullptr)

if (current != nullptr) {
prev->next = newNode; // Link the previous node to the new node
newNode->next = current; // Link the new node to the current node
}

// Return the head of the list (unchanged)

return head;
}
// Function to insert a new node at a specified position in the linked list
Node* insertAtPosition(Node* head, int position, int dataToAdd) {

// Initialize 'current' to start at the head of the list

Node* current = head;

// Create a new node with the provided data

Node* newNode = new Node(dataToAdd);

// Initialize count to track the current position during traversal

int count = 1;

// If inserting at the beginning (position = 1)

if (position == 1) { // Check if the desired position is 1
newNode->next = head; // Link the new node to the current head
head = newNode; // The new node becomes the head of the list
return head; // Return the new head of the list
}

// Traverse the list to find the node just before the desired position
while (current != nullptr) {

// Check if the current position matches the target position

if (position == count) { // Insert at this position (after the current
node)
break; // Exit the loop when the target position is reached
}

current = current->next; // Move to the next node

count++; // Increment the count to reflect the current position
}

// If 'current' becomes nullptr, it means the position is out of bounds

if (current == nullptr) {
cout << "Position is out of bounds" << endl; // Notify that the position
is invalid
delete newNode; // Free the memory for the unused new node
return head; // Return the unchanged head
}

// Insert the new node at the desired position

newNode->next = current->next; // Link the new node to the node after
'current'
 current->next = newNode; // Link 'current' to the new node, effectively
inserting it

// Return the head of the list (unchanged)

return head;
}

// Function to remove the first node from the linked list

Node* deleteFirstNode(Node* head) {

// Check if the list is empty (head is nullptr)

if (head == nullptr) {
return nullptr; // Nothing to remove, return nullptr
}

// Store the current head node in a temporary variable

Node* temp = head;

// Move the head pointer to the next node

head = head->next;

// Free the memory allocated for the old head node

delete temp;

// Return the updated head of the list

return head;
}

// Function to delete the last node from the linked list

Node* deleteLastNode(Node* head) {

// Initialize 'current' to traverse the list

Node* current = head;

// Check if the list is empty

if (current == nullptr) {
return nullptr; // Nothing to delete, return nullptr
}

// If there is only one node in the list

if (current->next == nullptr) {
delete head; // Free the memory allocated for the head node
return nullptr; // Return nullptr as the list is now empty
}

// Traverse the list to find the last node

 while (current->next->next != nullptr) {
current = current->next; // Move to the next node
}

// 'current' is now the second to last node

delete current->next; // Free the memory for the last node
current->next = nullptr; // Set the next pointer of the second to last node
to nullptr

// Return the head of the updated list

return head;
}

// Function to delete the node that comes after the given node with the specified
key
Node* deleteAfterGivenNode(Node* head, int key) {
// Initialize 'current' to start at the head of the linked list
Node* current = head;

// Check if the list is empty (head is nullptr)

if (current == nullptr) {
return head; // Nothing to delete, return the head (nullptr)
}

// Traverse the linked list to find the node with the specified key
while (current != nullptr) {
// If the current node's data matches the key
if (current->data == key) {
// following if, Checks if the current node has a next node to delete
if (current->next != nullptr) { // if it has then
Node* temp = current->next; // Store the node to be deleted
current->next = temp->next; // Bypass the node to be deleted
delete temp; // Free the memory of the deleted
node
}
return head; // Return the head of the list (unchanged)
}
current = current->next; // Move to the next node in the list
}

// If the key is not found, return the unchanged head

return head;
}
// Function to delete the node that comes before the given node with the specified
key
Node* deleteBeforeGivenNode(Node* head, int key) {
// If the list is empty or has only one node, return head (no deletion
possible)
if (head == nullptr || head->next == nullptr) {
return head;
}

// Special case: If the node before the key is the head itself
if (head->next->data == key) {
Node* temp = head;
head = head->next; // Move head to the next node
delete temp; // Delete the old head
return head; // Return new head
}

// Initialize 'current' to traverse the list

Node* current = head;

// Traverse the list to find the node before the node with the given key
while (current->next != nullptr && current->next->next != nullptr) {
/* The condition while (current->next != nullptr && current->next->next !=
nullptr)
is used to safely traverse the linked list while ensuring that you don't
accidentally dereference a nullptr, which would lead to runtime errors or
crashes. */

// If the node two steps ahead has the key, delete the node before it
if (current->next->next->data == key) {
Node* temp = current->next; // Store the node to be deleted
current->next = temp->next; // Bypass the node to be deleted
delete temp; // Free the memory of the deleted
node
return head; // Return the head after deletion
}
current = current->next; // Move to the next node
}
 // If key is not found, return the unchanged head
return head;
}

// C++ function to delete a node at a specific position

Node* deleteAtPosition(Node* head, int position) {

// If the list is empty or the position is invalid (less than 1)

if (head == nullptr || position < 1) {
return head; // Return the unchanged list
}

// If the node at the head needs to be deleted (position 1)

if (position == 1) {
Node* temp = head; // Store the current head node in a temporary pointer
head = head->next; // Move the head pointer to the next node
delete temp; // Delete the old head node
return head; // Return the new head of the list
}

// Traverse the list to find the node just before the node to be deleted
Node* current = head;
for (int i = 1; i < position - 1 && current != nullptr; i++) {
current = current->next; // Move to the next node
}

// If the position is out of range (no such node exists)

if (current == nullptr || current->next == nullptr) {
cout << "Not In range" << endl;
return head; // Return the unchanged list
}

// Store the node to be deleted in a temporary pointer

Node* temp = current->next;

// Update the current node's next pointer to skip over the node to be deleted
current->next = current->next->next;

// Delete the node that was at the specified position

 delete temp;

// Return the head of the list (unchanged if the position is valid)

return head;
}

Node* reverseList(Node* head) {

// Initialize three pointers: curr, prev and next

Node *curr = head, *prev = nullptr, *next;

// Traverse all the nodes of Linked List

while (curr != nullptr) {

// Store next
next = curr->next;

// Reverse current node's next pointer

curr->next = prev;

// Move pointers one position ahead

prev = curr;
curr = next;
}

// Return the head of reversed linked list

return prev;
}
int main() {
// Creating a linked list with 3 nodes
Node* head = new Node(1); // First node
head->next = new Node(2); // Second node
head->next->next = new Node(3); // Third node

// Traverse and print the list

cout << "Traversing the list: ";
traverseList(head);

// Search for a key in the linked list

int key = 2;
if (searchKey(head, key)) {
cout << "Key " << key << " found in the list." << endl;
} else {
cout << "Key " << key << " not found in the list." << endl;
}

cout << "Length of list is: " << lengthOfList(head) << endl;

head = insertAtBeginning(head,12);
head = insertAtBeginning(head,13);
head = insertAtBeginning(head,900);
head = insertAtBeginning(head,23);
head = insertAtBeginning(head,339);
head = insertAtBeginning(head,450);
head = insertAtEnd(head,5000);
head = insertAfterGivenNode(head,2,12345);
head = insertBeforeGivenNode(head,1,555);
head = insertBeforeGivenNode(head,200,999);
head = insertBeforeGivenNode(head,22,999);
head = insertAtPosition(head,3,333);
head = insertAtPosition(head,1,444);
head = insertAfterGivenNode(head,2,222);
traverseList(head);
 head = deleteFirstNode(head);
head = deleteLastNode(head);
head = deleteAfterGivenNode(head,2);
head = deleteBeforeGivenNode(head,2);
head = deleteAtPosition(head,9);
traverseList(head);
reverseList(head);

return 0;
}