JS_数据结构——链表的实现及增、删、改、查

链表可以说是数据结构中经典中的经典，链表实现相比于栈和队列要复杂一些，他不仅包含自己本身，还指向了它的下一个元素，它的原理这里不再赘述。但有一些理解技巧： 对于一个链表，因为他不是数组，无.length所以要手动设置长度属性每次添加一个元素，length++。此外还要有头节点.

链表想象成一个火车，火车必须要有头，并且对于每个节点都要用辅助类来实例化该节点（想象成一个带链子的车厢）

直接上代码。

var NodeList=function()
{
    //对于一个链表 它有头属性，因为他不是数组了所以有长度属性，并且对于每个节点都要用辅助类来实例化该节点
    var head=null
    var length=0
    var initNode=function(element)
    {
        this.element=element
        this.next=null

    }
    // 初始化链表
    this.append=function(element)
    {
        var NodeListObj=new initNode(element)  //将新增加的元素初始化为链表结构
        
        if(head==null)
        {
            head=NodeListObj
        }
        else{
            var current=head
            while(current.next)//将current移动到末尾
            {
                current=current.next
            }
            current.next=NodeListObj 
        }
        length++

    }
    // 像固定位置插入
    this.insert=function(element,position)
    {
    
        if(position>-1&&position<length){ //越界规定
            var node=new initNode(element)
        
            if(position==0)
            {
               var current=head
               head=node
               head.next=current

            }
            else{
                var pre=null
                var current=head
                for(var i=0;i<position;i++)
                {
                    pre=current
                    current=current.next
                }
                pre.next=node
                node.next=current

            }
            length++
        
    }
    }
    // 删除某个位置的元素
    this.removeAt=function(position)
    {
        if(position>-1&&position<length)
        {
            if(position==0)
            {
               var current=head
               head=current.next 
            }
            else{
                var pre=null
                var current=head
                for(var i=0;i<position;i++)
                {
                    pre=current
                    current=current.next
                }
                pre.next=current.next
              

            }
            length--
            return current
        }
        return null
    }
    //删除某个给定的元素
    this.remove=function(element)
    {
        return(this.removeAt(this.indexOf(element)))
    }
    // 改变某个固定位置元素的值
        this.changeAt=function(position,element)
    {

        
        if(position>-1&&position<length)
        {
            if(position==0)
            {
                head.element=element
                return head
            }
            else{
                var current=head
                for(var i=0;i<position;i++)
                {
                    current=current.next
                }
                current.element=element
            }
            return current
        }
    

    }
    //改变某个值的值
    this.change=function(oldelement,newelement)
    {
       
        return( this.changeAt(this.indexOf(oldelement),newelement))
    }
    //查找某个元素的位置
    this.indexOf=function(element)
    {
        var index=0
        var current=head
        while(current)
        {
            if(current.element==element)
            {
                return index
            }

            index++
            current=current.next
        }
        return -1


    }
    this.isEmpty=function()
    {
        return length==0
    }
    this.size=function()
    {   
        return length

    }
    this.getHead=function()
    {
        if(length>0)
        {
        return head
    
    }

}
    
}

要注意的一个技巧是代码复用！如删除固定位置的元素 改变固定位置的元素