推荐学习：《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怎么实现链表的知识。速戳>>知识兔学习精品课！