/** 
 * 链表
 * Node 类用来表示节点,LinkedList 类提供了插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法。
 * 
 * author ubuntuvim
 * website http://ibeginner.sinaapp.com
 */

function Node(e) {
	this.elem = e;  // 节点的元素
	this.next = null;  //指向下一个元素的指针
}

function LinkedList() {
	this.head = new Node("head");  //默认初始化头结点
	this.find = find;
	this.insert = insert;
	this.remove = remove;
	this.display = display;
}

/**
 * 查找元素
 * @param e 查找的元素
 * @return 匹配的元素；不存在返回，null(定义Node默认为null，如果不设置默认应该是undefined)
 */
function find(e) {
	var currNode = this.head;
	//  如果当前的节点不是要查找的节点继续匹配下一个节点
	while (null != currNode && currNode.elem != e) {
		currNode = currNode.next;
	}

	return currNode;
}

/**
 * 插入元素
 * @param newElem 插入的元素
 * @param pos 元素插入的位置（pos的next就是插入的位置）
 */
function insert(newElem, pos) {
	var newNode = new Node(newElem);  //创建一个新的节点
	var currPos = this.find(pos);  //找到插入的位置
	if (null != currPos) {
		newNode.next = currPos.next;  //新插入的元素指向插入未指定下一个元素
		currPos.next = newNode;  //原来的元素执行新插入的元素
	}
}

/**
 * 显示链表数据
 */
function display() {
	var currNode = this.head;  //设置游标的位置指向头元素
	while (null != currNode.next) {
		print(currNode.next.elem);
		//指向下一个元素
		currNode = currNode.next;
	}
}

// 测试前面的代码
var ct = new LinkedList();
ct.insert("JJ", "head");
ct.insert("NBA", "JJ");  
ct.insert("last element", "NBA");
ct.insert("insert", "NBA");  //  在NBA后插入一个元素
ct.insert("head next element", "head");  //在头结点后插入一个元素
ct.display();


/**
 * 移除一个节点
 * 从链表中删除节点时,需要先找到待删除节点前面的节点。
 * 找到这个节点后,修改它的 next 属性,使其不再指向待删除节点,而是指向待删除节点的下一个节点。
 */
function remove(e) {
	var currNode = this.head;  //设置游标的位置指向头元素
	while (null != currNode.next && currNode.next.elem != e) {
		//指向下一个元素
		currNode = currNode.next;  // 
	}
	//  暂时保存要删除的节点
	var tmpNode = currNode.next;
	// console.log('tmpNode = ' + tmpNode);
	//修改节点的指向
	if (null != currNode) {
		currNode.next = currNode.next.next;
	}
	//  删除完成之后清处已经删除的节点
	tmpNode = null;  // javascript会自动回收
	//console.log('tmpNode = ' + tmpNode);
	//console.log('tmpNode.elem = ' + tmpNode.elem);  //TypeError: tmpNode is null
}

ct.remove("NBA");
print("\n删除节点NBA.\n");
ct.display();