PHP实现双向链表

 

<?php
/**
 * **双向链表
 * @author zhiyuan12@
 * @modified 2012-10-25
 */
/**
 * 链表元素结点类
 */
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 );
?>