PHP Data Structures - Doubly Linked List Other Related Topics

PHP - Delete last node by key of the Doubly Linked List



In this method, last node in the doubly linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->20->40 and the last occurrence of 20 is deleted, the List becomes 10->20->30->40.

If the head of the doubly linked list is not null, create three nodes: 1. lastNode - to track the last node with value equal to key, 2. previousToLast - to track node previous to lastNode, and 3. temp - to traverse through the list. Then traverse the list to its end while updating lastNode and previousToLast whenever find a node with value equal to the specified key. At last delete lastNode and update links accordingly.

The function pop_last is created for this purpose. It is a 3-step process.

public function pop_last($key) {       

  //1. if head is not null create three nodes
  //   lastNode - to track last node with value
  //   equal to key, previousToLast - to track 
  //   node previous to lastNode, temp - to
  //   traverse through the list
  if($this->head != null) {
    $temp = new Node();
    $previousToLast = null;
    $lastNode = null;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if($this->head->data == $key) 
      $lastNode = $this->head;
    
    $temp = $this->head;
    while($temp->next != null) {
      if($temp->next->data == $key) {
        $previousToLast = $temp;
        $lastNode = $temp->next;
      }
      $temp = $temp->next;
    }
 
    //3. Delete the lastNode and update all links
    if($lastNode != null) {
      if($lastNode == $this->head) {
        $this->head = $this->head->next;
        $lastNode = null;
      } else {
        $previousToLast->next = $lastNode->next;
        if($previousToLast->next != null)
          $previousToLast->next->prev = $previousToLast;
        $lastNode = null;
      }
    }
  }
} 

The below is a complete program that uses above discussed concept to delete last occurrence of the specified key (if exists) of the 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;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->prev = $temp;
    }    
  }

  //Delete last node by key
  public function pop_last($key) {       
    if($this->head != null) {
      $temp = new Node();
      $previousToLast = null;
      $lastNode = null;

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

  //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(20);
$MyList->push_back(40);
$MyList->PrintList();

//Delete the last occurrence of 20
$MyList->pop_last(20);
$MyList->PrintList();
?>

The above code will give the following output:

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