这篇文章主要介绍了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是一个嵌套的缩写名称，是英文超级文本预处理语言，它的语法混合了C、Java、Perl以及php自创新的语法，主要用来做网站开发，许多小型网站都用php开发，因为php是开源的，从而使得php经久不衰。
感谢你能够认真阅读完这篇文章，希望小编分享的“PHP实现链表的方法”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网行业资讯频道，更多相关知识等着你来学习!
