Explication détaillée des bases de la liste doublement chaînée PHP

Cet article présente principalement la définition et l'utilisation de la liste doublement chaînée PHP, impliquant l'utilisation par PHP d'une classe de liste doublement chaînée pour encapsuler la définition, la lecture, la suppression, l'insertion et d'autres compétences opérationnelles connexes. Les amis qui en ont besoin peuvent s'y référer. ça. J'espère que cela pourra vous aider.

Comme un ensemble de données doit être déplacé plusieurs fois, une liste doublement chaînée est écrite. Mais je ne suis vraiment pas familier avec PHP. Bien qu'il n'y ait aucun problème à tester diverses méthodes, je ne sais tout simplement pas à quoi faire attention dans ces pointeurs et je ne suis pas encore au niveau profond du langage PHP. . L'efficacité n'a pas été testée....Désolé pour votre compréhension~

<?php
/**
 * **双向链表
 * @author zhiyuan12@
 */
/**
 * 链表元素结点类
 */
class Node_Element {
  public $pre = NULL; // 前驱
  public $next = NULL; // 后继
  public $key = NULL; // 元素键值
  public $data = NULL; // 结点值
  function __Construct($key, $data) {
    $this->key = $key;
    $this->data = $data;
  }
}
/**
 * 双向链表类
 */
class DoubleLinkedList {
  private $head; // 头指针
  private $tail; // 尾指针
  private $current; // 当前指针
  private $len; // 链表长度
  function __Construct() {
    $this->head = self::_getNode ( null, null );
    $this->curelement = $this->head;
    $this->tail = $this->head;
    $len = 0;
  }
  /**
   * @ desc: 读取链表全部结点
   */
  public function readAll() {
    $tmp = $this->head;
    while ( $tmp->next !== null ) {
      $tmp = $tmp->next;
      var_dump ( $tmp->key, $tmp->data );
    }
  }
  public function move($pos1, $pos2) {
    $pos1Node = $this->findPosition ( $pos1 );
    $pos2Node = $this->findPosition ( $pos2 );
    if ($pos1Node !== null && $pos2Node !== null) {
      $tmpKey = $pos1Node->key;
      $tmpData = $pos1Node->data;
      $pos1Node->key = $pos2Node->key;
      $pos1Node->data = $pos2Node->data;
      $pos2Node->key = $tmpKey;
      $pos2Node->data = $tmpData;
      return true;
    }
    return false;
  }
  /**
   * @ desc: 在指定关键词删除结点
   *
   * @param : $key
   *     指定位置的链表元素key
   */
  public function delete($key) {
    $pos = $this->find ( $key );
    if ($pos !== null) {
      $tmp = $pos;
      $last = null;
      $first = true;
      while ( $tmp->next !== null && $tmp->next->key === $key ) {
        $tmp = $tmp->next;
        if (! $first) {
          $this->delNode ( $last );
        } else {
          $first = false;
        }
        $last = $tmp;
      }
      if ($tmp->next !== null) {
        $pos->pre->next = $tmp->next;
        $tmp->next->pre = $pos->pre;
      } else {
        $pos->pre->next = null;
      }
      $this->delNode ( $pos );
      $this->delNode ( $tmp );
    }
  }
  /**
   * @ desc: 在指定位置删除结点
   *
   * @param : $key
   *     指定位置的链表元素key
   */
  public function deletePosition($pos) {
    $tmp = $this->findPosition ( $pos );
    if ($tmp === null) {
      return true;
    }
    if ($tmp === $this->getTail ()) {
      $tmp->pre->next = null;
      $this->delNode ( $tmp );
      return true;
    }
    $tmp->pre->next = $tmp->next;
    $tmp->next->pre = $tmp->pre;
    $this->delNode ( $tmp );
  }
  /**
   * @ desc: 在指定键值之前插入结点
   *
   * @param : $key
   *     //指定位置的链表元素key
   * @param : $data
   *     //要插入的链表元素数据
   * @param : $flag
   *     //是否顺序查找位置进行插入
   */
  public function insert($key, $data, $flag = true) {
    $newNode = self::_getNode ( $key, $data );
    $tmp = $this->find ( $key, $flag );
    if ($tmp !== null) {
      $newNode->pre = $tmp->pre;
      $newNode->next = $tmp;
      $tmp->pre = $newNode;
      $newNode->pre->next = $newNode;
    } else {
      $newNode->pre = $this->tail;
      $this->tail->next = $newNode;
      $this->tail = $newNode;
    }
    $this->len ++;
  }
  /**
   * @ desc: 在指定位置之前插入结点
   *
   * @param : $pos
   *     指定插入链表的位置
   * @param : $key
   *     指定位置的链表元素key
   * @param : $data
   *     要插入的链表元素数据
   */
  public function insertPosition($pos, $key, $data) {
    $newNode = self::_getNode ( $key, $data );
    $tmp = $this->findPosition ( $pos );
    if ($tmp !== null) {
      $newNode->pre = $tmp->pre;
      $newNode->next = $tmp;
      $tmp->pre = $newNode;
      $newNode->pre->next = $newNode;
    } else {
      $newNode->pre = $this->tail;
      $this->tail->next = $newNode;
      $this->tail = $newNode;
    }
    $this->len ++;
    return true;
  }
  /**
   * @ desc: 根据key值查询指定位置数据
   *
   * @param : $key
   *     //指定位置的链表元素key
   * @param : $flag
   *     //是否顺序查找
   */
  public function find($key, $flag = true) {
    if ($flag) {
      $tmp = $this->head;
      while ( $tmp->next !== null ) {
        $tmp = $tmp->next;
        if ($tmp->key === $key) {
          return $tmp;
        }
      }
    } else {
      $tmp = $this->getTail ();
      while ( $tmp->pre !== null ) {
        if ($tmp->key === $key) {
          return $tmp;
        }
        $tmp = $tmp->pre;
      }
    }
    return null;
  }
  /**
   * @ desc: 根据位置查询指定位置数据
   *
   * @param : $pos
   *     //指定位置的链表元素key
   */
  public function findPosition($pos) {
    if ($pos <= 0 || $pos > $this->len)
      return null;
    if ($pos < ($this->len / 2 + 1)) {
      $tmp = $this->head;
      $count = 0;
      while ( $tmp->next !== null ) {
        $tmp = $tmp->next;
        $count ++;
        if ($count === $pos) {
          return $tmp;
        }
      }
    } else {
      $tmp = $this->tail;
      $pos = $this->len - $pos + 1;
      $count = 1;
      while ( $tmp->pre !== null ) {
        if ($count === $pos) {
          return $tmp;
        }
        $tmp = $tmp->pre;
        $count ++;
      }
    }
    return null;
  }
  /**
   * @ desc: 返回链表头节点
   */
  public function getHead() {
    return $this->head->next;
  }
  /**
   * @ desc: 返回链表尾节点
   */
  public function getTail() {
    return $this->tail;
  }
  /**
   * @ desc: 查询链表节点个数
   */
  public function getLength() {
    return $this->len;
  }
  private static function _getNode($key, $data) {
    $newNode = new Node_Element ( $key, $data );
    if ($newNode === null) {
      echo "new node fail!";
    }
    return $newNode;
  }
  private function delNode($node) {
    unset ( $node );
    $this->len --;
  }
}
$myList = new DoubleLinkedList ();
$myList->insert ( 1, "test1" );
$myList->insert ( 2, "test2" );
$myList->insert ( "2b", "test2-b" );
$myList->insert ( 2, "test2-c" );
$myList->insert ( 3, "test3" );
$myList->insertPosition ( 5, "t", "testt" );
$myList->readAll ();
echo "+++";
$myList->deletePosition(0);
$myList->readAll ();
echo "..." . $myList->getLength ();
var_dump ( $myList->findPosition ( 3 )->data );
?>

Résultats de fonctionnement :

int(1)
string(5) "test1"
int(2)
string(7) "test2-c"
int(2)
string(5) "test2"
string(2) "2b"
string(7) "test2-b"
string(1) "t"
string(5) "testt"
int(3)
string(5) "test3"
+++int(1)
string(5) "test1"
int(2)
string(7) "test2-c"
int(2)
string(5) "test2"
string(2) "2b"
string(7) "test2-b"
string(1) "t"
string(5) "testt"
int(3)
string(5) "test3"
...6string(5) "test2"

Connexe recommandé :

Comment définir et utiliser une liste doublement chaînée JavaScript

Exemple détaillé de la fonction de classement des membres PHP basée sur une liste doublement chaînée et opération de tri

Un exemple de code pour implémenter une liste doublement chaînée en PHP

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!