Detaillierte Erklärung zur Implementierung einer verknüpften Liste in PHP

Dieser Artikel führt Sie in die Implementierung verknüpfter Listen in PHP ein. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird für alle hilfreich sein.

Empfohlenes Lernen: „PHP-Video-Tutorial“

Verknüpfte Liste

Eine verknüpfte Liste ist eine nicht kontinuierliche, nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge von Datenelementen wird durch die Zeigerverknüpfung realisiert Reihenfolge in der verknüpften Liste. Eine verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet), und Knoten können zur Laufzeit dynamisch generiert werden.

Formulare: einfach verknüpfte Liste, doppelt verknüpfte Liste, Sprungliste (Redis-Sammlungsdatenstruktur wird durch Sprungliste realisiert, zeitliche Komplexität O (log N))

Erfahren Sie mehr über Sprunglisten: https://lotabout.me/2018/ Skip-List /

php implementiert die Vorgänge zum Hinzufügen, Löschen, Ändern und Überprüfen der verknüpften Liste.

Knotenklasse definieren:

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



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


}

Verknüpfte Listenklasse:

<?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>Die aufrufende Operation lautet wie folgt:</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());

Analysieren Sie die Zeit Komplexität der verknüpften Listenoperation:

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

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

改：O(n)

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

Verwenden Sie die verknüpfte Liste, um den Stapel zu implementieren

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

Verknüpfte Listenimplementierungswarteschlange

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

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung zur Implementierung einer verknüpften Liste in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!