爱V空间

这个就是为了学习而使用，php有自身的链表实现，功能更全面，百度搜索 php spl

<?php
class node {
	public $val = null;
	public $pre = null;
	public $nex = null;
	//存放该node的位置
	public $index = null;
	public $num = 1;
	public function __construct($val){
		$this->val = $val;
		$this->pre = null;
		$this->nex = null;
	}
}

class links{
	//链表头
	static $head = null;
	//链表尾
	static $end = null;
	//链表内容
	static $nodes = [];
	
	/**
	 * 添加一个节点
	 * @param int $val 节点内容
	 */
	public static function add($val){
		//初始化一个节点
		$newNode = new node($val);
		$newNode->index = count(static::$nodes);
		static::$nodes[$newNode->index] = $newNode;
		//链表为空
		if( static::$head === null ){
			//头和尾都指向这个节点
			static::$head = $newNode->index;
			static::$end = $newNode->index;
		}else{
			static::searchSet($newNode, static::$nodes[static::$head]);
		}
	}

	/**
	 * 搜索链表插入
	 * @param node $newNode 新节点
	 * @param node $node 链表中的节点，和新节点做比较
	 */
	public static function searchSet($newNode, $node){
		//新插入的节点值小于目标节点值，则在目标节点前插入
		if($newNode->val < $node->val){
			if($node->pre === null){//如果目标节点前一个指向的是null，则说明需要在链表开头插入
				static::$head = $newNode->index;
			}else{//否则将前一个节点的后指针指向新节点，新节点的前指针指向前一个节点
				$pre = static::$nodes[$node->pre];
				$pre->nex = $newNode->index;
				$newNode->pre = $pre->index;
			}

			//新节点的后指针指向目标节点
			$newNode->nex = $node->index;
			//目标节点前指针指向新节点
			$node->pre = $newNode->index;

		}elseif($newNode->val == $node->val){
			++$node->num;
		}else{//新节点和下个节点比较
			if($node->nex === null){//如果下个节点为null，说明在链表尾部插入新节点
				$node->nex = $newNode->index;
				$newNode->pre = $node->index;
				static::$end = $newNode->index;
			}else{
				static::searchSet($newNode, static::$nodes[$node->nex]);
			}
		}
	}

    /**
     * 输出
     * @param bool $isasc 是否为正序输出
     */
	public static function printfs($isasc=true){
        static $index = null;

		if($index === null){
			if($isasc){
				$index = static::$head;
			}else{
				$index = static::$end;
			}
		}
		
		echo static::$nodes[$index]->val . ' ';

		if($isasc){
			if(static::$nodes[$index]->nex === null) return;
			$index = static::$nodes[$index]->nex;
		}else{
			if(static::$nodes[$index]->pre === null) return;
			$index = static::$nodes[$index]->pre;
		}

        static::printfs($isasc);
	}
}


function microtimeFloat() {
        list($usec, $sec) = explode(" ", microtime());
        return ((float) $usec + (float) $sec);
}


$time = microtimeFloat();
$ary = range(0, 1000);
shuffle($ary);

foreach($ary as $v){
	links::add($v);	
}
$time2 = microtimeFloat();
links::printfs();
$time3 = microtimeFloat();
echo "\n\n";
links::printfs(0);
$time4 = microtimeFloat();

echo "---------------\n";
echo ($time2 - $time) . "\n";
echo ($time3 - $time2) . "\n";
echo ($time4 - $time3) . "\n";