PHP 通过循环双向链表的键删除第一个节点

 PHP 数据结构

在此方法中，删除循环双向链表中具有指定键（值）的第一个节点。例如 - 如果给定列表是 10->20->30->10->20 并且删除第一次出现的 20，则列表将变为 10->30->10->20。

首先，检查链表是否为空值。如果 head 不为 null，则其中存储的值等于键，并且 head 是列表中唯一的元素，则将 head 设为 null。如果 head 不为 null，则其中存储的值等于键，列表包含多个元素，则将 head 下一个作为 head，并用新的 head 更新列表最后一个元素的链接。否则，遍历到value等于key的节点的前一个节点，并调整链接。

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

public function pop_first($key) {
  
  //1.如果 head 不为空，则创建三个节点 - temp，
  // nodeToDelete 和 lastNode - 遍历并到
  //跟踪最后一个节点和要删除的节点
  if($this->head != null) {
    $temp = $this->head;
    $nodeToDelete = $this->head;
    $lastNode = new Node();

    //2。如果 head 的值存储是 key 和 head
    //是列表中唯一的元素，使其为空
    if($temp->data == $key) {
      if($temp->next == $this->head) {
        $this->head = null;
      } else {

        //3。如果头部的值存储是键和列表
        //包含超过1个元素，调整链接
        $lastNode = $this->head->prev;
        $this->head = $this->head->next;
        $lastNode->next = $this->head;
        $this->head->prev = $lastNode;
        $nodeToDelete = null; 
      }
    } else {
      
      //4。否则，遍历到之前的节点
      //value等于key的节点，并调整链接
      while($temp->next != $this->head) {
        if($temp->next->data == $key) {
          $nodeToDelete = $temp->next;
          $temp->next = $temp->next->next;
          $temp->next->prev = $temp;
          $nodeToDelete = null;
          break; 
        }
        $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;
      $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;
    }    
  }

  //通过key删除第一个节点
  public function pop_first($key) { 
    if($this->head != null) {
      $temp = $this->head;
      $nodeToDelete = $this->head;
      $lastNode = new Node();
      if($temp->data == $key) {
        if($temp->next == $this->head) {
          $this->head = null;
        } else {
          $lastNode = $this->head->prev;
          $this->head = $this->head->next;
          $lastNode->next = $this->head;
          $this->head->prev = $lastNode;
          $nodeToDelete = null; 
        }
      } else {
        while($temp->next != $this->head) {
          if($temp->next->data == $key) {
            $nodeToDelete = $temp->next;
            $temp->next = $temp->next->next;
            $temp->next->prev = $temp;
            $nodeToDelete = null;
            break; 
          }
          $temp = $temp->next;
        }
      }
    }
  }

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      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_first(20);
$MyList->PrintList();
?>

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

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