Detailed explanation of how to implement linked list in PHP

This article will introduce you to the implementation of linked list in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

Recommended study: "PHP Video Tutorial"

Linked list

A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is achieved through the link order of pointers in the linked list. A linked list consists of a series of nodes (each element in the linked list is called a node), and nodes can be dynamically generated at runtime.

Forms: single linked list, double linked list, skip list (the redis collection data structure is realized by skip list, time complexity O (log N))

Learn about skip list: https://lotabout .me/2018/skip-list/

php implements addition, deletion, modification and query operations on linked lists

Define node class:

<?php class Node
{
    public $val;
    public $next;



    public function __construct( $val = null, $next = null )
    {
        $this->val  = $val;
        $this->next = $next;
    }


}

Linked list class:

<?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>The calling operation is as follows: </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());

Analyze the time complexity of the linked list operation:

增： O(n)  只对链表头操作：O(1)

删： O(n)  只对链表头操作：O(1)

改：O(n)

查：O(n)   只对链表头操作：O(1)

Use the linked list to implement the stack

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

The linked list implements the queue

<?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
**/

The above is the detailed content of Detailed explanation of how to implement linked list in PHP. For more information, please follow other related articles on the PHP Chinese website!