PHP中如何实现并处理链表

这篇“PHP中如何实现并处理链表”除了程序员外大部分人都不太理解，今天小编为了让大家更加理解“php中如何实现并处理链表”，给大家总结了以下内容，具有一定借鉴价值，内容详细步骤清晰，细节处理妥当，希望大家通过这篇文章有所收获，下面让我们一起来看看具体内容吧。

php有什么用

php是一个嵌套的缩写名称，是英文超级文本预处理语言，它的语法混合了C、Java、Perl以及php自创新的语法，主要用来做网站开发，许多小型网站都用php开发，因为php是开源的，从而使得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;    }}

链表类：

<?phpclass 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);    }        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 "$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)

利用链表实现栈

<?phpclass LinklistStack extends Linklist{        public function push( $value ){        $this->addFirst($value);    }        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);

链表实现队列

<?phpclass LinkListQueue extends Linklist{    public $tail;    //尾节点        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++;    }        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);    }}

测试

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

感谢你的阅读，希望你对“PHP中如何实现并处理链表”这一关键问题有了一定的理解，具体使用情况还需要大家自己动手实验使用过才能领会，快去试试吧，如果想阅读更多相关知识点的文章，欢迎关注编程网PHP编程频道！