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.

// 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.

#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