PHP doubly linked list definition and usage examples php skills

This article mainly introduces the definition and usage of PHP doubly linked list, involving PHP's use of doubly linked list classes to encapsulate doubly linked list definition, reading, deletion, insertion and other related operation skills. Friends in need can refer to the following

This article explains the definition and usage of doubly linked lists in PHP with examples. Share it with everyone for your reference, the details are as follows:

Since a set of data needs to be moved multiple times, a doubly linked list is written. But I am really not familiar with PHP. Although there is no problem in testing various methods, I just don’t know what to pay attention to about these pointers and unset in the deeper layers of PHP language. I will post it for everyone’s education. The efficiency has not been tested....Sorry for your understanding~

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

Running results:

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"

Articles you may be interested in:

PHP uses foreach to magically convert arrays (explanation with examples)php examples

Solution to the error when accessing array elements in php double quotes php tips

php How to delete a value element in a one-dimensional array php tips

The above is the detailed content of PHP doubly linked list definition and usage examples php skills. For more information, please follow other related articles on the PHP Chinese website!