Last Updated: Feb 3, 2025
Easy

Deleting a Node in a Linked List in C++

Table of contents
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Deleting a node in a linked list is a fundamental operation in data structure management. In C++, linked lists provide a dynamic way to store and manipulate data, allowing for efficient insertion and deletion of elements. 

Delete Node in a Linked List in C++

This article will explore the techniques for deleting a node in a linked list, including handling edge cases such as deleting the head node and managing memory effectively. By understanding these concepts, you will enhance your skills in managing linked lists and improve your overall proficiency in C++.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Why a linked list?

When we are not sure about the size beforehand, we need a data structure that stores the memory at runtime, the linked list does so. So we use a linked list when exact numbers of elements are not known to us.

singly ll

As we have already discussed that there are two types of linked list namely

  • Singly-linked list
  • Doubly Linked List

    In a singly linked list, the node contains only one pointer (next) but in doubly linked list node contains two pointers ( prev and next).
singly ll

There are many operations which can be performed in linked lists like Insertion, Deletion, Traversal among them let us talk about Deletion.

Also read - Merge sort in linked list

Deletion in a linked list


In a linked list, there is three possibilities for the deletion of a node :

  • If the node to be deleted happens to be the first node.
     
  • If the node happens to be in the middle of the list.
     
  • If the node is at the end of the list.

    Let us discuss deletion in linked list briefly:

    For the deletion of a node from the list, it involves two major steps:

    • Step1: Search for the availability of the node in the list.
    • Step2: If available, make its previous node pointing to its next node.
Linked List

Deleting node from the beginning of the list

The function for the deletion of the node is DeleteNodeBeg(). Let’s go through its code.
 

#include <iostream>
using namespace std;

// Define the structure for a node in the linked list
struct Node {
    int data;       // Data part of the node
    Node* next;     // Pointer to the next node
};

// Class for the linked list
class LinkedList {
private:
    Node* start; // Pointer to the first node of the list

public:
    // Constructor to initialize the linked list
    LinkedList() {
        start = nullptr; // Initially, the list is empty
    }

    // Function to add a node at the end of the list
    void addNode(int value) {
        Node* newNode = new Node(); // Create a new node
        newNode->data = value;      // Set the data for the new node
        newNode->next = nullptr;    // New node will be the last node

        if (start == nullptr) {
            start = newNode; // If the list is empty, make the new node the start
        } else {
            Node* temp = start;
            while (temp->next != nullptr) { // Traverse to the end of the list
                temp = temp->next;
            }
            temp->next = newNode; // Link the last node to the new node
        }
    }

    // Function to delete a node from the beginning of the list
    void DeleteNodeBeg() {
        if (start == nullptr) {
            cout << "Underflow" << "\n"; // List is empty
        } else {
            Node* ptr = start; // Pointer to the first node
            start = start->next; // Move the start pointer to the next node
            delete ptr; // Free the memory of the deleted node
            cout << "Node deleted from the beginning\n";
        }
    }

    // Function to display the linked list
    void display() {
        if (start == nullptr) {
            cout << "List is empty\n"; // If the list is empty
            return;
        }
        Node* temp = start;
        cout << "Linked List: ";
        while (temp != nullptr) { // Traverse the list
            cout << temp->data << " -> "; // Print each node's data
            temp = temp->next;
        }
        cout << "nullptr\n"; // Indicate the end of the list
    }
};

int main() {
    LinkedList list; // Create a linked list

    // Add some nodes to the list
    list.addNode(10);
    list.addNode(20);
    list.addNode(30);
    
    list.display(); // Display the list

    // Delete a node from the beginning
    list.DeleteNodeBeg();
    list.display(); // Display the list after deletion

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

Linked List: 10 -> 20 -> 30 -> nullptr
Node deleted from the beginning
Linked List: 20 -> 30 -> nullptr


In our code DeleteNodeBeg() is the function that we created to delete the first node. In this start is the pointer which is checking whether the list contains any element or it is empty. As it found that any element is stored in the list, it goes to the else part of the program.

Here, the address stored in the start pointer is assigned to the ptr pointer, now the start pointer is empty as the address stored in it is assigned to the ptr pointer, now in the second statement of the else block, the address of the next node is assigned to the start pointer, in third the statement, we deleted the ptr pointer as it stores the address of the first node which we want to delete.

Deleting node from the middle of the list

If the length of the linked list is odd then delete (( n+1)/2)th term of the linked list and if the list is of even length then delete the (n/2+1)th term of the linked list. To delete a the middle note we have to follow some points:

  • Let two pointers namely ptr1 and ptr2.
  • Each time increment ptr1 by 1 and ptr2 by 2.
  • Repeat step 2 until ptr2 goes to the end of the linked list.
  • When ptr2 is at the end of the list, at the same time ptr1 will be at the middle of the list.
     
#include <iostream>
using namespace std;

// Define the structure for a node in the linked list
struct Node {
    int data;       // Data part of the node
    Node* next;     // Pointer to the next node
};

// Class for the linked list
class LinkedList {
private:
    Node* start; // Pointer to the first node of the list

public:
    // Constructor to initialize the linked list
    LinkedList() {
        start = nullptr; // Initially, the list is empty
    }

    // Function to add a node at the end of the list
    void addNode(int value) {
        Node* newNode = new Node(); // Create a new node
        newNode->data = value;      // Set the data for the new node
        newNode->next = nullptr;    // New node will be the last node

        if (start == nullptr) {
            start = newNode; // If the list is empty, make the new node the start
        } else {
            Node* temp = start;
            while (temp->next != nullptr) { // Traverse to the end of the list
                temp = temp->next;
            }
            temp->next = newNode; // Link the last node to the new node
        }
    }

    // Function to delete a node from the middle of the list
    void DeleteNodeMid() {
        if (start == nullptr) {
            cout << "Underflow" << "\n"; // List is empty
            return;
        }

        Node* ptr1 = start;           // Pointer to find the middle node
        Node* ptr2 = start->next;     // Pointer to traverse the list

        // Traverse the list to find the middle node
        while (ptr2 != nullptr && ptr2->next != nullptr) {
            ptr1 = ptr1->next;        // Move ptr1 one step
            ptr2 = ptr2->next->next;  // Move ptr2 two steps
        }

        // If ptr1 is null, it means we have only one node
        if (ptr1 != nullptr && ptr1->next != nullptr) {
            Node* temp = ptr1->next;  // Store the node to be deleted
            ptr1->next = ptr1->next->next; // Link the previous node to the next of the node to be deleted
            delete temp;               // Free the memory of the deleted node
            cout << "Middle node deleted\n";
        }
    }

    // Function to display the linked list
    void display() {
        if (start == nullptr) {
            cout << "List is empty\n"; // If the list is empty
            return;
        }
        Node* temp = start;
        cout << "Linked List: ";
        while (temp != nullptr) { // Traverse the list
            cout << temp->data << " -> "; // Print each node's data
            temp = temp->next;
        }
        cout << "nullptr\n"; // Indicate the end of the list
    }
};

int main() {
    LinkedList list; // Create a linked list

    // Add some nodes to the list
    list.addNode(10);
    list.addNode(20);
    list.addNode(30);
    list.addNode(40);
    list.addNode(50);

    list.display(); // Display the list

    // Delete a node from the middle
    list.DeleteNodeMid();
    list.display(); // Display the list after deletion

    return 0;
}

You can also try this code with Online C++ Compiler
Run Code

Output

Linked List: 10 -> 20 -> 30 -> 40 -> 50 -> nullptr 
Middle node deleted Linked List: 10 -> 20 -> 40 -> 50 -> nullptr

Deleting a node from the end of the list

As we know that in a it, the last node of the linked list contains data in its info part and NULL in its pointer part. To delete the last node we should find the second last node of the list and make its pointer part carry NULL.

Algorithm:
1. If the first node is null or there is only one node, then return null.
2. Find Second last node.

  • Delete last node.
  • Change next of second last in NULL.
     
#include <iostream>
using namespace std;

// Define the structure for a node in the linked list
struct Node {
    int data;       // Data part of the node
    Node* next;     // Pointer to the next node
};

// Class for the linked list
class LinkedList {
private:
    Node* start; // Pointer to the first node of the list

public:
    // Constructor to initialize the linked list
    LinkedList() {
        start = nullptr; // Initially, the list is empty
    }

    // Function to add a node at the end of the list
    void addNode(int value) {
        Node* newNode = new Node(); // Create a new node
        newNode->data = value;      // Set the data for the new node
        newNode->next = nullptr;    // New node will be the last node

        if (start == nullptr) {
            start = newNode; // If the list is empty, make the new node the start
        } else {
            Node* temp = start;
            while (temp->next != nullptr) { // Traverse to the end of the list
                temp = temp->next;
            }
            temp->next = newNode; // Link the last node to the new node
        }
    }

    // Function to delete the last node of the linked list
    void DeleteLastNode() {
        if (start == nullptr) {
            cout << "Underflow: List is empty" << "\n"; // List is empty
            return;
        }

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

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

        // Delete the last node
        delete(second_last->next);
        // Change next of second last to null
        second_last->next = nullptr;
        cout << "Last node deleted\n";
    }

    // Function to display the linked list
    void display() {
        if (start == nullptr) {
            cout << "List is empty\n"; // If the list is empty
            return;
        }
        Node* temp = start;
        cout << "Linked List: ";
        while (temp != nullptr) { // Traverse the list
            cout << temp->data << " -> "; // Print each node's data
            temp = temp->next;
        }
        cout << "nullptr\n"; // Indicate the end of the list
    }
};

int main() {
    LinkedList list; // Create a linked list

    // Add some nodes to the list
    list.addNode(10);
    list.addNode(20);
    list.addNode(30);
    list.addNode(40);
    list.addNode(50);

    list.display(); // Display the list

    // Delete a node from the end
    list.DeleteLastNode();
    list.display(); // Display the list after deletion

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

Linked List: 10 -> 20 -> 30 -> 40 -> 50 -> nullptr
Last node deleted
Linked List: 10 -> 20 -> 30 -> 40 -> nullptr

Frequently Asked Questions

What is a linked list in C++?

A linked list is a linear data structure that instead of storing data at contiguous memory locations, stores data at random locations, and each node is linked to the other by the use of pointers.

How do I remove a node from a linked list?

To remove a node from a linked list, locate the node, adjust the pointers of the previous node to bypass it, and free the memory occupied by the node. Ensure to handle edge cases like deleting the head node.

What happens when a node is deleted?

When a node is deleted, its memory is deallocated, and the connections with neighboring nodes are updated to maintain the linked list's structure. If the deleted node is the head, the head pointer must also be updated to the next node.

How to delete a specific node in a linked list in C++?

To delete a specific node in a linked list in C++, traverse the list to find the node, adjust the previous node's next pointer, and free the memory of the target node. Ensure to handle cases where the node is the head or doesn't exist.

Conclusion

In this article, we learned how to delete a node in a linked list using C++. We looked at why we need a linked list, and later in the article looked at some of the ways on how you can delete a node in a linked list. 

Recommended Reading: