この記事では、PHP でのリンク リストの実装について紹介します。一定の参考値があるので、困っている友達が参考になれば幸いです。
推奨学習: 「PHP ビデオ チュートリアル 」
リンク リストは、コンピュータ上の非連続かつ非順次のストレージ構造です。物理ストレージ ユニット データ要素の論理的順序は、リンク リスト内のポインタのリンク順序によって実現されます。リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。
形式: シングル リンク リスト、ダブル リンク リスト、スキップ リスト (Redis コレクションのデータ構造はスキップ リスト、時間計算量 O (log N) によって実現されます)
スキップ リストについて学習します: https ://lotabout .me/2018/skip-list/
ノード クラスを定義します:
<?php class Node { public $val; public $next; public function __construct( $val = null, $next = null ) { $this->val = $val; $this->next = $next; } }
Linked list クラス:
<?php /**链表 * Class Linklist * @package app\models */ class Linklist { public $head; //头节点(默认一个虚拟头节点) public $size; //长度 public function __construct() { $this->head = new Node(); $this->size = 0; } //头插法 public function addFirst( $value ){ // $node = new Node($value); // $node->next = $this->head; // $this->head = $node; //简化 // $this->head = new Node( $value, $this->head ); // $this->size++; $this->add(0,$value); } /**指定索引位置插入 * @param $index * @param $value * @throws Exception */ public function add( $index, $value ){ if( $index > $this->size ) throw new Exception('超过链表范围'); // if( $index==0 ){ // $this->addFirst($value); // }else{ $prev = $this->head; for($i=0;$inext; } // $node = new Node($value); // $node->next = $prev->next; // $prev->next = $node; $prev->next = new Node($value,$prev->next); // } $this->size++; } /**尾插法 * @param $value */ public function addLast( $value ){ $this->add($this->size,$value); } /*** * 编辑 * @param $index * @param $value * @throws Exception */ public function edit( $index, $value ){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head->next; for($i=0;$ival = $value; $prev = $prev->next; } } /** * 查询 * @param $index * @return null * @throws Exception */ public function select($index){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head->next; for($i=0;$inext; } } /**删除 * @param $index * @throws Exceptionr */ public function delete( $index ){ if( $index > $this->size-1 ) throw new Exception('超过链表范围'); $prev = $this->head; for($i=0;$inext = $prev->next->next; $prev = $prev->next; } $this->size--; } /**检索值是否存在 * @param $value * @return bool */ public function iscontain( $value ){ $prev = $this->head->next; while( $prev ){ if( $prev->val==$value ){ return true; } $prev = $prev->next; } return false; } /**转换为字符串 * @return string */ public function tostring(){ $prev = $this->head->next; $r = []; while( $prev ){ $r[] = $prev->val; $prev = $prev->next; } return implode('->',$r); } /** * 删除指定的节点值 * @param $value */ public function removeFileds( $value ){ $prev = $this->head; while( $prev->next ){ if( $prev->val == $value ){ $prev->val = $prev->next->val; $prev->next = $prev->next->next; }else{ $prev = $prev->next; } } } /** * 通过递归方式删除指定的节点值 * @param $value */ public function removeFiledsByRecursion( $value ){ $this->head = $this->removeByRecursion( $this->head ,$value); return $this->head; } public function removeByRecursion( $node , $value, $level=0 ){ if( $node->next == null ){ $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } $this->showDeeep($level,$node->val); $node->next = $this->removeByRecursion( $node->next,$value,++$level ); $this->showDeeep($level,$node->val); return $node->val == $value ? $node->next:$node; } /** * 显示深度 * 帮助理解递归执行过程,回调函数执行层序遵循系统栈 * @param int $level 深度层级 * @param $val * @return bool */ public function showDeeep( $level=1,$val ){ if( $level<p>呼び出し操作は次のとおりです: </p><pre class="brush:php;toolbar:false"><?php $node = new Linklist(); $node->addFirst(1); $node->add(1,7); $node->add(2,10); $node->edit(1,8); var_dump($node->select(1)) ; $node->delete(1); $node->addLast(99); var_dump($node->iscontain(2)); var_export($node); var_export($node->tostring());
リンク リスト操作の時間計算量を分析します:
增: O(n) 只对链表头操作:O(1) 删: O(n) 只对链表头操作:O(1) 改:O(n) 查:O(n) 只对链表头操作:O(1)
<?php /** * 链表实现栈 * Class LinklistStack * @package app\models */ class LinklistStack extends Linklist { /** * @param $value */ public function push( $value ){ $this->addFirst($value); } /** * @return mixed */ public function pop(){ $r = $this->head->next->val; $this->delete(0); return $r; } }
<?php $stack = new LinklistStack(); $stack->push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head);
<?php /** * 链表实现队列 * Class LinkListQueue * @package app\models */ class LinkListQueue extends Linklist { public $tail; //尾节点 /** * push * @param $value */ public function push( $value ){ if( $this->head->val==null ){ $this->tail = new Node( $value ); $this->head = $this->tail; }else{ $this->tail->next = new Node( $value ); $this->tail = $this->tail->next; } $this->size++; } /** * pop * @return null * @throws \Exception */ public function pop(){ if( $this->sizehead->val; $this->head = $this->head->next; $this->size--; return $val; } /** * 查看队首 */ public function checkHead(){ return $this->head->val; } /** * 查看队尾 */ public function checkEnd(){ return $this->tail->val; } /** * toString */ public function toString(){ $r = []; while( $this->head ){ $r[] = $this->head->val; $this->head = $this->head->next; } return implode('->',$r); } }
Test
<?php $stack = new LinkListQueue(); $stack->push(1); $stack->push(3); $stack->push(6); $stack->push(9); print_r($stack->pop()); print_r($stack->head); print_r($stack->checkHead()); print_r($stack->checkEnd()); print_r($stack->toString()); /** 1 app\models\Node Object ( [val] => 3 [next] => app\models\Node Object ( [val] => 6 [next] => app\models\Node Object ( [val] => 9 [next] => ) ) ) 3 9 3->6->9 **/
以上がPHPでリンクリストを実装する方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。