数据结构篇——单向链表

在JavaScript中，由于数组被实现为对象，与其他语言相比效率很低。当我们发觉使用数组时运行效率很慢，那么就应该考虑链表。

链表是由一组节点组成的集合，每个节点都使用一个对象的引用来指向它后面的节点，这个指向后面节点的引用就被称为链。

数组和链表的区别：

• 数组靠位置来引用，链表靠节点之间的相互关系来引用

遍历链表时不包含头节点，头节点作为链表的接入点；链表的尾元素指向一个null节点

// 基于链表都是由节点组成的，我们需要定义一个节点类
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){
    let currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到插入的相对点后，就可以插入节点了
function insert(newElement, item){
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

// 展示链表所有节点(不显示头节点)
function display(){
    let currNode = this.head;
    while (currNode.next != null){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

// 从链表中删除节点
// 首先要找到待删除节点的前一个节点，让这个节点的next属性不再指向待删除节点，而是指向待删除节点的下一个节点
function findPrevious(item){
    let currNode = this.head;
    while(currNode.next != null && currNode.next.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

// 找到待删除节点的前一个节点后，就可以删除节点了
function remove(item){
    let prevNode = this.findPrevious(item);
    if(prevNode.next != null){
        // prevNode.next = item.next; 这样写是错的，因为item是节点的elment属性的值，并不是节点本身
        prevNode.next = prevNode.next.next;
    }
}

// 测试代码
let llist = new LList();
llist.insert("a", "head");
llist.insert("b", "a");
llist.insert("c", "b");
llist.insert("d", "c");
llist.display();
llist.remove("c");
llist.display();