PHP 在双向链表中的给定位置插入新节点

 PHP 数据结构

在此方法中，将一个新元素插入到双向链表中的指定位置。例如 - 如果给定列表为 10->20->30 并且在位置 2 添加了新元素 100，则列表将变为 10->100->20->30。

首先，具有给定元素的新节点被建造。如果插入位置为1，则将新节点设为头节点。否则，遍历插入位置之前的节点并检查它是否为空。如果为 null，则指定的位置不存在。在其他情况下，请更新链接。下图描述了插入节点不是头节点时的流程。

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

public function push_at($newElement, $position) {     
  
  //1.将节点分配给新元素
  $newNode = new Node(); 
  $newNode->data = $newElement;
  $newNode->next = null;
  $newNode->prev = null;

  //2。检查位置是否为 > 0
  if($position < 1) {
    echo "\nposition should be >= 1.";
  } else if ($position == 1) {
    
    //3。如果位置为1，则将新节点作为头
    $newNode->next = $this->head;
    $this->head->prev = $newNode;
    $this->head = $newNode;
  } else {
    
    //4。否则，创建一个临时节点并遍历到
    //该位置之前的节点
    $temp = new Node();
    $temp = $this->head;
    for($i = 1; $i < $position-1; $i++) {
      if($temp != null) {
        $temp = $temp->next;
      }
    }
 
    //5。如果前一个节点不为空，则调整
    // 链接
    if($temp != null) {
      $newNode->next = $temp->next;
      $newNode->prev = $temp;
      $temp->next = $newNode; 
      if($newNode->next != null)
        $newNode->next->prev = $newNode; 
    } else {
      
      //6。当前一个节点为空时
      echo "\nThe previous node is 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;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->prev = $temp;
    }    
  }

  //在给定位置插入新元素
  public function push_at($newElement, $position) {     
    $newNode = new Node(); 
    $newNode->data = $newElement;
    $newNode->next = null;
    $newNode->prev = null;
    if($position < 1) {
      echo "\nposition should be >= 1.";
    } else if ($position == 1) {
      $newNode->next = $this->head;
      $this->head->prev = $newNode;
      $this->head = $newNode;
    } else {
      $temp = new Node();
      $temp = $this->head;
      for($i = 1; $i < $position-1; $i++) {
        if($temp != null) {
          $temp = $temp->next;
        }
      }
      if($temp != null) {
        $newNode->next = $temp->next;
        $newNode->prev = $temp;
        $temp->next = $newNode; 
        if($newNode->next != null)
          $newNode->next->prev = $newNode; 
      } else {
        echo "\nThe previous node is null.";
      }       
    }
  }  

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

//在位置2插入一个元素
$MyList->push_at(100, 2);
$MyList->PrintList();

//在位置1插入一个元素
$MyList->push_at(200, 1);
$MyList->PrintList();  
?> 

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

The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30