//节点构造函数,element用于保存节点的数据，next用来保存指向下一个节点的链接,previous用作前驱，记录前一个节点
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
//链表类构造函数，包含对链表操作的方法
function LList() {
this.head = new Node('head');
this.find = find;
this.insert = insert;
this.remove = remove;
this.display = display;
this.dispReverse=dispReverse;
this.findLast=findLast;
}
//查找节点
function find(item) {
var currentNode = this.head;
while (currentNode.element != item) {
currentNode = currentNode.next;
}
return currentNode;
}
//插入新节点
function insert(newElement, item) {
var newNode = new Node(newElement);
var currentNode = this.find(item);
newNode.next = currentNode.next;
currentNode.next = newNode;
newNode.previous = currentNode;
}
//打印链表的数据
function display() {
var currentNode = this.head;
while (currentNode.next != null) {
print(currentNode.next.element);
currentNode = currentNode.next;
}
}
//有了双链表之后，就不需要找到删除节点的前一个节点进行删除了。
// //找到要删除的节点的上一个节点
// function findPrevious(item) {
// var currentNode = this.head;
// //只有同时满足该节点下一个节点既不是null，又不是找到的那个节点，循环才会继续，
// //如果该节点是null，或者是找到的那个节点，那么就跳出循环
// while (currentNode.next.element != item && currentNode.next != null) {
// currentNode = currentNode.next;
// }
// return currentNode;
// }
//删除节点
function remove(item) {
var currentNode = this.find(item);
if (currentNode != null) {
//如果要删除节点的上一个节点不是null（也就不是找不到），
//将要删除节点的上一个节点的后继，连接到要删除节点的后继。
//将要删除节点的的下一个节点的前驱，连接到要删除节点的上一个节点
//将要删除节点的后继置空，将要删除节点的前驱置空
currentNode.previous.next = currentNode.next;
currentNode.next.previous = currentNode.previous;
currentNode.next = null;
currentNode.previous = null;
}
}
//找到最后一个节点
function findLast(){
var currentNode=this.head;
while (currentNode.next!=null) {
currentNode=currentNode.next;
}
return currentNode;
}
function dispReverse(){
var currentNode=this.head;
currentNode=this.findLast();
while (currentNode!=null) {
print(currentNode.element);
currentNode=currentNode.previous;
}
}
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('jgchen', 'Russellville');
cities.insert('yinjun', 'jgchen');
cities.display();
print('---------------');
cities.remove('jgchen');
cities.display();
print('--------------');
cities.dispReverse();
