怎么在PHP中定义一个双向链表

这期内容当中小编将会给大家带来有关怎么在PHP中定义一个双向链表，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

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

运行结果：

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"

上述就是小编为大家分享的怎么在PHP中定义一个双向链表了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。