[数据结构与算法]js-数据结构-链表

个人博客： http://xiaolan1.icu

一、链表

1、概念

??链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。(即在数据逻辑上是线性的)，它的每个结点由两个域组成：①存储数据元素的数据域。②存储下一个结点地址的指针域。

2、特点

??①和线性表相比，链表在添加和删除结点上的效率更高，只需要修改指针信息即可完成操作，不用像线性表(数组)那样移动元素。链表操作的时间复杂度仅为O(1)。

??②因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。

??③链表的长度在理论上是无限的，可以动态变化长度。

??④哈希表是基于链表来实现的

二、链表类型

1、单链表

function LinkedList(){
    let Node=function (element){
        this.element = element
        this.next = null
    }
    
    let head = new Node('head')
    
    //查找返回最后一个节点
    this.findLast = function (){
        let currNode = head
        while (currNode.next){
            currNode = currNode.next
        }
        return currNode
    }
    
    //在尾部增加元素
    this.append = function (element){
        let newNode = new Node(element)
        let currNode = this.findLast()
        if(!head){
            head = newNode	//头节点为空的情况
        }else{
            currNode.next = newNode
        }
    }
    
    //查找item元素
    this.find = function(item){
        let currNode = head
    	while(currNode.next&&currNode.element!=item){
            currNode = currNode.next
        }
        return currNode
    }
    
    //插入元素
    this.insert = function(item, element){
        let itemNode = this.find(item)
       
        if(!itemNode){
            return 
        }
        let newNode = new Node(element)
        
        newNode.next = itemNode.next
        itemNode.next = newNode
    }
    
    //删除节点
    this.remove = function(item){
       let currNode = head
       while(currNode.next.element!==item){
           if(!currNode.next){
               return 
           }
           currNode = currNode.next
       }
        currNode.next=currNode.next.next
    }
      //打印链表元素
      this.display = function () {
          let result = []
          let currNode = head
          while (currNode ) {
              result.push(currNode.element)
              currNode = currNode.next
          }
          return result
      }
}


//测试部分：
let myList = new LinkedList()
let arr = [1, 4, 5, 2, 3]
for (i of arr) {
    myList.append(i)
}
console.log(myList.display());	//['head', 1, 4, 5, 2, 3]
console.log(myList.find(5));    //Node{element:5,next:Node}
console.log(myList.findLast()); //Node{element:3,next:null}
console.log(myList.remove(4));
console.log(myList.display());  //["head", 1, 5, 2, 3]

2、双链表

function doubleLinkedList(){
    let Node = function (element){
        this.element = element
        this.next = null
        this.previous = null
    }
    let head = new Node('head')
    
    //查找最后一个节点
    this.findLast = function(){
        let currNode = head
        while(currNode.next){
            currNode = currNode.next
        }
        return currNode
    }
    
    //查找特定元素节点
    this.find = function(item){
        let currNode = head
        while(currNode.element != item){
            if(currNode.next == null){
                return 
            }
            currNode = currNode.next
        }
        return currNode
    }
    
    //在某节点后插入一个新节点
    this.insert = function(item,element){
        let currNode = this.find(item)
        let newNode = new Node(element)
        
        if(currNode = null){
            return
        }
        if(currNode.next == null){
            currNode.next = newNode
            newNode.previous = currNode
        }else{
            newNode.next = currNode.next
            currNode.next.previous = newNode
            currNode.next = newNode
            newNode.previous = currNode
        }
    }
    
    //在尾结点插入元素
    this.append = function(element){
        let newNode = new Node(element)
        let currNode =this.findLast()
        if(!head){
            head = newNode
        }else{
            currNode.next = newNode
            newNode.previous =currNode
        }
    }
	
    //删除某节点
    this.remove = function(item){
        let currNode = this.find(item)
        if(!currNode){
            return
        }
        if(currNode.next != null &&  currNode.previous != null){  //该节点前后节点都不为空
        	currNode.previous.next = currNode.next
        	currNode.next.previous = currNode.previous
        	currNode.next = null
        	currNode.previous = null
        }else if(currNode.previous == null){   //该节点的前一节点为空
            head = currNode.next
            currNode.next.previous = null
            currNode.previous = null
        }else if(currNode.next == null){     //该节点的后一节点为空
            currNode.previous.next = null
            currNode.previous = null
        }
    }
     //打印链表元素
     this.display = function () {
          let result = []
          let currNode = head
          while (currNode) {
              result.push(currNode.element)
              currNode = currNode.next
          }
          return result
      }
}

//测试部分
let myList = new doubleLinkedList()
let arr = [1, 4, 5, 2, 3]; 
for (i of arr) {
    myList.append(i)
}
console.log(myList.display());  //['head', 1, 4, 5, 2, 3]
console.log(myList.find(5))		//Node{element:5,next:Node,previous:Node}
console.log(myList.remove(4));
console.log(myList.display());	//["head", 1, 5, 2, 3]