JS数据结构与算法之链表

JS数据结构与算法之链表

这是算法系列文章第一篇，参考的是<<javascript数据结构与算法>>

1.链表的概念， 可以去百度查阅 2.链表的实现，简单的链表数据结构操作的

以下是基本的数据结构

function LinkList(){
          
   
    var Node = function(element){
          
   
        this.element = element
        this.next = null
    }
}

链表末尾添加数据

let length = 0;
    let head = null
    this.append = function(element){
          
   
        let node = new Node(element),current
        /* debugger */
        if(head === null){
          
   
            head = node
        }else{
          
   
            //存在head,链表的缺点是必须从头开始遍历
            current = head
            while(current.next){
          
   
                current = current.next;
            }
            current.next = node
        }
        length++
    }

链表中删除数据

this.removeAt = function(pos){
          
   
        /* debugger */
        if(pos>-1 && pos < length){
          
   
            let current = head,
            prev,index = 0
            if(pos === 0){
          
   
                head = current.next
            }else{
          
   
                while(index++ < pos){
          
   
                    prev = current
                    current = current.next
                }
                prev.next = current.next
            }
            length--
            return current.element
        }else{
          
   
            return null
        }
    }

添加链表中的数据

this.insertAt = function(pos,element){
          
   
        
        if(pos>-1 && pos < length){
          
   
            let current = head,
            prev,index = 0
            let node = new Node(element)
            if(pos === 0){
          
   
               node.next = current
               head = node

            }else{
          
   
                while(index++ < pos){
          
   
                    prev = current
                    current = current.next
                }
                node.next = current
                prev.next = node
            }
            length++
            return true
        }else{
          
   
            return null
        }
    }

打印链表中的数据

this.toString1 = function(){
          
   
        let current = head,string=
        while(current){
          
   
            string += current.element + (current.next ? n : )
            current = current.next
        }
        return string
    }
    this.size = function(){
          
   
        return length
    }

查询链表中的数据

this.indexOf = function(element){
          
   
        let current = head,index = -1
        while(current){
          
   
            if(element === current.element){
          
   
                return index
            }
            index++
            current = current.next
        }
        return -1

    }

测试数据

let list = new LinkList()
list.append(15)
list.append(14)
list.append(16)
list.append(19)
list.insertAt(1,20)
console.log(list.toString1());

console.log(list.size());
console.log(list.removeAt(2));