Maison  >  Article  >  développement back-end  >  Comment implémenter la suppression et l'insertion de nœuds dans une double liste chaînée en PHP

Comment implémenter la suppression et l'insertion de nœuds dans une double liste chaînée en PHP

墨辰丷
墨辰丷original
2018-05-17 13:38:251497parcourir

Cet article présente principalement la méthode de suppression et d'insertion de nœuds dans une liste doublement chaînée en PHP. Il analyse la définition d'une liste doublement chaînée en PHP et les techniques d'implémentation liées aux opérations de nœuds sous forme d'exemples. reportez-vous à

pour plus de détails :

Aperçu :

Une liste doublement chaînée est également appelée une liste doublement chaînée. list. C'est un type de liste chaînée. Chacun de ses nœuds de données contient deux pointeurs, pointant vers le successeur direct et le prédécesseur direct. Par conséquent, à partir de n’importe quel nœud de la liste doublement chaînée, vous pouvez facilement accéder à ses nœuds prédécesseur et successeur. Généralement, nous construisons une liste chaînée circulaire bidirectionnelle.

Code d'implémentation :

<?php 
class node{
  public $prev;
  public $next;
  public $data;
  public function __construct($data,$prev=null,$next=null){
    $this->data=$data;
    $this->prev=$prev;
    $this->next=$next;
  }
}
class doubleLinkList{
  private $head;
  public function __construct()
  {
    $this->head=new node("head",null,null);
  }
  //插入节点
  public function insertLink($data){
    $p=new node($data,null,null);
    $q=$this->head->next;
    $r=$this->head;
    while($q){
      if($q->data>$data){
        $q->prev->next=$p;
        $p->prev=$q->prev;
        $p->next=$q;
        $q->prev=$p;
      }else{
      $r=$q;$q=$q->next;
      }
    }
    if($q==null){
      $r->next=$p;
      $p->prev=$r;
    }
  }
  //从头输出节点
  public function printFromFront(){
    $p=$this->head->next;
    $string="";
    while($p){
    $string.=$string?",":"";
    $string.=$p->data;
    $p=$p->next;
    }
    echo $string."<br>";
  }
  //从尾输出节点
  public function printFromEnd(){
    $p=$this->head->next;
    $r=$this->head;
    while($p){
    $r=$p;$p=$p->next;
    }
    $string="";
    while($r){
      $string.=$string?",":"";
      $string.=$r->data;
      $r=$r->prev;
    }
    echo $string."<br>";
  }
  public function delLink($data){
    $p=$this->head->next;
    if(!$p)
    return;
    while($p){
      if($p->data==$data)
      {
        $p->next->prev=$p->prev;
        $p->prev->next=$p->next;
        unset($p);
        return;
      }
      else{
        $p=$p->next;
      }
    }
    if($p==null)
    echo "没有值为{$data}的节点";
  }
}
$link=new doubleLinkList();
$link->insertLink(1);
$link->insertLink(2);
$link->insertLink(3);
$link->insertLink(4);
$link->insertLink(5);
$link->delLink(3);
$link->printFromFront();
$link->printFromEnd();
$link->delLink(6);

Résultats en cours :

1,2,4,5
5,4,2,1,head
没有值为6的节点

Recommandations associées :

Opération JS Insertion du DOM Nœud

Comment JS implémente-t-il l'insertion DOM du nœud

JQuery insertion node insertAfter et mobile node insertBefore exemples d'utilisation

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn