PHP で二重リンクリストを実装するためのサンプルコード

/**
 * **二重リンクリスト
 * @author zhiyuan12@
 * @modified 2012-10-25
 * @site: bbs.it-home.org
*/
/**
 * リンクされたリスト要素のノードクラス
*/
class Node_Element { // プリカーサー
 public $next = NULL;後継者
 public $key = NULL; // 要素キー値
 public $data = NULL; // ノード値
 function __Construct($key, $data) {
 $this->key = $key; >data = $data; }
}
/**
 * 二重リンクリストクラス
*/
 private $head; // 先頭ポインタ
 private $tail; // 現在のpointer
 private $len; // リンクリストの長さ
 function __Construct() {
 $this->head = self::_getNode ( null, null );
 $this->tail = $this->head;
 $len = 0;
 }
 /**
 * @ desc: リンクされたリストのすべてのノードを読み取ります
*/
 $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; ;data = $pos2Node->data;
 $pos2Node->key = $tmpData;
 true を返す
 }
 /**
 * @ desc: 指定したキーワードのノードを削除
 *
 * @param: $key
 * 指定した位置のリンクリスト要素キー
*/
 public function delete($key) {
 $pos = $this->find ( $key );
 if ($pos !== null) {
 $tmp = $pos = null; ;
 $first = true;
 while ( $tmp->next !== null && $tmp->next->key === $key ) {
 $tmp = $tmp->next; if (! $first) {
 $this->delNode ( $last );
 $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 );
 }
 }
 /**
 * @ desc: 指定位置のノードを削除
 *
 * @param: $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 ) }
 $tmp->pre-> ;next = $tmp->next;
 $tmp->next->pre = $tmp->delNode ( $tmp ) }
 /**
 * @ desc: 指定されたキー値の前にノードを挿入します
 *
 * @param : $key
 * //指定された位置のリンク リスト要素キー
 * @param : $data
 * //リンク リスト要素挿入するデータ
 * @param: $flag
 * //位置を順番に検索して挿入するかどうか
 */
 public function insert($key, $data, $flag = true) {
 $newNode = self::_getNode ( $key, $data );
 $tmp = $this->find ( $key, $フラグ );
 if ($tmp !== null) {
 $newNode->pre = $tmp->pre;
 $tmp->pre = $newNode; ;
 $newNode->前>次 = $newNode;else {
 $newNode->pre = $this->tail;
 $this->tail->next = $newNode;
 $this->tail = $newNode;
 }
 $this->len ++;
 }
 /**
 * @ desc: 指定した位置の前にノードを挿入します
 *
 * @param : $pos
 * リンクリストに挿入する位置を指定します
 * @param : $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 ++;
 true を返します。
 }
 /**
 * @desc: キー値に基づいて指定された位置データをクエリします
 *
 * @param : $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;
 }
 }
 null を返します。
 }
 /**
 * @ desc: 位置に基づいて指定された位置データをクエリします
 *
 * @param: $pos
 * //指定された位置のリンク リスト要素キー
*/
 public function findPosition($pos) {
 if ($pos len)
 return null;
 if ($pos 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 ++;
 }
 }
 null を返します。
 }
 /**
 * @desc: リンクされたリストのヘッドノードを返します
*/
 public function getHead() {
 return $this->head->next;
 }
 /**
 * @desc: リンクされたリストの末尾ノードを返します
*/
 public function getTail() {
 return $this->tail;
 }
 /**
 * @ desc: リンクリスト内のノード数をクエリします
*/
 public function getLength() {
 return $this->len;
 }
 プライベート静的関数 _getNode($key, $data) {
 $newNode = new Node_Element ( $key, $data );
 if ($newNode === null) {
 echo "新しいノードが失敗しました!";
 }
 $newNode を返します。
 }
 プライベート関数 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();
// エコー「+++」;
// $myList->deletePosition(0);
// $myList->readAll();
// 「...」をエコーし​​ます。 $myList->getLength();
// var_dump ( $myList->findPosition ( 3 )->data );
?>