浅谈PHP中实现并处理链表的方法

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

链表

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

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

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

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

定义节点类：

val  = $val;
 $this->next = $next;
    }


}

链表类：

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

    
    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++;
    }

    
    public function addLast( $value ){

 $this->add($this->size,$value);

    }


    
    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;
 }

    }

    
    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;
 }
    }


    
    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--;
    }

    
    public function iscontain( $value ){
 $prev = $this->head->next;
 while( $prev ){

     if( $prev->val==$value ){
  return true;
     }
     $prev = $prev->next;
 }

 return false;
    }

    
    public function tostring(){

 $prev = $this->head->next;

 $r = [];
 while( $prev ){
     $r[] = $prev->val;
     $prev = $prev->next;
 }
 return implode('->',$r);

    }
    
     
      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;
 }
    }
      }
      

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;
    }

 
 public function showDeeep( $level=1,$val ){
      if( $level<1 ){
   return false;
      }
    
      while($level--){
   echo '-';
      }
      echo "$valn";
 }

}

调用操作如下：

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)

利用链表实现栈

addFirst($value);
    }

    
    public function pop(){
 $r = $this->head->next->val;
 $this->delete(0);
 return $r;
    }
}

push(1);
 $stack->push(3);
 $stack->push(6);
 $stack->push(9);

 print_r($stack->pop());
 print_r($stack->head);

链表实现队列

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++;
    }

    
    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;
    }

    
    public function toString(){
 $r = [];
 while( $this->head ){
     $r[] = $this->head->val;
     $this->head = $this->head->next;
 }
 return implode('->',$r);
    }
}

测试

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

更多编程相关知识，请访问：编程视频！！

以上就是浅谈PHP中实现并处理链表的方法的详细内容，更多请关注考高分网其它相关文章！