Detaillierte Erläuterung der Grundlagen der doppelt verknüpften PHP-Liste

In diesem Artikel wird hauptsächlich die Definition und Verwendung doppelt verknüpfter Listen in PHP vorgestellt. Dabei geht es um die Verwendung der Klasse doppelt verknüpfter Listen durch PHP, um die Definition, das Lesen, das Löschen, das Einfügen und andere verwandte Vorgänge zu kapseln. Freunde, die dies benötigen, können sich darauf beziehen Ich hoffe, es kann Ihnen helfen.

Da ein Datensatz mehrmals verschoben werden muss, wird eine doppelt verknüpfte Liste geschrieben. Aber ich bin wirklich nicht mit PHP vertraut. Obwohl es kein Problem ist, verschiedene Methoden zu testen, weiß ich einfach nicht, worauf ich bei diesen Hinweisen achten soll, und ich werde sie zur Aufklärung aller veröffentlichen . Die Effizienz wurde nicht getestet....Tut mir leid für Ihr Verständnis~

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

Betriebsergebnisse:

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"

Verwandt empfohlen:

So definieren und verwenden Sie eine doppelt verknüpfte JavaScript-Liste

Detailliertes Beispiel einer PHP-Mitgliedsrankingfunktion basierend auf einer doppelt verknüpften Liste und Sortiervorgang

Ein Beispielcode für die Implementierung einer doppelt verknüpften Liste in PHP

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Grundlagen der doppelt verknüpften PHP-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!