Linked List Important Questions With Code And Algorithm

Case 1: New node is inserted at the beginning

Case 2: New node is inserted at the end

Case 3: New node is inserted after a given node

Case 4: New node is inserted before a given node

Case 5: New node is inserted in a sorted linked list

1. Inserting a New Node at the Beginning

Algorithm-

1. Create a new node and assign data to it.
2. Set the new node’s next pointer to point to the current head.
3. Update the head to point to the new node.

Code:

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* next;
};
// Function to insert at the beginning
void insertAtBeginning(Node*& head, int newData) {
    Node* newNode = new Node();  // Create a new node
    newNode->data = newData;      // Assign data to the new node
    newNode->next = head;         // Make new node point to current head
    head = newNode;               // Update head to new node

2. Inserting a New Node at the End

Algorithm-

1. Create a new node and assign data to it.
2. If the list is empty, make the new node the head.
3. Traverse to the last node of the list.
4. Set the last node’s next pointer to the new node.

Code-

// Function to insert at the end
void insertAtEnd(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nullptr; // New node is the last node, so next is nullptr
    
    if (head == nullptr) {  // If the list is empty, new node becomes the head
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {  // Traverse to the last node
        temp = temp->next;
    }
    temp->next = newNode;  // Set last node's next to new node
}

3. Inserting a New Node After a Given Node

Algorithm-

1. Find the node after which to insert the new node.
2. Create a new node and assign data to it.
3. Set the new node’s next pointer to the given node’s next.
4. Set the given node’s next pointer to the new node.

Code-

// Function to insert after a given node
void insertAfterNode(Node* prevNode, int newData) {
    if (prevNode == nullptr) { // Check if given node is nullptr
        cout << "Previous node cannot be null" << endl;
        return;
    }

    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = prevNode->next;  // Point new node's next to given node's next
    prevNode->next = newNode;        // Point given node's next to new node
}

4. Inserting a New Node Before a Given Node

Algorithm-

1. Traverse the list to find the node just before the target node.
2. Create a new node and assign data to it.
3. Set the new node’s next pointer to point to the target node.
4. Update the previous node’s next pointer to point to the new node.

Code-

// Function to insert before a given node
void insertBeforeNode(Node*& head, Node* nextNode, int newData) {
    if (head == nullptr || nextNode == nullptr) {
        cout << "Node cannot be inserted" << endl;
        return;
    }

    if (head == nextNode) {  // If the node to insert before is the head
        insertAtBeginning(head, newData);
        return;
    }

    Node* temp = head;
    while (temp->next != nextNode && temp->next != nullptr) {
        temp = temp->next;
    }

    if (temp->next == nullptr) {
        cout << "Given node not found" << endl;
        return;
    }

    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nextNode;
    temp->next = newNode;
}

5. Inserting a New Node in a Sorted Linked List

Algorithm-

1. Create a new node and assign data to it.
2. If the list is empty or the new node should be the first node, insert at the beginning.
3. Traverse the list to find the position where the new node should be inserted.
4. Insert the new node in the appropriate position to keep the list sorted.

Code-

// Function to insert in a sorted linked list
void insertInSortedList(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;

    if (head == nullptr || head->data >= newData) {  // Insert at the beginning
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr && temp->next->data < newData) {
        temp = temp->next;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

Case 1: First node is deleted

Case 2: Last node is deleted

Case 3: Node after a given node is deleted

Case 4: Node is deleted from a sorted linked list

1. Deleting the First Node

Algorithm-

1. Check if the list is empty. If it is, return.
2. Save the current head node in a temporary pointer.
3. Update the head to point to the next node.
4. Delete the temporary node.

Code-

#include <iostream>
using namespace std;

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

// Function to delete the first node
void deleteFirstNode(Node*& head) {
    if (head == nullptr) return;  // If the list is empty, do nothing

    Node* temp = head;            // Store the head node
    head = head->next;            // Move head to the next node
    delete temp;                  // Delete the old head
}

2. Deleting the Last Node

Algorithm-

1. Check if the list is empty. If it is, return.
2. If there is only one node, delete it and update the head to nullptr.
3. Traverse to the second-last node in the list.
4. Set the next pointer of the second-last node to nullptr.
5. Delete the last node.

Code-

// Function to delete the last node
void deleteLastNode(Node*& head) {
    if (head == nullptr) return;  // If the list is empty, do nothing

    if (head->next == nullptr) {  // If there's only one node
        delete head;
        head = nullptr;
        return;
    }

    Node* temp = head;
    while (temp->next->next != nullptr) {  // Find the second-last node
        temp = temp->next;
    }

    delete temp->next;       // Delete the last node
    temp->next = nullptr;    // Update the second-last node's next to nullptr
}

3. Deleting the Node After a Given Node

Algorithm-

1. Check if the given node is nullptr or if the given node's next is nullptr.
2. If either is nullptr, return since there is no node after the given node.
3. Store the node to be deleted in a temporary pointer.
4. Update the given node’s next pointer to skip the node to be deleted.
5. Delete the temporary node.

Code-

// Function to delete the node after a given node
void deleteNodeAfter(Node* prevNode) {
    if (prevNode == nullptr || prevNode->next == nullptr) return;  // Check if deletion is possible

    Node* temp = prevNode->next;   // Node to be deleted
    prevNode->next = temp->next;   // Bypass the deleted node
    delete temp;                   // Delete the node
}

4. Deleting a Specific Node from a Sorted Linked List

Algorithm-

1. Check if the list is empty. If it is, return.
2. If the head node contains the data, delete the head.
3. Traverse the list to find the node with the matching data.
4. If the node is found, bypass it by updating the previous node’s next pointer.
5. Delete the node with the matching data.

Code-

// Function to delete a specific node from a sorted linked list
void deleteNodeFromSorted(Node*& head, int key) {
    if (head == nullptr) return;  // If the list is empty, do nothing

    if (head->data == key) {  // If the head needs to be deleted
        deleteFirstNode(head);
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr && temp->next->data != key) {
        temp = temp->next;
    }

    if (temp->next == nullptr) {  // If the key is not found
        cout << "Node with data " << key << " not found." << endl;
        return;
    }

    Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;  // Bypass the node to be deleted
    delete nodeToDelete;            // Delete the node
}

Circular LL-

Case 1: New node is inserted at the beginning

Case 2: New node is inserted at the en

1. Inserting a New Node at the Beginning

Algorithm-

1. Create a new node and assign data to it.
2. If the list is empty (head is nullptr), set the new node to point to itself and make it the head.
3. Otherwise:

• Traverse to the last node in the circular linked list (the node that points to the head).
• Set the new node’s next pointer to point to the head.
• Update the last node’s next pointer to point to the new node.
• Set the head to the new node.

Code-

#include <iostream>
using namespace std;

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

// Function to insert at the beginning of a circular linked list
void insertAtBeginning(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;

    if (head == nullptr) {  // If the list is empty
        newNode->next = newNode;  // Point to itself
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != head) {  // Find the last node
            temp = temp->next;
        }
        newNode->next = head;      // New node points to head
        temp->next = newNode;      // Last node points to new node
        head = newNode;            // Update head to new node
    }
}

2. Inserting a New Node at the End

Algorithm-

1. Create a new node and assign data to it.
2. If the list is empty (head is nullptr), set the new node to point to itself and make it the head.
3. Otherwise:

• Traverse to the last node in the circular linked list (the node that points to the head).
• Set the new node’s next pointer to point to the head.
• Update the last node’s next pointer to point to the new node.

Code-

// Function to insert at the end of a circular linked list
void insertAtEnd(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;

    if (head == nullptr) {  // If the list is empty
        newNode->next = newNode;  // Point to itself
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != head) {  // Find the last node
            temp = temp->next;
        }
        temp->next = newNode;     // Last node points to new node
        newNode->next = head;     // New node points to head
    }
}

Case 1: Node is deleted at the beginning

Case 2: Node is deleted at the end

1. Deleting the First Node

Algorithm-

1. If the list is empty (head is nullptr), return.
2. If the list has only one node (head’s next points to head):

• Delete the head and set it to nullptr.

1. Otherwise:

• Traverse to the last node (the node whose next points to head).
• Update the last node’s next to point to the second node.
• Delete the head and update the head to the second node.

Code-

#include <iostream>
using namespace std;

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

// Function to delete the first node in a circular linked list
void deleteFirstNode(Node*& head) {
    if (head == nullptr) return;  // If the list is empty, do nothing

    if (head->next == head) {     // If there's only one node
        delete head;
        head = nullptr;
    } else {
        Node* last = head;
        while (last->next != head) {  // Find the last node
            last = last->next;
        }
        
        Node* temp = head;            // Store the head node to delete
        head = head->next;            // Move head to the second node
        last->next = head;            // Update last node's next
        delete temp;                  // Delete the old head
    }
}

2. Deleting the Last Node

Algorithm-

1. If the list is empty (head is nullptr), return.
2. If the list has only one node (head’s next points to head):

• Delete the head and set it to nullptr.

1. Otherwise:

• Traverse to the second-last node in the circular linked list (the node whose next points to the last node).
• Update the second-last node’s next pointer to point to head.
• Delete the last node.

Code-

// Function to delete the last node in a circular linked list
void deleteLastNode(Node*& head) {
    if (head == nullptr) return;  // If the list is empty, do nothing

    if (head->next == head) {     // If there's only one node
        delete head;
        head = nullptr;
    } else {
        Node* temp = head;
        while (temp->next->next != head) {  // Find the second-last node
            temp = temp->next;
        }
        
        delete temp->next;       // Delete the last node
        temp->next = head;       // Update second-last node's next to head
    }
}

Thank you for reading up to this point.

If you Really Like it then ⮯

If you want to know anything related to this blog then please comment.

Thanks for reading my blog until the end. If you really enjoyed it, please give it a clap 👏 and follow me for more similar blogs.

• Follow us
• X
• LinkedIn
• YouTube
• Discord