1.js-链表

数组缺点：（大多数语言中）数组的大小是固定的，从数组的起点或者中间插入或者一处项的成本太高，因为需要移动元素（js中的array类可以帮我们做这些事情，但背后的情况同样是这样的）
链表：1.存储有序的的元素集合，不同于数组，链表中的元素在内存中不是连续放置的。每个元素有一个存储元素本身的节点和一个指向下一个元素的引用（指针或链接）2.添加或移除元素不需要移动其他元素 3.遍历的时候需要从头开始迭代

//代码实现
function LinkedList(){
    let head = null;
    let length = 0;
    let Node = function(val){
        this.val = val;
        this.next = null;
    }
    this.append = function(val){
        let node  = new Node(val),current;
        if(length === 0){
            head = node;
        }else{
            current = head;
            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        length++;
    }
    this.remove = function(index){
        if(index < -1 || index >= length){
            return;
        }else{
            let current = head,previous = null;
            if(index === 0){
                head = current.next
            }else{
                for(let i = 0; i < index;i++){
                    previous = current;
                    current = current.next;
                }
                //当前移除的元素会被丢弃在计算机内存中，等着被垃圾回收器清除
                previous.next = current.next;
            }
            length--;
            return current.val
        }
    } 
    this.insert = function(index,val){
        if(index < -1 || index >= length ){
            return;
        }else{
            let current = head,previous = null;
            let node = new Node(val)
            if(index === 0){
                node.next = current;
                head = node;
            }else{
                for(let i = 0; i < index; i++){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length++;
        }
    }
    this.isEmpty = function(){
        return length === 0
    }
    this.toString = function(){
        let current = head,str = "";
        while(current){
            str += current.val+",";
            // console.log(current.val)
            current = current.next;
        }
        return str
    }
    this.getHead = function(){
        return head;
    }
}
let link = new LinkedList();
link.append(1)
link.append(4)
link.append(5)
link.append(6)
console.log(link.remove(0))
link.insert(0,1)
link.insert(1,2)
console.log(link.toString())
//将文件导出
module.exports =  {
    LinkedList:LinkedList
} 

双向链表优点：解决单向链表中获取当前节点前驱需要从头遍历的问题