链表

定义

链表是由一组节点组成。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。

设计一个基于对象的链表

1. Node类

function Node(element) {
  this.element = element;
  this.next = null;
}

2. LinkedList类

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

实现方法

我们首先实现 insert 方法， 但是实现insert方法之前可以先实现 find 方法，先找到已知节点，然后将新节点插入到已知节点后：

function find(item) {
    var currentNode = this.head;
    while(currentNode.element!=item) {
        currentNode = currentNode.next
    }
    return currentNode;
}

现在就可以实现insert方法了：

function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

展示所有数据的 display 方法：

function display() {
    var currentNode = this.head;
    while(currentNode != null) {
        console.log(currentNode.element);
        currentNode = currentNode.next;
    }
}

测试我们写的方法：

var cities = new LList();
cities.display();
cities.insert('second', 'head');
cities.insert('third', 'second');
cities.insert('second-third', 'second');
cities.display();

结果

我们似乎还少写了一个 remove 方法，从链表中删除节点时，需要找到待删除节点前面的节点。找到这个节点后修改它的 next 属性，使其不再指向待删除的节点，而是指向待删除节点的下一个节点。我们可以先写一个findprevious方法：

function findPrevious(item) {
    var currentNode = this.head;
    while(currentNode.next != null && currentNode.next.element != item) {
        console.log(currentNode.next);
        currentNode = currentNode.next;
    }
    return currentNode;
}

所以，现在可以写remove 方法了：

function remove(item) {
    var currentNode = this.findPrevious(item);
    if (currentNode.next != null) {
        currentNode.next = currentNode.next.next;
    }
}

现在可以来测试下我们写的remove 方法了。

cities.remove('second');
console.log('删除second后:');
cities.display();

结果

双向链表

首先我们需要给Node类增加一个 previous 属性：

function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
}

由于现在节点多了一个 previous 属性，所以需要改造下 insert 方法：

function insert(newElement, item) {
    var currentNode = this.find(item);
    var newNode = new Node(newElement);
    newNode.previous = currentNode;
    newNode.next = currentNode.next;
    currentNode.next.previous = newNode;
    currentNode.next = newNode;
}

双向链表的 remove 方法比单向链表的效率更高，因为不需要再查找前驱节点了，首先要在链表中查找待删除的节点，然后再设置该节点前驱节点的 next 属性，使其指向待删除节点的后驱节点就好了。

function remove(element) {
    var currentNode = this.find(element);
    if (currentNode.next != null) {
        currentNode.previous.next = currentNode.next;
        currentNode.next.previous = currentNode.previous;
        currentNode.next = null;
        currentNode.previous = null;
    }
}

最后我们再实现一个反向打印链表的方法，就基本完成了链表的基本方法实现，实现这个方法之前我们需要实现一个 findLast 方法来查找链表最后一个节点：

findLast() {
    var currentNode = this.head;
    while(currentNode.next != null)  {
        currentNode = currentNode.next;
    }
    return currentNode;
}

这时候我们就可以很容易实现反向打印链表了：

function dispReverse() {
    var lastNode = this.findLast();
    while(lastNode.previous != null) {
        console.log(lastNode.element);
        lastNode = lastNode.previous;
    }
    console.log(lastNode.element);
}