• 數(shù)組不是組織數(shù)據(jù)的最佳結(jié)構(gòu)
• 在做刪除和插入操作的時候我們需要將其它的元素前移/后移，這樣執(zhí)行效率會過低
• javascript 的數(shù)組被實現(xiàn)成了對象，與其他語言數(shù)組相比，效率低了很多
• 除了對數(shù)據(jù)的隨機訪問，鏈表幾乎可以用在任何可以使用以為數(shù)組的地方

單向鏈表

// 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 {
        // 尾節(jié)點
        currNode.previous.next = null;
        currNode.previous = null;
    }
}
// 查找最后一個節(jié)點
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();