Data Structures - Linked List Other Related Topics
Data Structures - Linked List Other Related Topics

Linked List - Delete all nodes by key

In this method, all nodes in the linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->10->20 and all occurrences of 20 are deleted, the Linked List becomes 10->30->10.

If the head of the linked list is not null and the value stored at head is equal to key, then adjust the head as head next and delete previous head. Keep on doing the same process until the new head becomes null or not equal to the key. After that create a temp node to traverse through the list and delete those nodes with value equal to the key and adjust links accordingly.

The function pop_all is created for this purpose. It is a 2-step process.

void pop_all(int key) {     
  Node* nodeToDelete;
  
  //1. if the head is not null and value stored at
  //   head is equal to key, keep on adjusting the
  //   head as head next and deleting previous head
  //   until new head becomes null or not equal to key
  while(head != NULL && head->data == key) {
    nodeToDelete = head;
    head = head->next;
    free(nodeToDelete);
  } 

  //2. create a temp node to traverse through the
  //   list and delete nodes with value equal to 
  //   key and adjust links accordingly
  Node* temp = head;        
  if(temp != NULL) {
    while(temp->next != NULL) {
      if(temp->next->data == key) {
        nodeToDelete = temp->next;
        temp->next = temp->next->next;
        free(nodeToDelete);
      } else {
        temp = temp->next;
      }
    }
  }
} 

void pop_all(struct Node** head_ref, int key) {     
  struct Node* nodeToDelete;
  
  //1. if the head is not null and value stored at
  //   head is equal to key, keep on adjusting the
  //   head as head next and deleting previous head
  //   until new head becomes null or not equal to key
  while(*head_ref != NULL && (*head_ref)->data == key) {
    nodeToDelete = *head_ref;
    *head_ref = (*head_ref)->next;
    free(nodeToDelete);
  } 

  //2. create a temp node to traverse through the
  //   list and delete nodes with value equal to 
  //   key and adjust links accordingly
  struct Node* temp = *head_ref;        
  if(temp != NULL) {
    while(temp->next != NULL) {
      if(temp->next->data == key) {
        nodeToDelete = temp->next;
        temp->next = temp->next->next;
        free(nodeToDelete);
      } else {
        temp = temp->next;
      }
    }
  }
}   

def pop_all(self, key):   
  
  #1. if the head is not null and value stored at
  #   head is equal to key, keep on adjusting the
  #   head as head next and deleting previous head
  #   until new head becomes null or not equal to key
  while(self.head != None and self.head.data == key):
    nodeToDelete = self.head
    self.head = self.head.next
    nodeToDelete = None

  #2. create a temp node to traverse through the
  #   list and delete nodes with value equal to 
  #   key and adjust links accordingly
  temp = self.head        
  if(temp != None):
    while(temp.next != None):
      if(temp.next.data == key):
        nodeToDelete = temp.next
        temp.next = temp.next.next
        nodeToDelete = None
      else:
        temp = temp.next

void pop_all(int key) {     
  Node nodeToDelete = new Node();
  
  //1. if the head is not null and value stored at
  //   head is equal to key, keep on adjusting the
  //   head as head next and deleting previous head
  //   until new head becomes null or not equal to key
  while(head != null && head.data == key) {
    nodeToDelete = head;
    head = head.next;
    nodeToDelete = null;
  } 

  //2. create a temp node to traverse through the
  //   list and delete nodes with value equal to 
  //   key and adjust links accordingly
  Node temp = head;        
  if(temp != null) {
    while(temp.next != null) {
      if(temp.next.data == key) {
        nodeToDelete = temp.next;
        temp.next = temp.next.next;
        nodeToDelete = null;
      } else {
        temp = temp.next;
      }
    }
  }
} 

public void pop_all(int key) {     
  Node nodeToDelete = new Node();
  
  //1. if the head is not null and value stored at
  //   head is equal to key, keep on adjusting the
  //   head as head next and deleting previous head
  //   until new head becomes null or not equal to key
  while(head != null && head.data == key) {
    nodeToDelete = head;
    head = head.next;
    nodeToDelete = null;
  } 

  //2. create a temp node to traverse through the
  //   list and delete nodes with value equal to 
  //   key and adjust links accordingly
  Node temp = head;        
  if(temp != null) {
    while(temp.next != null) {
      if(temp.next.data == key) {
        nodeToDelete = temp.next;
        temp.next = temp.next.next;
        nodeToDelete = null;
      } else {
        temp = temp.next;
      }
    }
  }
} 

public function pop_all($key) {     
  $nodeToDelete = new Node();
  
  //1. if the head is not null and value stored at
  //   head is equal to key, keep on adjusting the
  //   head as head next and deleting previous head
  //   until new head becomes null or not equal to key
  while($this->head != null && $this->head->data == $key) {
    $nodeToDelete = $this->head;
    $this->head = $this->head->next;
    $nodeToDelete = null;
  } 

  //2. create a temp node to traverse through the
  //   list and delete nodes with value equal to 
  //   key and adjust links accordingly
  $temp = $this->head;        
  if($temp != null) {
    while($temp->next != null) {
      if($temp->next->data == $key) {
        $nodeToDelete = $temp->next;
        $temp->next = $temp->next->next;
        $nodeToDelete = null;
      } else {
        $temp = $temp->next;
      }
    }
  }
}

The below is a complete program that uses above discussed concept to delete all occurrences of the specified key (if exists) of the linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL; 
      if(head == NULL) {
        head = newNode;
      } else {
        Node* temp = head;
        while(temp->next != NULL)
          temp = temp->next;
        temp->next = newNode;
      }    
    }

    //Delete all nodes by key
    void pop_all(int key) {     
      Node* nodeToDelete;
      while(head != NULL && head->data == key) {
        nodeToDelete = head;
        head = head->next;
        free(nodeToDelete);
      } 

      Node* temp = head;        
      if(temp != NULL) {
        while(temp->next != NULL) {
          if(temp->next->data == key) {
            nodeToDelete = temp->next;
            temp->next = temp->next->next;
            free(nodeToDelete);
          } else {
            temp = temp->next;
          }
        }
      }
    } 

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<"\n";
      } else {
        cout<<"The list is empty.\n";
      }
    }   
};

// test the code
int main() {
  LinkedList MyList;

  //Add five elements at the end of the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.push_back(10);
  MyList.push_back(20);  
  MyList.PrintList();

  //Delete all occurrences of 20
  MyList.pop_all(20);
  MyList.PrintList();
  
  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 

#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode; 
  } else {
    temp = *head_ref;
    while(temp->next != NULL) {
      temp = temp->next;
    }    
    temp->next = newNode;
  }
}

//Delete all nodes by key
void pop_all(struct Node** head_ref, int key) {     
  struct Node* nodeToDelete;
  while(*head_ref != NULL && (*head_ref)->data == key) {
    nodeToDelete = *head_ref;
    *head_ref = (*head_ref)->next;
    free(nodeToDelete);
  } 

  struct Node* temp = *head_ref;        
  if(temp != NULL) {
    while(temp->next != NULL) {
      if(temp->next->data == key) {
        nodeToDelete = temp->next;
        temp->next = temp->next->next;
        free(nodeToDelete);
      } else {
        temp = temp->next;
      }
    }
  }
}    

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (temp != NULL) {
      printf("%i ",temp->data);
      temp = temp->next;  
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code
int main() {
  struct Node* MyList = NULL;

  //Add five elements at the end of the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  PrintList(MyList);

  //Delete all occurrences of 20
  pop_all(&MyList, 20);
  PrintList(MyList);

  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode

  #Delete all nodes by key
  def pop_all(self, key):   
    while(self.head != None and self.head.data == key):
      nodeToDelete = self.head
      self.head = self.head.next
      nodeToDelete = None

    temp = self.head        
    if(temp != None):
      while(temp.next != None):
        if(temp.next.data == key):
          nodeToDelete = temp.next
          temp.next = temp.next.next
          nodeToDelete = None
        else:
          temp = temp.next

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      print()
    else:
      print("The list is empty.")

# test the code                
MyList = LinkedList()

#Add five elements at the end of the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(10)
MyList.push_back(20)
MyList.PrintList()

#Delete all occurrences of 20
MyList.pop_all(20)
MyList.PrintList()

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 

//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the end of the list
  void push_back(int newElement) {
    Node newNode = new Node(); 
    newNode.data = newElement;
    newNode.next = null;
    if(head == null) {
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
    }    
  }

  //Delete all nodes by key
  void pop_all(int key) {     
    Node nodeToDelete = new Node();
    
    while(head != null && head.data == key) {
      nodeToDelete = head;
      head = head.next;
      nodeToDelete = null;
    } 

    Node temp = head;        
    if(temp != null) {
      while(temp.next != null) {
        if(temp.next.data == key) {
          nodeToDelete = temp.next;
          temp.next = temp.next.next;
          nodeToDelete = null;
        } else {
          temp = temp.next;
        }
      }
    }
  } 

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }    
};

// test the code
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements at the end of the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.PrintList();

    //Delete all occurrences of 20
    MyList.pop_all(20);
    MyList.PrintList();    
  }
}

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 

using System;

//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  Node head;

  public LinkedList(){
    head = null;
  }
  
  //Add new element at the end of the list
  public void push_back(int newElement) {
    Node newNode = new Node(); 
    newNode.data = newElement;
    newNode.next = null;
    if(head == null) {
      head = newNode;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
    }    
  }

  //Delete all nodes by key
  public void pop_all(int key) {     
    Node nodeToDelete = new Node();

    while(head != null && head.data == key) {
      nodeToDelete = head;
      head = head.next;
      nodeToDelete = null;
    } 

    Node temp = head;        
    if(temp != null) {
      while(temp.next != null) {
        if(temp.next.data == key) {
          nodeToDelete = temp.next;
          temp.next = temp.next.next;
          nodeToDelete = null;
        } else {
          temp = temp.next;
        }
      }
    }
  } 

  //display the content of the list
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("The list contains: ");
      while(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
      Console.WriteLine();
    } else {
      Console.WriteLine("The list is empty.");
    }
  }     
};
// test the code
class Implementation {
  static void Main(string[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements at the end of the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.PrintList(); 

    //Delete all occurrences of 20
    MyList.pop_all(20);
    MyList.PrintList();     
  }
}

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10 

<?php
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //Add new element at the end of the list
  public function push_back($newElement) {
    $newNode = new Node(); 
    $newNode->data = $newElement;
    $newNode->next = null;
    if($this->head == null) {
      $this->head = $newNode;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
    }    
  }

  //Delete all nodes by key
  public function pop_all($key) {     
    $nodeToDelete = new Node();
    while($this->head != null && $this->head->data == $key) {
      $nodeToDelete = $this->head;
      $this->head = $this->head->next;
      $nodeToDelete = null;
    } 

    $temp = $this->head;        
    if($temp != null) {
      while($temp->next != null) {
        if($temp->next->data == $key) {
          $nodeToDelete = $temp->next;
          $temp->next = $temp->next->next;
          $nodeToDelete = null;
        } else {
          $temp = $temp->next;
        }
      }
    }
  } 

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }   
};

// test the code
$MyList = new LinkedList();

//Add five elements at the end of the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->PrintList();

//Delete all occurrences of 20
$MyList->pop_all(20);
$MyList->PrintList();  
?>

The above code will give the following output: 

The list contains: 10 20 30 10 20 
The list contains: 10 30 10
AlphaCodingSkills
AlphaCodingSkills Android App
Facebook Page Twitter Page LinkedIn Page
Learning Tutorials
Learning Tutorials
Useful Links
Python Libraries
About Us  |  Privacy Policy  |  Contact Us
AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.