php中的单项链表与双向链表

（一）什么是链表？

链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。

1、那么先从单向链表着手，先看看单向链表的模拟图：

单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。

2、双向链表：

从上图可以很清晰的看出，每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。

3、循环链表：

循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。

参考：http://zh.wikipedia.org/wiki/链表

（二）链表有什么作用？

链表本质上就是一种数据结构，主要用来动态放置数据。也可用来构建许多数据结构，比如堆栈、队列及它们的派生。

（三）链表的实现？

1、单向链表的实现

（1）单向链表的创建过程：

第一步：定义节点的数据结构；

第二步：创建一个空表。

第三步：利用malloc（）向系统申请分配一个节点。

第四步：将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点连接到表尾。

第五步：判断是否有后续节点，如有则转入第三步，否则结束。

（2）单向链表的输出过程：

第一步：找到表头。

第二步：若为非空表，则输出节点的值成员，是空表则退出。

第三步：跟踪链表，找到下一节点的地址。

第四步：转到第二步。

//单项链表实现

单链表，节点只有一个指针域的链表。节点包括数据域和指针域。

　　因此用面向对象的思维，节点类的属性就有两个：一个data（表示存储的数据），一个指针next（链表中指向下一个节点）。

　　链表一个很重要的特性，就是这个头节点$head。它绝对不能少，每次遍历都要从它开始，并且不能移动头节点，应该用一个变量去代替他移动。脑袋里要有链表的结构。这是关键。

　　来一段代码：

　　

1 <?php 2 3 class Node{ 4 public $data = ''; 5 public $next = null; 6 function __construct($data) 7 { 8 $this->data = $data; 9 } 10 } 11 12 13 // 链表有几个元素 14 function countNode($head){ 15 $cur = $head; 16 $i = 0; 17 while(!is_null($cur->next)){ 18 ++$i; 19 $cur = $cur->next; 20 } 21 return $i; 22 } 23 24 // 增加节点 25 function addNode($head, $data){ 26 $cur = $head; 27 while(!is_null($cur->next)){ 28 $cur = $cur->next; 29 } 30 $new = new Node($data); 31 $cur->next = $new; 32 33 } 34 35 // 紧接着插在$no后 36 function insertNode($head, $data, $no){ 37 if ($no > countNode($head)){ 38 return false; 39 } 40 $cur = $head; 41 $new = new Node($data); 42 for($i=0; $i<$no;$i++){ 43 $cur = $cur->next; 44 } 45 $new->next = $cur->next; 46 $cur->next = $new; 47 48 } 49 50 // 删除第$no个节点 51 function delNode($head, $no){ 52 if ($no > countNode($head)){ 53 return false; 54 } 55 $cur = $head; 56 for($i=0; $i<$no-1; $i++){ 57 $cur = $cur->next; 58 } 59 $cur->next = $cur->next->next; 60 61 } 62 63 // 遍历链表 64 function showNode($head){ 65 $cur = $head; 66 while(!is_null($cur->next)){ 67 $cur = $cur->next; 68 echo $cur->data, '<br/>'; 69 } 70 } 71 72 $head = new Node(null);// 定义头节点 73 74 75 addNode($head, 'a'); 76 addNode($head, 'b'); 77 addNode($head, 'c'); 78 79 insertNode($head, 'd', 0); 80 81 showNode($head); 82 83 echo '<hr/>'; 84 85 delNode($head, 2); 86 87 showNode($head); //双向链表

PHP SPL标准库里实现了几种简单的线性表和树型结构，其中包括了双链表和双链表实现的队列和栈、最大堆、最小堆和优先队列。双链表是一种重要的线性存储结构，对于双链表中的每个节点，不仅仅存储自己的信息，还要保存前驱和后继节点的地址。

双链表对php开发程序来讲是很重要的一种数据结构，可以把PHP数组中想想成一个双链表，而PHP内置的SplDoublyLinkedList类通过实现迭代器、数组访问和获取数量的接口使程序访问对象变得访问数组一样方便。

SplDoublyLinkedList类代码如下：

[php] view plain copy <?php  /**  * PS：关于预定义接口Iterator, ArrayAccess, Countable的文章已经介绍过了，不认识的可以往前翻翻  */  class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable  {      /**       * @var _llist 定义一个数组用于存放数据      */      protected $_llist   = array();        /**       * @var _it_mode 链表的迭代模式      */      protected $_it_mode = 0;        /**       * @var _it_pos 链表指针      */      protected $_it_pos  = 0;      /**       * 迭代模式      * @see setIteratorMode      */      const IT_MODE_LIFO     = 0x00000002;      const IT_MODE_FIFO     = 0x00000000;      const IT_MODE_KEEP     = 0x00000000;      const IT_MODE_DELETE   = 0x00000001;        /**       * @return 返回被移出尾部节点元素      * @throw RuntimeException 如果链表为空则抛出异常      */      public function pop()      {          if (count($this->_llist) == 0) {              throw new RuntimeException("Can't pop from an empty datastructure");          }          return array_pop($this->_llist);      }        /**       * @return 返回被移出头部节点元素      * @throw RuntimeException 如果链表为空则抛出异常      */      public function shift()      {          if (count($this->_llist) == 0) {              throw new RuntimeException("Can't shift from an empty datastructure");          }          return array_shift($this->_llist);      }        /**       * 往链表尾部添加一个节点元素      * @param $data 要添加的节点元素      */      public function push($data)      {          array_push($this->_llist, $data);          return true;      }        /**       * 往链表头部添加一个节点元素      * @param $data 要添加的节点元素      */      public function unshift($data)      {          array_unshift($this->_llist, $data);          return true;      }        /**       * @return 返回尾部节点元素，并把指针指向尾部节点元素      */      public function top()      {          return end($this->_llist);      }        /**       * @return 返回头部节点元素，并把指针指向头部节点元素      */      public function bottom()      {          return reset($this->_llist);      }        /**       * @return 返回链表节点数      */      public function count()      {          return count($this->_llist);      }        /**       * @return 判断链表是否为空      */      public function isEmpty()      {          return ($this->count() == 0);      }      /**       * 设置迭代模式      * - 迭代的顺序 (先进先出、后进先出)      *  - SplDoublyLnkedList::IT_MODE_LIFO (堆栈)      *  - SplDoublyLnkedList::IT_MODE_FIFO (队列)      *      * - 迭代过程中迭代器的行为      *  - SplDoublyLnkedList::IT_MODE_DELETE (删除已迭代的节点元素)      *  - SplDoublyLnkedList::IT_MODE_KEEP   (保留已迭代的节点元素)      *      * 默认的模式是 0 : SplDoublyLnkedList::IT_MODE_FIFO | SplDoublyLnkedList::IT_MODE_KEEP      *      * @param $mode 新的迭代模式      */      public function setIteratorMode($mode)      {          $this->_it_mode = $mode;      }        /**       * @return 返回当前的迭代模式      * @see setIteratorMode      */      public function getIteratorMode()      {          return $this->_it_mode;      }        /**       * 重置节点指针      */      public function rewind()      {          if ($this->_it_mode & self::IT_MODE_LIFO) {              $this->_it_pos = count($this->_llist)-1;          } else {              $this->_it_pos = 0;          }      }        /**       * @return 判断指针对应的节点元素是否存在      */      public function valid()      {          return array_key_exists($this->_it_pos, $this->_llist);      }        /**       * @return 返回当前指针的偏移位置      */      public function key()      {          return $this->_it_pos;      }        /**       * @return 返回当前指针对应的节点元素      */      public function current()      {          return $this->_llist[$this->_it_pos];      }        /**       * 将指针向前移动一个偏移位置      */      public function next()      {          if ($this->_it_mode & self::IT_MODE_LIFO) {              if ($this->_it_mode & self::IT_MODE_DELETE) {                  $this->pop();              }              $this->_it_pos--;          } else {              if ($this->_it_mode & self::IT_MODE_DELETE) {                  $this->shift();              } else {                  $this->_it_pos++;              }          }      }      /**       * @return 偏移位置是否存在      *      * @param $offset             偏移位置      * @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常      */      public function offsetExists($offset)      {          if (!is_numeric($offset)) {              throw new OutOfRangeException("Offset invalid or out of range");          } else {              return array_key_exists($offset, $this->_llist);          }      }        /**       * @return 获取偏移位置对应的值      *      * @param $offset             偏移位置      * @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常      */      public function offsetGet($offset)      {          if ($this->_it_mode & self::IT_MODE_LIFO) {              $realOffset = count($this->_llist)-$offset;          } else {              $realOffset = $offset;          }          if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {              throw new OutOfRangeException("Offset invalid or out of range");          } else {              return $this->_llist[$realOffset];          }      }        /**       * @return 设置偏移位置对应的值      *      * @param $offset             偏移位置      * @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常      */      public function offsetSet($offset, $value)      {          if ($offset === null) {              return $this->push($value);          }          if ($this->_it_mode & self::IT_MODE_LIFO) {              $realOffset = count($this->_llist)-$offset;          } else {              $realOffset = $offset;          }          if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {              throw new OutOfRangeException("Offset invalid or out of range");          } else {              $this->_llist[$realOffset] = $value;          }      }        /**       * @return 删除偏移位置对应的值      *      * @param $offset             偏移位置      * @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常      */      public function offsetUnset($offset)      {          if ($this->_it_mode & self::IT_MODE_LIFO) {              $realOffset = count($this->_llist)-$offset;          } else {              $realOffset = $offset;          }          if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {              throw new OutOfRangeException("Offset invalid or out of range");          } else {              array_splice($this->_llist, $realOffset, 1);          }      }  }  ?>  

例子说明：

[php] view plain copy <?php  $doubly=new SplDoublyLinkedList();  $doubly->push('a');  $doubly->push('b');  $doubly->push('c');  $doubly->push('d');    echo '初始链表结构：';  var_dump($doubly);    echo '<br/> 先进先出Keep模式迭代输出： <br/>';  $doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);  $doubly->rewind();  foreach($doubly as $key=>$value)  {      echo $key.' '.$value."<br/>";  }    echo '<br/>后进先出Keep模式迭代输出：<br/>';  $doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP);  $doubly->rewind();  foreach($doubly as $key=>$value)  {      echo $key.' '.$value."<br/>";  }    echo '<br/>后进先出Delete模式迭代输出：<br/>';  $doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);  $doubly->rewind();  foreach($doubly as $key=>$value)  {      if($key == 1) break;      echo $key.' '.$value."<br/>";  }  echo '<br/>Delete模式迭代之后的链表：';  var_dump($doubly);  ?>   输出：

初始链表结构：

object(SplDoublyLinkedList)[1] private 'flags' => int 0 private 'dllist' => array (size=4) 0 => string 'a' (length=1) 1 => string 'b' (length=1) 2 => string 'c' (length=1) 3 => string 'd' (length=1) 先进先出Keep模式迭代输出：  0 a 1 b 2 c 3 d 后进先出Keep模式迭代输出： 3 d 2 c 1 b 0 a 后进先出Delete模式迭代输出： 3 d 2 c Delete模式迭代之后的链表： object(SplDoublyLinkedList)[1] private 'flags' => int 3 private 'dllist' => array (size=2) 0 => string 'a' (length=1) 1 => string 'b' (length=1)