doublelinked.md

之前所讨论的链表是单向链表，只能从前向后寻找，无法从后向前查找节点，在这一节我们来解决这个问题。

首先要对节点进行扩展：

class Node_doublelinked extends Node_linked{
	public $prev = NULL;
	function __construct($value=NULL){
		parent::__construct($value);
	}
}

我们是基于之前的节点类Node_linked进行了改造，添加了一个$prev属性，这个属性指向了前一个节点。

随后我们实现双向链表类：

class Linear_doublelinked extends Linear_linked{
	function __construct(){
		$this->_head = new Node_doublelinked();		
	}

	function insert($value,$index){
		$length = $this->length();
		if($index<0 || $index>$length){
			return false;
		}
		$node = new Node_doublelinked($value);
		$prev = $this->head();
		for($i=0;$i<$index;$i++){
			$prev = $prev->next;
		}
		$node->next = $prev->next;
		$node->prev = $prev;
		if($prev->next){
			$prev->next->prev = $node;
		}
		$prev->next = $node;

		return true;
	}

	function delete($index){
		$length = $this->length();
		if($index<0 || $index>$length-1){
			return NULL;
		}
		$prev = $this->head();
		for($i=0;$i<$index;$i++){
			$prev = $prev->next;
		}
		$next = $prev->next;
		$value = $next->data;
		if($next->next){
			$next->next->prev = $prev;
		}
		$prev->next = $next->next;
		$next->next = NULL;
		$next->prev = NULL;
		unset($next);
		return $value;
	}
}

我这里只实现了双向链表的插入和删除操作，其他需要修改的操作，如merge请自行完成。在插入时，双向链表所需要改变的指针域更多，要考虑对$prev属性进行设置，注意这里的顺序。在删除时，也需要改变后继节点的$prev指向。