本篇文章給大家介紹PHP實(shí)現(xiàn)鏈表 。有一定的參考價(jià)值，有需要的朋友可以參考一下，希望對(duì)大家有所幫助。

推薦學(xué)習(xí)：《PHP視頻教程》

鏈表

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。

形式：?jiǎn)捂湵怼㈦p鏈表、跳表（redis 集合數(shù)據(jù)結(jié)構(gòu)就是跳表實(shí)現(xiàn)，時(shí)間復(fù)雜度O（log N））

跳表了解：https://lotabout.me/2018/skip-list/

php實(shí)現(xiàn)對(duì)鏈表的增刪改查操作

定義節(jié)點(diǎn)類(lèi)：

<?php class Node {     public $val;     public $next;        public function __construct( $val = null, $next = null )     {         $this->val  = $val;         $this->next = $next;     }   }

鏈表類(lèi)：

<?php /**鏈表  * Class Linklist  * @package appmodels  */ class Linklist {     public $head;           //頭節(jié)點(diǎn)(默認(rèn)一個(gè)虛擬頭節(jié)點(diǎn))     public $size;           //長(zhǎng)度      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;          //簡(jiǎn)化 //        $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('超過(guò)鏈表范圍');  //        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('超過(guò)鏈表范圍');          $prev = $this->head->next;         for($i=0;$i<=$index;$i++){             if( $i==$index )                 $prev->val = $value;             $prev = $prev->next;         }      }      /**      * 查詢(xún)      * @param $index      * @return null      * @throws Exception      */     public function select($index){         if( $index > $this->size-1 )             throw new Exception('超過(guò)鏈表范圍');          $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('超過(guò)鏈表范圍');          $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;     }      /**轉(zhuǎn)換為字符串      * @return string      */     public function tostring(){          $prev = $this->head->next;          $r = [];         while( $prev ){             $r[] = $prev->val;             $prev = $prev->next;         }         return implode('->',$r);      }           /**       * 刪除指定的節(jié)點(diǎn)值       * @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;                }            }       }               /**         * 通過(guò)遞歸方式刪除指定的節(jié)點(diǎn)值         * @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;            }                 /**         * 顯示深度         * 幫助理解遞歸執(zhí)行過(guò)程，回調(diào)函數(shù)執(zhí)行層序遵循系統(tǒng)棧          * @param int $level 深度層級(jí)         * @param $val         * @return bool         */         public function showDeeep( $level=1,$val ){              if( $level<1 ){                  return false;              }                   while($level--){                  echo '-';              }              echo "$valn";         }  }

調(diào)用操作如下：

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

分析下鏈表操作的時(shí)間復(fù)雜度：

增： O(n)  只對(duì)鏈表頭操作：O(1)  刪： O(n)  只對(duì)鏈表頭操作：O(1)  改：O(n)  查：O(n)   只對(duì)鏈表頭操作：O(1)

利用鏈表實(shí)現(xiàn)棧

<?php /**  * 鏈表實(shí)現(xiàn)棧  * Class LinklistStack  * @package appmodels  */ 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);

鏈表實(shí)現(xiàn)隊(duì)列

<?php  /**  * 鏈表實(shí)現(xiàn)隊(duì)列  * Class LinkListQueue  * @package appmodels  */ class LinkListQueue extends Linklist {     public $tail;    //尾節(jié)點(diǎn)      /**      * 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('超過(guò)鏈表范圍');         $val = $this->head->val;         $this->head = $this->head->next;          $this->size--;         return $val;     }      /**      * 查看隊(duì)首      */     public function checkHead(){         return $this->head->val;     }      /**      * 查看隊(duì)尾      */     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);     } }

測(cè)試

<?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 appmodelsNode Object (     [val] => 3     [next] => appmodelsNode Object         (             [val] => 6             [next] => appmodelsNode Object                 (                     [val] => 9                     [next] =>                  )          )  ) 3 9 3->6->9 **/