C++ program to delete alternate nodes of a Linked List

June 25, 2020

Delete alternate nodes of a linked list in C++

How to delete alternate nodes of a Singly Linked List in C++?

Deleting alternate nodes of the linked list means to keep one node and delete another for example if the data in the list is 14,7,6,20 and 56 it should return 14,6 and 56 after deleting alternate node 7 and 20. In this article, we will learn how to code a C++ program to delete alternate nodes of a linked list.

 

Steps to write a C++ program to delete alternate nodes of a linked list

S

T

E

P

S

If we want to delete alternate nodes of a linked list, following steps are followed.

  1. Create linked list using the set of code defined below.
  2. Initialize the variables.
  3. Create a function named make() to create all the nodes of linked list.
  4. Now we need a display function that will be help us to show list before and after deletion.
  5. Create that display function.
  6. Create a function to delete alternate nodes named alternateDel().
  7. Take two pointers prev and alt_node
  8. Initially prev will points to head and alt_node will points to second node .
  9. Make the link of prev to point to link of alt_node and free alt_node.
  10. Traverse prev to next node.
  11. Traverse alt_node to next node of prev.
  12. Repeat step 9,10, and 11 until prev and alt_node becomes null.
  13. Print list after deleting alternate nodes.

S

T

E

P

S

If we want to delete alternate nodes of a linked list, following steps are followed.

  1. Create linked list using the set of code defined below.
  2. Initialize the variables.
  3. Create a function named make() to create all the nodes of linked list.
  4. Now we need a display function that will be help us to show list before and after deletion.
  5. Create that display function.
  6. Create a function to delete alternate nodes named alternateDel().
  7. Take two pointers prev and alt_node
  8. Initially prev will points to head and alt_node will points to second node .
  9. Make the link of prev to point to link of alt_node and free alt_node.
  10. Traverse prev to next node.
  11. Traverse alt_node to next node of prev.
  12. Repeat step 9,10, and 11 until prev and alt_node becomes null.
  13. Print list after deleting alternate nodes.

How to struct node of a linked list?

Syntax 

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

Following set of code is used to define a linked list in our program.

C++ program to delete alternate nodes of a linked list

Algorithm to delete alternate nodes of a linked list

A

L

G

O

R

I

T

H

M

Following algorithm is used to delete alternate nodes of a linked list.

  1. IF STNODE==NULL
  2. EXIT
  3. WHILE (PREV!=NULL&&ALT_NODE!=NULL)
  4. PREV->NEXTPTR=ALT_NODE->NEXTPTR
  5. FREE(ALT_NODE)
  6. PREV=PREV->NEXTPTR
  7. IF(PREV!=nULL)
  8. ALT_NODE=PREV->NEXTPTR
  9. PRINT

A

L

G

O

R

I

T

H

M

Following algorithm is used to delete alternate nodes of a linked list.

  1. IF STNODE==NULL
  2. EXIT
  3. WHILE (PREV!=NULL&&ALT_NODE!=NULL)
  4. PREV->NEXTPTR=ALT_NODE->NEXTPTR
  5. FREE(ALT_NODE)
  6. PREV=PREV->NEXTPTR
  7. IF(PREV!=nULL)
  8. ALT_NODE=PREV->NEXTPTR
  9. PRINT

Program to delete alternate nodes of a linked list in C++

#include <iostream>
using namespace std;

struct node 
{
    int num;                
    node *nextptr;             
}*stnode; //node declared

void make(int n);                 
void alternateDel(node *stnode);	            
void print();

 
int main() //main method
{
    int n,num;
		
    cout<<"Enter the number of nodes: ";
    cin>>n;
    make(n);
    cout<<"\nLinked list data: \n";		
    print();
    cout<<"\nAfter deleting alternate node:\n";
    alternateDel(stnode);
    print();
    return 0;
}
void make(int n) //function to create linked list.
{
    struct node *frntNode, *tmp;
    int num, i;
 
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL)        
    {
        cout<<" Memory can not be allocated";
    }
    else
    {
                                  
        cout<<"Enter the data for node 1: ";
        cin>>num;
        stnode-> num = num;      
        stnode-> nextptr = NULL; //Links the address field to NULL
        tmp = stnode;
 
        for(i=2; i<=n; i++)
        {
            frntNode = (struct node *)malloc(sizeof(struct node)); 
 

            if(frntNode == NULL) //If frntnode is null no memory cannot be alloted
            {
                cout<<"Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Enter the data for node "<<i<<": "; // Entering data in nodes.
                cin>>num;
                frntNode->num = num;         
                frntNode->nextptr = NULL;    
                tmp->nextptr = frntNode;     
                tmp = tmp->nextptr;
            }
        }
    }
} 

void print() //function to display linked list
{
    struct node *tmp;
    if(stnode == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        tmp = stnode;
        cout<<"Linked List\t";
        while(tmp != NULL)
        {
            cout<<tmp->num<<"\t";   
            tmp = tmp->nextptr;                
        }
    }
}
void alternateDel(node *stnode)  //function to delete alternate nodes.
{  
    if (stnode == NULL)  
        return;  
  
    
    node *prev = stnode;  
    node *alt_node = stnode->nextptr;  
  
    while (prev != NULL && alt_node != NULL)  
    {  
     
        prev->nextptr = alt_node->nextptr;  
  
        free(alt_node);  
  
        prev = prev->nextptr;  
        if (prev != NULL)  
            alt_node = prev->nextptr;  
    }  
} 
Output: 
Enter the number of nodes: 5
Enter the data for node 1: 14
Enter the data for node 2: 7
Enter the data for node 3: 6
Enter the data for node 4: 20
Enter the data for node 5: 56

Linked list data: 
Linked List	14	7	6	20	56	
After deleting alternate node:
Linked List	14	6	56

Deletion in a linked list

Deletion in linked list