PHP 在循环双向链表的末尾插入一个新节点

 PHP 数据结构

在此方法中，一个新节点被插入到循环双向链表的末尾。例如 - 如果给定的 List 是 10->20->30 并且在末尾添加了新元素 100，则 List 变为 10->20->30->100。

在循环双向链表的末尾插入新节点非常容易。首先，创建一个具有给定元素的新节点。然后通过将最后一个节点和头节点链接到新节点来将其添加到列表的末尾。

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

public function push_back($newElement) {
  
  //1.分配节点
  $newNode = new Node();
  
  //2。分配数据元素
  $newNode->data = $newElement;
  
  //3。将 null 分配给下一个和上一个
  //新节点
  $newNode->next = null; 
  $newNode->prev = null;

  //4。检查列表是否为空，
  //如果为空则将新节点作为头
  if($this->head == null) {
    $this->head = $newNode;
    $newNode->next = $this->head;
    $newNode->prev = $this->head;
  } else {
    
    //5。否则，遍历到最后一个节点
    $temp = new Node();
    $temp = $this->head;
    while($temp->next !== $this->head) {
      $temp = $temp->next;
    }
    
    //6。调整链接
    $temp->next = $newNode;
    $newNode->next = $this->head;
    $newNode->prev = $temp;
    $this->head->prev = $newNode;
  }    
}

下面是一个完整的程序，使用上面讨论的概念在循环双向链接的末尾插入新节点

<?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 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->PrintList();
?>

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

The list contains: 10 20 30