我们今天为大家带来的时候如何运用PHP数组实现单链表结构
此类主要是依靠PHP强大的数组系统来模拟出单链表类型的数据结构。 本人完全凭借自己的 兴趣来编写此类，并未考虑其实用性，主要是给大家理解一些简单的数据结构知识，同时也训练 一下PHP中的数组运用能力。
单链表简介：
单链表是最简单的链表表示。用它来表示线性表时，每一个数据元素占用一个结点(node)。一个 结点一般由两个域组成，一个域存放数据元素data； 另一个域存放一个指向链表中下一个结点的指针link，它指出下一个结点 的开始存储地址。而最后一个结点的指针为空。单链表中数据元素之间的逻 辑关系是由结点中的指针指示的，换句话说，指针为数据元素之间的逻辑关系的映象，则逻辑上相邻的两个元素其存储的物理位置不要求紧邻，因此， 这种存储结构为非顺序映像或链式映像。当然，在PHP没有指针这个概念，但是我们可以用关联数组来模拟。
立即学习“PHP免费学习笔记（深入）”；
PHP数组实现单链表的代码如下：
<ol class="dp-xml"><li class="alt"><span><strong><font color="#006699"><span class="tag"><?</span><span class="tag-name">php</span></font></strong><span> </span></span></li><li class=""><span>class LinkList </span></li><li class="alt"><span>{ </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 成员变量 </span></li><li class=""><span> * @var array $linkList 链表数组 </span></li><li class="alt"><span> * @var number $listHeader 表头索引 </span></li><li class=""><span> * @var number $listLength 链表长度 </span></li><li class="alt"><span> * @var number $existedCounts 记录链表中出现过的元素的个数，和$listLength不同的是, 删除一 </span></li><li class=""><span> * 个元素之后，该值不需要减1，这个也可以用来为新元素分配索引。 </span></li><li class="alt"><span> */ </span></li><li class=""><span> protected $</span><span class="attribute"><font color="#ff0000">linkList</font></span><span> =</span><span class="attribute-value"><font color="#0000ff">array</font></span><span>(); </span></li><li class="alt"><span> protected $</span><span class="attribute"><font color="#ff0000">listLength</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>; </span></li><li class=""><span> protected $</span><span class="attribute"><font color="#ff0000">listHeader</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">null</font></span><span>; </span></li><li class="alt"><span> protected $</span><span class="attribute"><font color="#ff0000">existedCounts</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>; </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 构造函数 </span></li><li class=""><span> * 构造函数可以带一个数组参数，如果有参数，则调用成员方法 </span></li><li class="alt"><span> * createList将数组转换成链表，并算出链表长度.如果没有参 </span></li><li class=""><span> * 数，则生成一空链表.空链表可以通过调用成员方法createList </span></li><li class="alt"><span> * 生成链表. </span></li><li class=""><span> * @access public </span></li><li class="alt"><span> * @param array $arr 需要被转化为链表的数组 </span></li><li class=""><span> */ </span></li><li class="alt"><span> public function __construct($</span><span class="attribute"><font color="#ff0000">arr</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">''</font></span><span>) </span></li><li class=""><span> { </span></li><li class="alt"><span> $arr!=null&&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>createList($arr); </span></li><li class=""><span> } </span></li><li class="alt"><span> /** </span></li><li class=""><span> * 生成链表的函数 </span></li><li class="alt"><span> * 将数组转变成链表，同时计算出链表长度。分别赋值给成员标量 </span></li><li class=""><span> * $linkList和$listLength. </span></li><li class="alt"><span> * @access public </span></li><li class=""><span> * @param array $arr 需要被转化为链表的数组 </span></li><li class="alt"><span> * @return boolean true表示转换成功，false表示失败 </span></li><li class=""><span> */ </span></li><li class="alt"><span> public function createList($arr) </span></li><li class=""><span> { </span></li><li class="alt"><span> if (!is_array($arr)) </span></li><li class=""><span> return false; </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">length</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">count</font></span><span>($arr); </span></li><li class=""><span> for($</span><span class="attribute"><font color="#ff0000">i</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>;$i</span><span class="tag"><strong><font color="#006699"><</font></strong></span><span>$length;$i++) </span></li><li class="alt"><span> { </span></li><li class=""><span> if($</span><span class="attribute"><font color="#ff0000">i</font></span><span>==$length-1) </span></li><li class="alt"><span> { </span></li><li class=""><span> //每个链表结点包括var和next两个索引，var表示结点值，next为下一个结点的索引 </span></li><li class="alt"><span> //最后一个结点的next为null </span></li><li class=""><span> $list[$i]['var'] =$arr[$i]; </span></li><li class="alt"><span> $list[$i]['next'] =null; </span></li><li class=""><span> } </span></li><li class="alt"><span> else </span></li><li class=""><span> { </span></li><li class="alt"><span> $list[$i]['var'] =$arr[$i]; </span></li><li class=""><span> $list[$i]['next'] =$i+1; </span></li><li class="alt"><span> } </span></li><li class=""><span> } </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">linkList</font></span><span> =$list; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">listLength</font></span><span> =$length; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">existedCounts</font></span><span> =$length; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">listHeader</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>; </span></li><li class="alt"><span> return true; </span></li><li class=""><span> } </span></li><li class="alt"><span> /** </span></li><li class=""><span> * 将链表还原成一维数组 </span></li><li class="alt"><span> * @access public </span></li><li class=""><span> * @return array $arr 生成的一维数组 </span></li><li class="alt"><span> */ </span></li><li class=""><span> public function returnToArray() </span></li><li class="alt"><span> { </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">arr</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">array</font></span><span>(); </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">tmp</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader]; </span></li><li class=""><span> for($</span><span class="attribute"><font color="#ff0000">i</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>;$i</span><span class="tag"><strong><font color="#006699"><</font></strong></span><span>$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength;$i++) </span></li><li class="alt"><span> { </span></li><li class=""><span> $arr[]=$tmp['var']; </span></li><li class="alt"><span> if ($i!=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength-1) </span></li><li class=""><span> { </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">tmp</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$tmp['next']]; </span></li><li class=""><span> } </span></li><li class="alt"><span> } </span></li><li class=""><span> return $arr; </span></li><li class="alt"><span> } </span></li><li class=""><span>public function getLength() </span></li><li class="alt"><span> { </span></li><li class=""><span> return $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength; </span></li><li class="alt"><span> } </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 计算一共删除过多少个元素 </span></li><li class=""><span> * @access public </span></li><li class="alt"><span> * @return number $count 到目前为止删除过的元素个数 </span></li><li class=""><span> */ </span></li><li class="alt"><span> public function getDeletedNums() </span></li><li class=""><span> { </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">count</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts-$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength; </span></li><li class=""><span> return $count; </span></li><li class="alt"><span> } </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 通过元素索引返回元素序号 </span></li><li class=""><span> * @access protected </span></li><li class="alt"><span> * @param $index 元素的索引号 </span></li><li class=""><span> * @return $num 元素在链表中的序号 </span></li><li class="alt"><span> */ </span></li><li class=""><span> public function getElemLocation($index) </span></li><li class="alt"><span> { </span></li><li class=""><span> if (!array_key_exists($index,$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList)) </span></li><li class="alt"><span> return false; </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">arrIndex</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader; </span></li><li class="alt"><span> for($</span><span class="attribute"><font color="#ff0000">num</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span>;$</span><span class="attribute"><font color="#ff0000">tmp</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$arrIndex];$num++) </span></li><li class=""><span> { </span></li><li class="alt"><span> if ($</span><span class="attribute"><font color="#ff0000">index</font></span><span>==$arrIndex) </span></li><li class=""><span> break; </span></li><li class="alt"><span> else </span></li><li class=""><span> { </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">arrIndex</font></span><span>=$tmp['next']; </span></li><li class=""><span> } </span></li><li class="alt"><span> } </span></li><li class=""><span> return $num; </span></li><li class="alt"><span> } </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 获取第$i个元素的引用 </span></li><li class=""><span> * 这个保护方法不能被外界直接访问，许多服务方法以来与次方法。 </span></li><li class="alt"><span> * 它用来返回链表中第$i个元素的引用，是一个数组 </span></li><li class=""><span> * @access protected </span></li><li class="alt"><span> * @param number $i 元素的序号 </span></li><li class=""><span> * @return reference 元素的引用 </span></li><li class="alt"><span> */ </span></li><li class=""><span> protected function &getElemRef($i) </span></li><li class="alt"><span> { </span></li><li class=""><span> //判断$i的类型以及是否越界 </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">result</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">false</font></span><span>; </span></li><li class=""><span> if (!is_numeric($i)||(int)$i</span><span class="tag"><strong><font color="#006699"><</font></strong></span><span>=0||(int)$i</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength) </span></li><li class="alt"><span> return $result; </span></li><li class=""><span> //由于单链表中的任何两个元素的存储位置之间没有固定关系，要取得第i个元素必须从 </span></li><li class="alt"><span> //表头开始查找，因此单链表是非随机存储的存储结构。 </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">j</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>; </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">value</font></span><span>=&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader]; </span></li><li class=""><span> while ($j</span><span class="tag"><strong><font color="#006699"><</font></strong></span><span>$i-1) </span></li><li class="alt"><span> { </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">value</font></span><span>=&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$value['next']]; </span></li><li class="alt"><span> $j++; </span></li><li class=""><span> } </span></li><li class="alt"><span> return $value; </span></li><li class=""><span> } </span></li><li class="alt"><span> /** </span></li><li class=""><span> * 返回第i个元素的值 </span></li><li class="alt"><span> * @access public </span></li><li class=""><span> * @param number $i 需要返回的元素的序号，从1开始 </span></li><li class="alt"><span> * @return mixed 第i个元素的值 </span></li><li class=""><span> */ </span></li><li class="alt"><span> public function getElemvar($i) </span></li><li class=""><span> { </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">var</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>getElemRef($i); </span></li><li class=""><span> if ($var!=false) </span></li><li class="alt"><span> { </span></li><li class=""><span> return $var['var']; </span></li><li class="alt"><span> } </span></li><li class=""><span> else return false; </span></li><li class="alt"><span> } </span></li><li class=""><span> /** </span></li><li class="alt"><span> * 在第i个元素之后插入一个值为var的新元素 </span></li><li class=""><span> * i的取值应该为[1,$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength]，如果</span><span class="attribute"><font color="#ff0000">i</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">0</font></span><span>，表示在表的最前段插入， </span></li><li class="alt"><span> * 如果</span><span class="attribute"><font color="#ff0000">i</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength，表示在表的末尾插入,插入的方法为，将第$i-1个元素 </span></li><li class=""><span> * 的next指向第$i个元素，然后将第$i个元素的next指向第$i+1个元素，这样就实现了插入 </span></li><li class="alt"><span> * @access public </span></li><li class=""><span> * @param number $i 在位置i插入新元素 </span></li><li class="alt"><span> * @param mixed $var 要插入的元素的值 </span></li><li class=""><span> * @return boolean 成功则返回true,否则返回false </span></li><li class="alt"><span> */ </span></li><li class=""><span> public function insertIntoList($i,$var) </span></li><li class="alt"><span> { </span></li><li class=""><span> if (!is_numeric($i)||(int)$i</span><strong><font color="#006699"><span class="tag"><</span><span class="tag-name">0</span></font></strong><span>||(int)$i</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength) </span></li><li class="alt"><span> return false; </span></li><li class=""><span> if ($</span><span class="attribute"><font color="#ff0000">i</font></span><span>==0) </span></li><li class="alt"><span> { </span></li><li class=""><span> //如果$i-0，则在表最前面添加元素，新元素索引为$listLength，这样是确保不会 </span></li><li class="alt"><span> //覆盖原来的元素，另外这种情况需要重新设置$listHeader </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts]['var'] =$var; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts]['next']=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">listHeader</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength++; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts++; </span></li><li class="alt"><span> return true; </span></li><li class=""><span> } </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">value</font></span><span>=&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>getElemRef($i); </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts]['var'] =$var; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts]['next']=($</span><span class="attribute"><font color="#ff0000">i</font></span><span>==$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength?null:$value['next']); </span></li><li class=""><span> $value['next']=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength++; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts++; </span></li><li class="alt"><span> return true; </span></li><li class=""><span> } </span></li><li class="alt"><span> /** </span></li><li class=""><span> * 删除第$i个元素 </span></li><li class="alt"><span> * 删除第$i个元素，该元素为取值应该为[1，$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength],需要注意，删除元素之后， </span></li><li class=""><span> * $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength减1,而$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>existedCounts不变。删除的方法为将第$i-1个元素的 </span></li><li class="alt"><span> * next指向第$i+1个元素，那么第$i个元素就从链表中删除了。 </span></li><li class=""><span> * @access public </span></li><li class="alt"><span> * @param number $i 将要被删除的元素的序号 </span></li><li class=""><span> * @return boolean 成功则返回true,否则返回false </span></li><li class="alt"><span> */ </span></li><li class=""><span> public function delFromList($i) </span></li><li class="alt"><span> { </span></li><li class=""><span> if (!is_numeric($i)||(int)$i</span><span class="tag"><strong><font color="#006699"><</font></strong></span><span>=0||(int)$i</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength) </span></li><li class="alt"><span> return false; </span></li><li class=""><span> if ($</span><span class="attribute"><font color="#ff0000">i</font></span><span>==1) </span></li><li class="alt"><span> { </span></li><li class=""><span> //若删除的结点为头结点，则需要从新设置链表头 </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">tmp</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader]; </span></li><li class=""><span> unset($this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listHeader]); </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span class="attribute"><font color="#ff0000">listHeader</font></span><span>=$tmp['next']; </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength--; </span></li><li class="alt"><span> return true; </span></li><li class=""><span> } </span></li><li class="alt"><span> else </span></li><li class=""><span> { </span></li><li class="alt"><span> $</span><span class="attribute"><font color="#ff0000">value</font></span><span> =&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>getElemRef($i); </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">prevValue</font></span><span>=&$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>getElemRef($i-1); </span></li><li class="alt"><span> unset($this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>linkList[$prevValue['next']]); </span></li><li class=""><span> $prevValue['next']=$value['next']; </span></li><li class="alt"><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>listLength--; </span></li><li class=""><span> return true; </span></li><li class="alt"><span> } </span></li><li class=""><span> } </span></li><li class="alt"><span>/** </span></li><li class=""><span> * 对链表的元素排序 </span></li><li class="alt"><span> * 谨慎使用此函数，排序后链表将被从新初始化，原有的成员变量将会被覆盖 </span></li><li class=""><span> * @accse public </span></li><li class="alt"><span> * @param boolean $</span><span class="attribute"><font color="#ff0000">sortType</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">'true'</font></span><span> 排序方式,true表示升序，false表示降序，默认true </span></li><li class=""><span> */ </span></li><li class="alt"><span>public function listSort($</span><span class="attribute"><font color="#ff0000">sortType</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">'true'</font></span><span>) </span></li><li class=""><span>{ </span></li><li class="alt"><span> //从新修改关联关系可能会更复杂，所以我选择先还原成一维数组，然后对数组排序，然后再生成链表 </span></li><li class=""><span> $</span><span class="attribute"><font color="#ff0000">arr</font></span><span>=$this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>returnToArray(); </span></li><li class="alt"><span> $sortType?sort($arr):rsort($arr); </span></li><li class=""><span> $this-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>createList($arr); </span></li><li class="alt"><span>} </span></li><li class=""><span>} </span></li><li class="alt"><span></span><span class="tag"><strong><font color="#006699">?></font></strong></span><span> </span></li></ol>上面这段代码就是PHP数组实现单链表的源码编写，希望对大家有所帮助。
