/** 
 * 双向链表
 * Node 类用来表示节点,LinkedList 类提供了插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法。
 * 
 * author ubuntuvim
 * website http://ibeginner.sinaapp.com
 */
function Node(e) {
	this.elem = e;
	this.next = null;  // 节点的后继
	this.previons = null;  //节点的前趋
}

function DoubleLinkedList() {
	this.head = new Node("head");
	this.insert = insert;
	this.find = find;
	this.display = display;
	this.findLast = findLast;
	this.dispReverse = dispReverse;
	this.remove = remove;
}

/**
 * 逆序显示所有的元素
 */ 
function dispReverse() {
	var currNode = this.head;
	currNode = this.findLast();
	while (null != currNode) {
		print(currNode.elem);
		currNode = currNode.previons;
	}
}

/**
 * 正序显示所有元素
 */
function display() {
	var currNode = this.head;
	while (null != currNode.next) {
		print(currNode.next.elem);
		currNode = currNode.next;  //  类似于i++的作用
	}
}

/**
 * 查找最后一个节点
 * @param 最后一个节点
 */
function findLast() {
	var currNode = this.head;  //从头结点开始遍历
	while (null != currNode.next) {
		currNode = currNode.next;
	}

	return currNode;
}

/**
 * 删除队列的元素
 */
function remove(item) {
	var currNode = this.find(item);
	if (null != currNode.next) {
		// 下列2句代码不能重复，否则导致队列断开，链接不上了
		currNode.previons.next = currNode.next;  //当前元素的上一个元素的后继指向当前元素的后继
		currNode.next.previons = currNode.previons; //当前元素的下一个元素的前趋指向当前元的前趋
		//回收删除的元素
		currNode.next = null;
		currNode.previons = null;
	}
}

/**
 * 查找某个节点
 * @return 匹配的节点；null-查找的节点不存在
 */
function find(item) {
	var currNode = this.head;  //从头遍历
	while (currNode.elem != item) {  //元素值不相等。继续向下遍历
		currNode = currNode.next;
	}

	return currNode;
}

/**
 * 在pos后面插入一个节点
 * @param e 插入的节点元素值
 * @param pos 插入位置
 */
function insert(e, pos) {
	// 构建要插入的节点
	var node = new Node(e);
	var currNode = this.find(pos);  //查找插入的位置
	node.next = currNode.next;  //新节点的后继指向插入位置元素的后继
	node.previons = currNode;  //新节点的前趋指向当前节点  
	currNode.next = node;  // 当前节点的后继指向新节点
}


// 测试
var dll = new DoubleLinkedList();
dll.insert("BeiJing", "head");  //节点beijing插入到head之后
dll.insert("GuangZhou", "BeiJing");  // 节点guangzhou插入到beijing之后
dll.insert("ShenZhen", "GuangZhou");  
dll.display();
print("\n从中间插入节点\n");
// 从中间插入节点
dll.insert("YuLin", "head");  //节点YuLin直接插入到head之后
dll.display();

print("\n删除节点GuangZhou\n");
dll.remove("GuangZhou");
dll.display();