#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;
}
