<?php/** * **雙向鏈表 * @author zhiyuan12@ *//** * 鏈表元素結點類 */class Node_Element {  public $pre = NULL; // 前驅  public $next = NULL; // 后繼  public $key = NULL; // 元素鍵值  public $data = NULL; // 結點值  function __Construct($key, $data) {    $this->key = $key;    $this->data = $data;  }}/** * 雙向鏈表類 */class DoubleLinkedList {  private $head; // 頭指針  private $tail; // 尾指針  private $current; // 當前指針  private $len; // 鏈表長度  function __Construct() {    $this->head = self::_getNode ( null, null );    $this->curelement = $this->head;    $this->tail = $this->head;    $len = 0;  }  /**   * @ desc: 讀取鏈表全部結點   */  public function readAll() {    $tmp = $this->head;    while ( $tmp->next !== null ) {      $tmp = $tmp->next;      var_dump ( $tmp->key, $tmp->data );    }  }  public function move($pos1, $pos2) {    $pos1Node = $this->findPosition ( $pos1 );    $pos2Node = $this->findPosition ( $pos2 );    if ($pos1Node !== null && $pos2Node !== null) {      $tmpKey = $pos1Node->key;      $tmpData = $pos1Node->data;      $pos1Node->key = $pos2Node->key;      $pos1Node->data = $pos2Node->data;      $pos2Node->key = $tmpKey;      $pos2Node->data = $tmpData;      return true;    }    return false;  }  /**   * @ desc: 在指定關鍵詞刪除結點   *   * @param : $key   *     指定位置的鏈表元素key   */  public function delete($key) {    $pos = $this->find ( $key );    if ($pos !== null) {      $tmp = $pos;      $last = null;      $first = true;      while ( $tmp->next !== null && $tmp->next->key === $key ) {        $tmp = $tmp->next;        if (! $first) {          $this->delNode ( $last );        } else {          $first = false;        }        $last = $tmp;      }      if ($tmp->next !== null) {        $pos->pre->next = $tmp->next;        $tmp->next->pre = $pos->pre;      } else {        $pos->pre->next = null;      }      $this->delNode ( $pos );      $this->delNode ( $tmp );    }  }  /**   * @ desc: 在指定位置刪除結點   *   * @param : $key   *     指定位置的鏈表元素key   */  public function deletePosition($pos) {    $tmp = $this->findPosition ( $pos );    if ($tmp === null) {      return true;    }    if ($tmp === $this->getTail ()) {      $tmp->pre->next = null;      $this->delNode ( $tmp );      return true;    }    $tmp->pre->next = $tmp->next;    $tmp->next->pre = $tmp->pre;    $this->delNode ( $tmp );  }  /**   * @ desc: 在指定鍵值之前插入結點   *   * @param : $key   *     //指定位置的鏈表元素key   * @param : $data   *     //要插入的鏈表元素數據   * @param : $flag   *     //是否順序查找位置進行插入   */  public function insert($key, $data, $flag = true) {    $newNode = self::_getNode ( $key, $data );    $tmp = $this->find ( $key, $flag );    if ($tmp !== null) {      $newNode->pre = $tmp->pre;      $newNode->next = $tmp;      $tmp->pre = $newNode;      $newNode->pre->next = $newNode;    } else {      $newNode->pre = $this->tail;      $this->tail->next = $newNode;      $this->tail = $newNode;    }    $this->len ++;  }  /**   * @ desc: 在指定位置之前插入結點   *   * @param : $pos   *     指定插入鏈表的位置   * @param : $key   *     指定位置的鏈表元素key   * @param : $data   *     要插入的鏈表元素數據   */  public function insertPosition($pos, $key, $data) {    $newNode = self::_getNode ( $key, $data );    $tmp = $this->findPosition ( $pos );    if ($tmp !== null) {      $newNode->pre = $tmp->pre;      $newNode->next = $tmp;      $tmp->pre = $newNode;      $newNode->pre->next = $newNode;    } else {      $newNode->pre = $this->tail;      $this->tail->next = $newNode;      $this->tail = $newNode;    }    $this->len ++;    return true;  }  /**   * @ desc: 根據key值查詢指定位置數據   *   * @param : $key   *     //指定位置的鏈表元素key   * @param : $flag   *     //是否順序查找   */  public function find($key, $flag = true) {    if ($flag) {      $tmp = $this->head;      while ( $tmp->next !== null ) {        $tmp = $tmp->next;        if ($tmp->key === $key) {          return $tmp;        }      }    } else {      $tmp = $this->getTail ();      while ( $tmp->pre !== null ) {        if ($tmp->key === $key) {          return $tmp;        }        $tmp = $tmp->pre;      }    }    return null;  }  /**   * @ desc: 根據位置查詢指定位置數據   *   * @param : $pos   *     //指定位置的鏈表元素key   */  public function findPosition($pos) {    if ($pos <= 0 || $pos > $this->len)      return null;    if ($pos < ($this->len / 2 + 1)) {      $tmp = $this->head;      $count = 0;      while ( $tmp->next !== null ) {        $tmp = $tmp->next;        $count ++;        if ($count === $pos) {          return $tmp;        }      }    } else {      $tmp = $this->tail;      $pos = $this->len - $pos + 1;      $count = 1;      while ( $tmp->pre !== null ) {        if ($count === $pos) {          return $tmp;        }        $tmp = $tmp->pre;        $count ++;      }    }    return null;  }  /**   * @ desc: 返回鏈表頭節點   */  public function getHead() {    return $this->head->next;  }  /**   * @ desc: 返回鏈表尾節點   */  public function getTail() {    return $this->tail;  }  /**   * @ desc: 查詢鏈表節點個數   */  public function getLength() {    return $this->len;  }  private static function _getNode($key, $data) {    $newNode = new Node_Element ( $key, $data );    if ($newNode === null) {      echo "new node fail!";    }    return $newNode;  }  private function delNode($node) {    unset ( $node );    $this->len --;  }}$myList = new DoubleLinkedList ();$myList->insert ( 1, "test1" );$myList->insert ( 2, "test2" );$myList->insert ( "2b", "test2-b" );$myList->insert ( 2, "test2-c" );$myList->insert ( 3, "test3" );$myList->insertPosition ( 5, "t", "testt" );$myList->readAll ();echo "+++";$myList->deletePosition(0);$myList->readAll ();echo "..." . $myList->getLength ();var_dump ( $myList->findPosition ( 3 )->data );?>

int(1)string(5) "test1"int(2)string(7) "test2-c"int(2)string(5) "test2"string(2) "2b"string(7) "test2-b"string(1) "t"string(5) "testt"int(3)string(5) "test3"+++int(1)string(5) "test1"int(2)string(7) "test2-c"int(2)string(5) "test2"string(2) "2b"string(7) "test2-b"string(1) "t"string(5) "testt"int(3)string(5) "test3"...6string(5) "test2"