Delete nth node in Linked List in C++

C+++ Program to delete nth Node from a Singly Linked List

On this article will learn to write a program to delete the nth node from a singly Linked List in C++

delete

Delete a Linked List node at a given position in C++

Following are the steps –

  • Insert the initial items in the linked list
  • Calculate the current size of the linked list
  • Ask the user for nth position he wants to delete
  • if(n < 1 || n > size) then say invalid
  • If deleting the first node, just change the head to the next item in Linked List
  • Else traverse to the nth node to delete
  • Change the next of (n-1)th node to (n+1)th node
  • Free the memory for th nth node
Delete nth node in Linked List in C++

Constructing a singly linked list in C++

Nodes of singly linked list is defined by using the set of code given below. Whole linked list will be build by each set of nodes using this code.

class Node  
{   
    int data;  
    Node *next;  
};
deletion of nth node in Singly Linked List in C++

Program for deleting nth Node from Linked List

The following method uses non member functions with head explicitly passed in the function.
Run
// deletion of th nth node in a Linked List in C++
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};
int calcLen(Node* node){
    
    int len = 0;

    while(node!=NULL){
        node = node->next;
        len++;
    }
    return len;
}

void insert(Node** head, int data){
    Node* new_node = new Node();
    
    new_node->data = data;
    new_node->next = *head;
    *head = new_node;
}

void deleteNthNode(int n, Node** head){
    Node* temp = *head;
    Node* prevNode;
    
    int len = calcLen(*head);
    
    if(n < 1 || n > len){
        cout << "Invalid" << endl; 
        return; 
    } 

    // delete the 1st node 
    if(n == 1){ 
        *head = (*head)->next;
        cout << temp->data << " deleted" << endl; 
        delete(temp); 
        return; 
    } 

    // traverse to the n'th node 
    while (--n) { 
        prevNode = temp; 
        temp = temp->next; 
    }

    // change prevNode node's next node to nth node's next node
    prevNode->next = temp->next;

    // delete this nth node
    cout << temp->data << " deleted" << endl;;
    delete(temp);
}

void printList(Node* temp){
    
    cout << "Linked List : ";
    
    // as linked list will end when Node is Null
    while(temp!=NULL){
        cout << temp->data << " "; 
        temp = temp->next;
    }
    cout << endl;
}

int main()
{
    Node* head = NULL;
    
    insert(&head, 25);
    insert(&head, 24);
    insert(&head, 23);
    insert(&head, 22);
    insert(&head, 21);
    insert(&head, 20);
    
    printList(head); 
   
    deleteNthNode(2, &head);
    
    deleteNthNode(4, &head);
    
    printList(head); 

    return 0; 
}

Output

Linked List : 20 21 22 23 24 25 
21 deleted
24 deleted
Linked List : 20 22 23 25
The following method uses class member functions which can access the class’s member variable head so no need to explicitly pass head in function.
Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        int calcSize();
        void deleteStart();
        void deleteEnd();
        void deleteNthNode(int n);
        void printList();
        void insert(int data);
};

void LinkedList::deleteNthNode(int n)
{
    Node* temp = head;
    Node* previous;

    
    int size = calcSize();

    if(n < 1 || n > size){
        cout << "\nEnter valid position\n"; 
        return; 
    } 

    // if first node has to be deleted 
    if(n == 1) { 
        head = head->next;
        cout << "\nValue deleted: " << temp->data << endl; 
        delete(temp); 
        return; 
    }

     //traverse till the nth node 
    while (--n) 
    { 
        // store previous link as we need to change its next val 
        previous = temp; 
        temp = temp->next; 
    }
    
    // previous node's next changed to nth node's next
    previous->next = temp->next;

    cout << "Value deleted: " << temp->data << endl; 
    delete(temp); 
} 

int LinkedList::calcSize(){ 
    Node* node = new Node(); 
    node = head; 

    int size = 0; 

    while(node!=NULL){ 
        node = node->next;
        size++;
    }
    return size;
}

void LinkedList::insert(int data){

    Node* newNode = new Node();
    
    newNode->data = data;
    newNode->next = head;

    // assigned head to newNode
    head = newNode;
}
void LinkedList::printList(){
    
    Node* temp = new Node();
    temp = head;
    
    cout << "Linked List : ";

    //as linked list will end when Node is Null
    while(temp!=NULL){
        cout << temp->data << " "; 
        temp = temp->next;
    }
    cout << endl; 
} 

int main(){ 
    LinkedList* list = new LinkedList(); 
    list->insert(25);
    list->insert(24);
    list->insert(24);
    list->insert(22);
    list->insert(21);
    list->insert(20);

    list->printList(); 
   
    list->deleteNthNode(2);
    
    list->deleteNthNode(4);
    
    list->printList();
    
    return 0;
}

Output

Linked List : 20 21 22 24 24 25 
Value deleted: 21
Value deleted: 24
Linked List : 20 22 24 25