本篇文章给大家介绍一下php中实现并处理链表的方法。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。
【推荐学习：《php视频教程》】
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
形式：单链表、双链表、跳表（redis 集合数据结构就是跳表实现，时间复杂度o（log n））
跳表了解：https://lotabout.me/2018/skip-list/
php实现对链表的增删改查操作
定义节点类：
<?phpclass node{ public $val; public $next; public function __construct( $val = null, $next = null ) { $this->val = $val; $this->next = $next; }}
链表类：
<?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;$i<$index;$i++){ $prev = $prev->next; }// $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;$i<=$index;$i++){ if( $i==$index ) $prev->val = $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;$i<=$index;$i++){ if( $i==$index ) return $prev; $prev = $prev->next; } } /**删除 * @param $index * @throws exceptionr */ public function delete( $index ){ if( $index > $this->size-1 ) throw new exception('超过链表范围'); $prev = $this->head; for($i=0;$i<=$index;$i++){ if( $i==$index ) $prev->next = $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<1 ){ return false; } while($level--){ echo '-'; } echo "$val\n"; }}
调用操作如下：
<?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->size<=0 ) throw new \exception('超过链表范围'); $val = $this->head->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); }}
测试
<?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());/** 1app\models\node object( [val] => 3 [next] => app\models\node object ( [val] => 6 [next] => app\models\node object ( [val] => 9 [next] => ) ))393->6->9**/
更多编程相关知识，请访问：编程视频！！
以上就是浅谈php中实现并处理链表的方法的详细内容。