PHP 通过双向链表的键删除所有节点

 PHP 数据结构

该方法删除双向链表中指定键（值）的所有节点。例如 - 如果给定列表是 10->20->30->10->20 并且删除所有出现的 20，则列表将变为 10->30->10。

如果双向链表的头是not null 并且 head 存储的值等于 key，然后将 head 调整为 head next，删除前一个 head 并调整链接。继续执行相同的过程，直到新头变为空或不等于密钥。之后创建一个临时节点来遍历列表并删除那些值等于键的节点并相应地调整链接。

函数pop_all就是为此目的而创建的。这是一个两步过程。

public function pop_all($key) {     
  $nodeToDelete = new Node();
  
  //1.如果 head 不为 null 并且值存储在 head 中
  //等于key，继续调整头部为
  // 下一个标题，删除上一个标题并调整链接
  //直到新头变为空或不等于键
  while($this->head != null && $this->head->data == $key) {
    $nodeToDelete = $this->head;
    $this->head = $this->head->next;
    $nodeToDelete = null;
    if ($this->head != null)
      $this->head->prev = null;
  } 

  //2。创建一个临时节点来遍历
  //列出并删除值等于的节点
  // 键入并相应调整链接
  $temp = $this->head;        
  if($temp != null) {
    while($temp->next != null) {
      if($temp->next->data == $key) {
        $nodeToDelete = $temp->next;
        $temp->next = $temp->next->next;
        if($temp->next != null)
          $temp->next->prev = $temp;  
        $nodeToDelete = null;
      } else {
        $temp = $temp->next;
      }
    }
  }
} 

下面是一个完整的程序，它使用上面讨论的概念来删除所有出现的指定键（如果存在）双向链表的。

<?php
//节点结构
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  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;
    }    
  }

  //通过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;
      if ($this->head != null)
        $this->head->prev = null;
    } 

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

  //显示列表内容
  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";
    }
  }   
};

//测试代码
$MyList = new LinkedList();

//在列表末尾添加五个元素。
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->PrintList();

//删除所有出现的20
$MyList->pop_all(20);
$MyList->PrintList();
?>

上面的代码将给出以下输出:

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