好得很程序员自学网

<tfoot draggable='sEl'></tfoot>

详解PHP怎么实现链表
本篇文章给大家介绍PHP实现链表 。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。

推荐学习：《PHP视频教程》

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

形式：单链表、双链表、跳表（redis 集合数据结构就是跳表实现，时间复杂度O（log N））

跳表了解：https://lotabout.me/2018/skip-list/

php实现对链表的增删改查操作

定义节点类：

<?php
class 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());
/**   
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怎么实现链表的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did51807

  阅读：31次

上一篇： php怎么跳转到不同页面

下一篇：php怎么将字符串转为小写

相关资讯