链表 --js实现

1.链表的概念

列表存储的是有序元素集合，不同于数组，链表的中的元素在内存中并不是连续放置的。每个元素是由一个存储元素本身的节点和指向下一个元素的引用(指针或链接)组成。
通过的这个概念的我们可以分析出
某一个节点大概是:

node:{
value:xxx,
next:node
}

除此之外还有length保存着链表的长度,head表示第一个元素在哪里
所以添加元素

2.1添加元素

function LinkedList(){
  let 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
    if(head === null) {//列表中第一个节点
      head = node
    }else{
      current = head
      // 循环列表直到找到最后一项
      while(current.next){
        current = current.next
      }
      current.next = node
    }
    length++
  }
  this.print = function(){
  console.log(head)
  }
}

image.png

2.2移除某一个位置

在数组中删除某一项元素是:把第n项的值删除，第n+1项以及n+1项之后的项全部向前移动一位
在链表中删除某一项元素是:把第n-1项的next指向n+1，则自动把第n项删除了
代码实现:

this.remove=function(position){
  if(position>=0&&position<length){
      let current = head
      let prev
  
      if(position===0){
      head = current.next 
      }else{
      let index = 0  
      while(index<position){
          prev = current  //现任变前任
          current = current.next //后任变现任
          index++
        }
       prev.next = current.next // 断掉current
       length--
       return current
      }
    }else{
    return null
   }
}

2.3向指定位置插入新项

与2.2类似，首先需要判断这个位置是不是越界的，index不能在length之外，和0之前，然后通过循环找到position。

this.insert=function(position,element){
  if(position<=length&&position>=0){
      let current,prev,index = 0
      let node = new Node(element)
      if(position === 0){ // 位置为head则只需要改变head的值，和指针
        current = head
        head = node
        head.next = current
      }else{
        current = head
        while(index<position){
          prev = current
          current = current.next
          index++
        }
        prev.next = node
        node.next = current
        length++
        return node
      }
    }else{
      return null
    }  
}

最后:所有方法的实现

function LinkedList () {
  let 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
    if (head === null) {//列表中第一个节点
      head = node
    } else {
      current = head
      // 循环列表直到找到最后一项
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
    length++
  }
  // 向列表的特定位置插入一个新的项
  this.insert = function (position, element) {
    if (position <= length && position >= 0) {
      let current, prev, index = 0
      let node = new Node(element)
      if (position === 0) { // 位置为head则只需要改变head的值，和指针
        current = head
        head = node
        head.next = current
      } else {
        current = head
        while (index < position) {
          prev = current
          current = current.next
          index++
        }
        prev.next = node
        node.next = current
        length++
        return node
      }
    } else {
      return null
    }
  }
  // 从列表的特定位置移除一项
  this.removeAt = function (element) {
    let index = 0
    let current = head
    let prev
    while (current) {
      prev = current
      current = current.next
      if (current.element === element) {
        prev.next = current.next
        return current
      }
      current = current.next
      index++
    }
    return null
  }
  // 从列表中移除一项
  this.remove = function (position) {
    if (position >= 0 && position < length) {
      let current = head
      let prev

      if (position === 0) {
        head = current.next
      } else {
        let index = 0
        while (index < position) {
          prev = current  //现任变前任
          current = current.next //后任变现任
          index++
        }
        prev.next = current.next // 断掉current
        length--
        return current
      }
    } else {
      return null
    }
  }
  // 返回元素在列表中的索引
  this.indexOf = function (element) {
    let index = 0
    let current = head
    while (current) {
      if(current.element === element){
         return index

      } 
      current = current.next
      index++
    }
    return null
  }
  // 如果链表不存在任何元素返回true
  this.isEmpty = function () {
    if (head) {
      return false
    }
    return true
  }
  // 返回列表包含的元素个数
  this.size = function () {
    return length
  }
  // 
  this.getHead = function () {
    return head
  }
  this.toString = function () {
    return this.toString()
  }
  this.print = function () {
    console.log(head)
  }
}