链表

• 数组不是组织数据的最佳结构
• 在做删除和插入操作的时候我们需要将其它的元素前移/后移，这样执行效率会过低
• javascript 的数组被实现成了对象，与其他语言数组相比，效率低了很多
• 除了对数据的随机访问，链表几乎可以用在任何可以使用以为数组的地方

单向链表

// singleLinkedList
function Node (element) {
    this.element = element;
    this.next = null;
}
function LList () {
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

function find (item) {
    // 查找
    var currNode = this.head;
    while (currNode.element !== item) {
        currNode =currNode.next;
    }
    return currNode;
}
function insert (newElement, item) {
    // 插入
    var newNode= new Node(newElement);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
}
function display (){
    // 遍历
    var currNode = this.head;
    while(currNode.next !== null) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}
function findPrevious (item) {
    var currNode = this.head;
    while (currNode.next !== null && currNode.next.element !== item) {
        currNode = currNode.next;
    }
    return currNode;
}

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

var cities = new LList();
cities.insert('first', 'head');
cities.insert('second', 'first');
cities.insert('thrid', 'second');
cities.display();
console.log('===================')
cities.remove('second');
cities.display();

双向链表

// doubleLinkedList
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.display = display;
    this.remove = remove;
    this.displayReverse = displayReverse;
    this.findLast = findLast;
}
// 查找
function find (item) {
    var currNode = this.head;
    while (currNode.element !== item) {
        currNode = currNode.next
    }
    return currNode;
}
// 插入
function insert (newElement, item) {
    var newNode = new Node(newElement);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    newNode.previous = currNode;
    currNode.next = newNode;
    if (!(newNode.next === null)) {
        newNode.next.previous = newNode;
    }
}
// 遍历
function display () {
    var currNode = this.head;
    console.log('遍历')
    while (currNode.next !== null) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
    console.log('== end ==')
}
// 删除
function remove (item) {
    var currNode = this.find(item);
    if (!(currNode.next == null)) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    } else {
        // 尾节点
        currNode.previous.next = null;
        currNode.previous = null;
    }
}
// 查找最后一个节点
function findLast () {
    var currNode = this.head;
    while(!(currNode.next == null)) {
        currNode = currNode.next
    }
    return currNode
}
// 反序
function displayReverse () {
    var currNode = this.findLast()
    console.log('反序:')
    while(!(currNode.previous == null)) {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
    console.log('== end ==')
}

var cities = new LList();
cities.insert('first', 'head');
cities.insert('second', 'first');
cities.insert('thrid', 'second');
cities.display();
cities.remove('second');
cities.display();
cities.displayReverse();