JavaScript单向链表的实现

javascript实现单向链表

• 单向链表简介
  • 链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有的语言称为指针或连接）组成。类似于火车头，一节车厢载着乘客（数据），通过节点连接另一节车厢。
    
• head属性指向链表的第一个节点；
• 链表中的最后一个节点指向null；
• 当链表中一个节点也没有的时候，head直接指向null；
  

  数组与链表的对比

  数组的缺点

• 数组的创建通常是申请一段连续的内存空间,而且大小是固定的 当数组超出原长度时 会进行扩容 一般情况下为申请一个更大的数组 然后将原数组复制过去
• 数组的插入成本很高 因为数组会进行大量的位移来进行数据的存储位置的变更

  链表的优点

• 链表在存储空间中 不再是一段连续的空间 而是任意的位置存储链表中的数据
• 链表的大小可以随意扩容
• 链表在进行插入和删除数据时 时间复杂度可以到O(1),相比较于数组效率高到不知哪里去了

  链表的缺点

• 在访问链表的数据时 只能从头进行访问 无法根据下标值来进行读取数据
• 可以轻松的到达下一个节点 但是回到之前节点时很难的

链表中的常见操作

• append 链表中增加一个新的项
• insert(position,data) 向链表中特定位置增加一个香
• removeAt(position)删除链表中特定位置的项
• remove(data)删除链表中该项
• update(position,data)将链表中特定位置的项改变内容
• indexOf(data)查找在链表中特定的项的位置
• get(position)获得特定位置的项的内容
• isEmpty()返回链表是否为空
• size()返回链表的长度
• toString()返回链表的toString方法

封装单向链表

• 先创建单向链表类linklist,并且添加基本属性 再添加链表的各种方法

fuction llinklixt(){
    <!-- 封装内部节点 -->
    fuction Node(data){
        this.data=data
        this.next=null
    }
    <!-- 属性 -->
    this.length=0
    this.head=null

• 实现append方法

  linklixt.prototype.append=function(data){
         var node=new Node(data)
         //链表长度为0的情况
         if(this.length==0){
             this.head=node
         }else{//不为0的情况
             var current=this.head
             while(current.next){
                 current=current.next
             }
             current.next=node
         }
         this.length+=1
     }

• 首先创建一个新的node 长度为0时 直接将this.head的指针指向node

• 不为0时 创建一个current值设置为this.head 并且通过while遍历 每遍历一次 current的值就指向下一位 直到current的next值指向null 也就是最后一位 此时 将current的next的值赋值给node

• 实现toString方法

  linklixt.prototype.toString=function(){
           var current=this.head
           var retstr=''
           while(current){
               retstr+=current.data+' '
               current=current.next
           }
           return retstr
       }

• 非常简单 不做分析

• insert方法的实现

  linklixt.prototype.insert=function(position,data){
         if(position < 0 || position > this.length) return false
         var node=new Node(data)
         if(position==0){
             node.next=this.head
             this.head=node
         }else{
             var index=0
             var current=this.head
             var previous=null
             while(index++<position){
                 previous=current
                 current=current.next
                 
             }
             node.next=current
             previous.next=node
         }
         this.length+=1
         return true
         
         }

• insert方法的实现 当poition为o时 直接

  • node.next=this.head
  • this.head=node

• 当position不为0时首先定义两个变量previous和curent分别指向需要插入位置的前一个节点和后一个节点

  • 然后，通过：newNode.next = current，改变指向3
  • 最后，通过：previous.next = newNode，改变指向4

• get方法的实现

  linklixt.prototype.get=function(position){
             // var newnode=new Node()
             // 1.越界判断
             if(position<0||position>=this.length) return null
             // 2.获取对应date
             var current=this.head
             var index=0
             while (index++ < position) {
                 current=current.next
                 
             }
             return current.data
         }

• indexOf方法的实现

  linklixt.prototype.indexOf=function(data){
              var index=0
              var current=this.head
  
              while (current) {
                  if(current.data==data){
                      return index
  
                  }
                  index+=1
                  current=current.next
                  
              }
              // 没有找到 返回-1
              return -1;
  
          }

• update方法的实现

  linklixt.prototype.update=function(position,data){
              // 2.越界判断
              if(position<0 || position>=this.length) return false
              // 2.查找正确的节点
              var current=this.head
              var index=0
              while (index<position) {
                  current=current.next
                  index++
                  
              }
              // 3.将数据更改
              current.data=data
              return true
  
          }

• removeAt方法的实现

  linklixt.prototype.removeAt=function(position){
                // 1.越界判断
                if(position<0  || position>=this.length) return false
  
                // 2,进行移除
                if(position==0){
                    this.head=this.head.next
                }else{
                    var index=0
                    var previous=null
                    var current=this.head
                    while ((index++ < position)) {
                        previous=current
                        current=current.next
                        
                    }
                    // 前一个结点的next指向 current的next
                    previous.next=current.next
                 
                    
  
  
                }
                this.length-=1
                    return true
            }

• 实现思路其实和insert方法差不多 不懂得多看看insert方法的实现就懂了,这里不做详解 等哪天有时间了再来写吧

• remove方法的实现

  linklixt.prototype.remove=function(data){
                // 1.先获取data再元素中的位置
                var position=indexOf(data)
                // 2.将获取到的位置的元素删除
                return this.removeAt(position)
  
  
            }

• 就是调用前两种方法 先获取到具体位置 再将该位置的元素删除

• isEmpty方法的实现

  linklixt.prototype.isEmpty=function(){
                 return this.length==0;
             }

• size方法的实现

  li1.prototype.length=function(){
                 return this.length
             }