PHP 数据结构

在此方法中,删除链表中指定位置的节点。例如 - 如果给定的列表是 10->20->30 并且删除了第 2 个nd 节点,则链接列表将变为 10->20。

首先,指定的位置必须是大于等于1。如果指定位置为1且head不为null,则将下一个head作为head,并删除前一个head。否则,遍历到指定位置之前的节点。如果指定节点和指定节点的前一个节点不为空,则调整链接。在其他情况下,指定的节点将已经为空。下图描述了如果删除节点不是头节点的情况。

PHP - 删除链表中给定位置的节点

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

public function pop_at($position) {     
  
  //1.检查位置是否为 > 0
  if($position < 1) {
    echo "\nposition should be >= 1.";
  } else if ($position == 1 && $this->head != null) {
    
    //2。如果位置为 1 并且 head 不为空,则使
    // 下一个头作为头并删除上一个头
    $nodeToDelete = $this->head;
    $this->head = $this->head->next;
    $nodeToDelete = null;
  } else {
    
    //3。否则,创建一个临时节点并遍历到
    //该位置之前的节点
    $temp = new Node();
    $temp = $this->head;
    for($i = 1; $i < $position-1; $i++) {
      if($temp != null) {
        $temp = $temp->next;
      }
    }
 
    //4。如果前一个节点和下一个节点
    //不为空,调整链接
    if($temp != null && $temp->next != null) {
      $nodeToDelete = $temp->next;
      $temp->next = $temp->next->next;
      $nodeToDelete = null;  
    } else {
      
      //5。否则给定的节点将为空。
      echo "\nThe node is already null.";
    }       
  }
} 

下面是一个完整的程序,它使用上面讨论的概念来删除链表中给定位置的节点.

<?php
//节点结构
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node(); 
    $newNode->data = $newElement;
    $newNode->next = 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;
    }    
  }

  //删除给定位置的元素
  public function pop_at($position) {     
    if($position < 1) {
      echo "\nposition should be >= 1.";
    } else if ($position == 1 && $this->head != null) {
      $nodeToDelete = $this->head;
      $this->head = $this->head->next;
      $nodeToDelete = null;
    } else {
      $temp = new Node();
      $temp = $this->head;
      for($i = 1; $i < $position-1; $i++) {
        if($temp != null) {
          $temp = $temp->next;
        }
      }
      if($temp != null && $temp->next != null) {
        $nodeToDelete = $temp->next;
        $temp->next = $temp->next->next;
        $nodeToDelete = null; 
      } else {
        echo "\nThe node is already 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->pop_at(2);
$MyList->PrintList();

//删除位置1的元素
$MyList->pop_at(1);
$MyList->PrintList();    
?> 

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

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