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

 PHP 数据结构

在此方法中，循环双向链表的第一个节点被删除。例如 - 如果给定列表为 10->20->30->40，并且删除第一个节点，则列表将变为 20->30->40。

删除循环双向链表的第一个节点非常简单简单的。如果列表中包含一个节点，则删除该节点。如果列表包含多个节点，则创建两个节点 - temp 和firstNode 都指向头。使用临时节点，遍历到列表的最后一个节点。将head的next作为头节点并更新所有链接。最后删除第一个节点。

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

public function pop_front() {
  if($this->head != null) {
    
    //1.链表包含一个节点，删除
    //使头部为空
    if($this->head->next == $this->head) {
      $this->head = null;
    } else {
      
      //2。如果列表包含多个节点，
      // 创建两个节点 - temp 和firstNode，两者都是
      //指向头节点
      $temp = $this->head;
      $firstNode = $this->head;
      
      //3。使用临时节点，遍历到最后一个节点
      while($temp->next != $this->head) {
        $temp = $temp->next;
      }
      
      //4。将头部设为下一个头部，然后
      //更新链接
      $this->head = $this->head->next;
      $this->head->prev = $temp;
      $temp->next = $this->head; 
      $firstNode = null; 
    }
  }
}

下面是一个完整的程序，它使用了上面讨论的删除循环双向链表的第一个节点的概念。

<?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;
    }    
  }

  //删除链表第一个节点
  public function pop_front() {
    if($this->head != null) {
      if($this->head->next == $this->head) {
        $this->head = null;
      } else {
        $temp = $this->head;
        $firstNode = $this->head;
        while($temp->next != $this->head) {
          $temp = $temp->next;
        }
        $this->head = $this->head->next;
        $this->head->prev = $temp;
        $temp->next = $this->head; 
        $firstNode = null; 
      }
    }
  }

  //显示列表内容
  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(40);
$MyList->PrintList();

//删除第一个节点
$MyList->pop_front();
$MyList->PrintList(); 
?>

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

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