線性表的鏈式存儲：用一組任意的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表簡稱線性鏈表。
鏈式存儲線性表的特點：存儲鏈表中結點的一組任意的存儲單元可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。鏈表中結點的邏輯順序和物理順序不一定相同。
PHP實現單鏈表
<?php/***單鏈表的基本操作*1.初始化單鏈表 __construct()*2.清空單鏈表 clearSLL()*3.返回單鏈表長度 getLength()*4. 判斷單鏈表是否為空 getIsEmpty()*5.頭插入法建表 getHeadCreateSLL()*6.尾插入法建表 getTailCreateSLL()*7.返回第$i個元素 getElemForPos()*8.查找單鏈表中是否存在某個值的元素 getElemIsExist()*9.單鏈表的插入操作 getInsertElem()*10.遍歷單鏈表中的所有元素 getAllElem()*11.刪除單鏈中第$i個元素 getDeleteElem()*12.刪除單鏈表中值為$value的前$i($i>=1)個結 點 getDeleteElemForValue()*13.刪除單鏈表所有重復的值 getElemUnique()**/header("content-type:text/html;charset=gb2312");class LNode{public $mElem;public $mNext;public function __construct(){$this->mElem=null;$this->mNext=null;}}class SingleLinkedList{//頭結點數據public $mElem;//下一結點指針public $mNext;//單鏈表長度public static $mLength=0;/***初始化單鏈表**@return void*/public function __construct(){$this->mElem=null;$this->mNext=null;}/***清空單鏈表**@return void*/public function clearSLL(){if(self::$mLength>0){while($this->mNext!=null){$q=$this->mNext->mNext;$this->mNext=null;unset($this->mNext);$this->mNext=$q;}self::$mLength=0;}}/***返回單鏈表長度**@return int*/public static function getLength(){return self::$mLength;}/***判斷單鏈表是否為空**@return bool 為空返回true,不為空返回false*/public function getIsEmpty(){if(self::$mLength==0 && $this->mNext==null){return true;}else{return false;}}/***頭插入法建表**@param array $sarr 建立單鏈表的數據*@return void*/public function getHeadCreateSLL($sarr){$this->clearSLL();if(is_array($sarr)){foreach($sarr as $value){$p=new LNode();$p->mElem=$value;$p->mNext=$this->mNext;$this->mNext=$p;self::$mLength++;}}else{return false;}}/***尾插入法建表**@param array $sarr 建立單鏈表的數據*@return void*/public function getTailCreateSLL($sarr){$this->clearSLL();if(is_array($sarr)){$q=$this;foreach($sarr as $value){$p=new LNode();$p->mElem=$value;$p->mNext=$q->mNext;$q->mNext=$p;$q=$p;self::$mLength++;}}else{return false;}}/***返回第$i個元素**@param int $i 元素位序，從1開始*@return mixed*/public function getElemForPos($i){$i=(int)$i;if($i>self::$mLength || $i < 1){return null;}$j=1;$p=$this->mNext;while($j<$i){$q=$p->mNext;$p=$q;$j++;}return $p;}/***查找單鏈表中是否存在某個值的元素*如果有返回該元素結點，否則返回null**@param mixed $value 查找的值*@return mixed*/public function getElemIsExist($value){$p=$this;while($p->mNext != null && strcmp($p->mElem,$value)!==0){$p=$p->mNext;}if(strcmp($p->mElem,$value)===0){return $p;}else{return null;}}/***查找單鏈表中是否存在某個值的元素*如果有返回該元素位序，否則返回-1**@param mixed $value 查找的值*@return mixed*/public function getElemPosition($value){$p=$this;$j=0;while($p->mNext != null && strcmp($p->mElem,$value)!==0){$j++;$p=$p->mNext;}if(strcmp($p->mElem,$value)===0){return $j;}else{return -1;}}/***單鏈表的插入操作**@param int $i 插入元素的位序，即在什么位置插入新的元素,從1開始*@param mixed $e 插入的新的元素值*@return boolean 插入成功返回true，失敗返回false*/public function getInsertElem($i,$e){if($i>self::$mLength || $i<1){return false;}$j=1;$p=$this;while($p->mNext!=null && $j<$i){$p=$p->mNext;$j++;}$q=new LNode();$q->mElem=$e;$q->mNext=$p->mNext;$p->mNext=$q;self::$mLength++;return true;}/***遍歷單鏈表中的所有元素**@return array 包括單鏈中的所有元素*/public function getAllElem(){$slldata=array();if($this->getIsEmpty()){}else{$p=$this->mNext;while($p->mNext!=null){$slldata[]=$p->mElem;$p=$p->mNext;}$slldata[]=$p->mElem;}return $slldata;}/***刪除單鏈中第$i個元素*@param int $i 元素位序*@return boolean 刪除成功返回true,失敗返回false*/public function getDeleteElem($i){$i=(int)$i;if($i>self::$mLength || $i<1){return false;}$p=$this;$j=1;while($j<$i){$p=$p->mNext;$j++;}$q=$p->mNext;$p->mNext=$q->mNext;$q=null;unset($q);self::$mLength--;}/***刪除單鏈表中值為$value的前$i($i>=1)個結 點**@param mixed 待查找的值*@param $i 刪除的次數，即刪除查找到的前$i個@return void*/public function getDeleteElemForValue($value,$i=1){if($i>1){$this->getDeleteElemForValue($value,$i-1);}$vp=$this->getElemPosition($value);$this->getDeleteElem($vp);}/***刪除單鏈表所有重復的值**@return void*/public function getElemUnique(){if(!$this->getIsEmpty()){$p=$this;while($p->mNext!=null){$q=$p->mNext;$ptr=$p;while($q->mNext!=null){if(strcmp($p->mElem,$q->mElem)===0){$ptr->mNext=$q->mNext;$q->mNext=null;unset($q->mNext);$q=$ptr->mNext;self::$mLength--;}else{$ptr=$q;$q=$q->mNext;}}if(strcmp($p->mElem,$q->mElem)===0){$ptr->mNext=null;self::$mLength--;}$p=$p->mNext;}}}}?> ?
)
)
