PHP 数据结构

删除循环双向链表的所有节点需要遍历链表,将每个节点一一删除。它需要创建一个指向头的下一个节点的当前节点。删除当前节点并使用临时节点移动到下一个节点。重复这个过程,直到当前节点成为头节点。最后,删除头部。

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

public function deleteAllNodes() {
  if($this->head != null) {
    
    //1.如果 head 不为空,则创建一个临时节点
    //当前节点指向头的下一个
    $temp = new Node();
    $current = new Node();
    $current = $this->head->next;
    
    //2。如果当前节点不等于head,则删除
    // 当前节点并使用 temp 将当前节点移动到下一个节点,
    //重复该过程,直到电流到达头部
    while($current != $this->head) {
      $temp = $current->next;
      $current = null;
      $current = $temp;
    }

    //3。删除头部
    $this->head = null;
  }
  echo "All nodes are deleted successfully.\n";  
}

下面是一个完整的程序,它使用上面讨论的删除循环双向链表的所有节点的概念,这使得列表为空,大小为零。

<?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 deleteAllNodes() {
    if($this->head != null) {
      $temp = new Node();
      $current = new Node();
      $current = $this->head->next;
      while($current != $this->head) {
        $temp = $current->next;
        $current = null;
        $current = $temp;
      }
      $this->head = null;
    }
    echo "All nodes are deleted successfully.\n";  
  }

  //显示列表内容
  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->deleteAllNodes();

//显示列表内容。
$MyList->PrintList();
?>

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

The list contains: 10 20 30 40 
All nodes are deleted successfully.
The list is empty.