Facebook Page Twitter Page LinkedIn Page
× PHP Data Structures - Circular Doubly Linked List Other Related Topics


In this method, all nodes in the circular doubly 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 list becomes 10->30->10.

If the head of the circular doubly linked list is not null and the value stored at head is equal to key, then adjust the head as head next, delete previous head and adjust links. 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.

public function pop_all($key) {     
  $nodeToDelete = new Node();
  $temp = 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) {

    if($this->head->next == $this->head) {
      $this->head = null;
    } else {
      $nodeToDelete = $this->head;
      $temp = $this->head;
      // traverse to the last element of
      // the list to adjust links
      while($temp->next != $this->head) {
        $temp = $temp->next;
      } 
      $this->head = $this->head->next;
      $temp->next = $this->head;   
      $this->head->prev = $temp;
      $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 != $this->head) {
      if($temp->next->data == $key) {
        $nodeToDelete = $temp->next;
        $temp->next = $temp->next->next;
        $temp->next->prev = $temp;
        $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 circular doubly linked list.

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

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; 
    $newNode->prev = null;
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
      $newNode->prev = $temp;
      $this->head->prev = $newNode;
    }    
  }

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

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

    $temp = $this->head;        
    if($temp != null) {
      while($temp->next != $this->head) {
        if($temp->next->data == $key) {
          $nodeToDelete = $temp->next;
          $temp->next = $temp->next->next;
          $temp->next->prev = $temp;
          $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 "\nThe list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
    } else {
      echo "\nThe list is empty.";
    }
  }    
};

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