[数据结构与算法]JavaScript【数据结构与算法】(二) 单向链表

个人博客地址：https://tao-yuhan.gitee.io/tyhanblog/

链表的优势

• 链表中的元素在内存中不必是连续的空间
• 链表的每一个元素由一个存储元素本身的节点和一个指向下一个元素的引用
• 链表在创建的时候不需要确定大小，大小可以无线延伸下去

单向链表的一些基本操作

链表得有一个head指向第一个节点，其次每个节点中有data和next,next指向下一个节点

• append(element): 在尾部添加一个新的项
• insert(position,ele): 向链表的特定位置插入一个新的项
• get(position): 获取对应位置的元素
• indexOf(ele): 返回元素在链表中的索引，如果没有该元素则返回-1
• update(position，ele): 修改某个位置的元素
• removeAt(position): 从列表的特定位置移除一项
• remove(ele): 从链表中移除一项
• isEmpty(): 是否为空
• size(): 链表长度
• toString(): 输出元素的值

链表操作的封装

链表的基本实现

function LinkedList() {
 this.head = null
 this.length = 0

 //节点类
 function Node(data) {
   this.data = data
   this.next = null
 }
}

1.append

LinkedList.prototype.append = function (data) {
  //先创建这个节点
  let newNode = new Node(data)
  //如果添加的为第一个节点,将head指针指向该节点的data
  if (this.length == 0) {
    this.head = newNode
  } else {
    let current = this.head
    while (current.next) {
      //找下一个
      current = current.next
    }
    //最后节点的next指向新的节点
    current.next = newNode
  }
  this.length++
}

2.insert

LinkedList.prototype.insert = function (position, data) {
  //对position进行越界判断和长度判断
  if (position < 0 || position > this.length) return false

  //创建节点
  let newNode = new Node(data)
  //如果是插入在第一个
  if (position == 0) {
    newNode.next = this.head
    this.head = newNode
  } else { //如果不是插入第一个
    let index = 0 //自己定义一个位置
    let current = this.head //先让current为第一个节点
    while (index++ < position - 1) { //3
      current = current.next
    }
    newNode.next = current.next
    current.next = newNode
  }
  this.length++
  return true
}

3.get

LinkedList.prototype.get = function (position) {
  //对position进行越界判断和长度判断
  if (position < 0 || position >= this.length) return false

  //创建一个空的字符用来接收
  let str = ""
  let index = 0 //自己定义一个位置
  let current = this.head //先让current为第一个节点
  while (index++ < position) {
    current = current.next
  }
  str += current.data
  return str
}

4.indexOf

LinkedList.prototype.indexOf = function (data) {
  //从第一个开始找
  let index = 0
  //一个链表中可能存在几个相同的几个值，将其位置全部存放在一个数组中
  let arr = []
  let current = this.head
  while (index < this.length) {
    //符合的位置全部push到数组中
    if (current.data == data) {
      arr.push(index)
    }
    current = current.next
    index++
  }
  // return index
  // 循环结束后再根据数组中的数来做判断
  if (arr.length == 0) {
    return -1
  } else if (arr.length == 1) { //如果只有一个的话就不返回数组，直接返回这个位置
    return arr[0]
  } else {
    return arr
  }
}

5.update

LinkedList.prototype.update = function (position, data) {
  //对position进行越界判断和长度判断
  if (position < 0 || position >= this.length) return false

  let index = 0 //自己定义一个位置
  let current = this.head //先让current为第一个节点
  while (index++ < position) {
    current = current.next
  }
  current.data = data
}

6.removeAt

LinkedList.prototype.removeAt = function (position) {
  //对position进行越界判断和长度判断
  if (position < 0 || position >= this.length) return false

  let index = 0 //前一个的位置
  let current = this.head //先让current为第一个节点
  //如果删除的是第一个节点
  if(position === 0) {
    this.head = this.head.next 
  }else {
    while (index++ < position - 1) {//找到要删除节点的前一个节点
      current = current.next
    }
        /**
   * 将链表断开
   */
    let mid = current.next
    current.next = mid.next
    mid.next = null
  }
  this.length -= 1
  return true
}

7.remove

LinkedList.prototype.remove = function(ele) {
  //直接调用indexOf()与removeAt()
  const position = this.indexOf(ele)
  console.log(position);
  if(position === -1) {
    return false
  }else if(position instanceof Array) {
    position.forEach((item) => {
      this.removeAt(item)
      this.remove(ele)
    })
  }else {
    this.removeAt(position)
  }
  return true
}

8.toString

LinkedList.prototype.toString = function () {
 let current = this.head
 let listString = ""
 while (current) {
   listString += current.data + " "
   current = current.next
 }
 return listString
}

完整代码实现

function LinkedList() {
  this.head = null
  this.length = 0

  //节点类
  function Node(data) {
    this.data = data
    this.next = null
  }

  //1.追加方法
  LinkedList.prototype.append = function (data) {
    //先创建这个节点
    let newNode = new Node(data)
    //如果添加的为第一个节点,将head指针指向该节点的data
    if (this.length == 0) {
      this.head = newNode
    } else {
      let current = this.head
      while (current.next) {
        //找下一个
        current = current.next
      }
      //最后节点的next指向新的节点
      current.next = newNode
    }
    this.length++
  }

  //2.toString方法
  LinkedList.prototype.toString = function () {
    let current = this.head
    let listString = ""
    while (current) {
      listString += current.data + " "
      current = current.next
    }
    return listString
  }

  //3.insert方法
  LinkedList.prototype.insert = function (position, data) {
    //对position进行越界判断和长度判断
    if (position < 0 || position > this.length) return false

    //创建节点
    let newNode = new Node(data)
    //如果是插入在第一个
    if (position == 0) {
      newNode.next = this.head
      this.head = newNode
    } else { //如果不是插入第一个
      let index = 0 //自己定义一个位置
      let current = this.head //先让current为第一个节点
      while (index++ < position - 1) { //3
        current = current.next
      }
      newNode.next = current.next
      current.next = newNode
    }
    this.length++
    return true
  }

  //4.get方法
  LinkedList.prototype.get = function (position) {
    //对position进行越界判断和长度判断
    if (position < 0 || position >= this.length) return false

    //创建一个空的字符用来接收
    let str = ""
    let index = 0 //自己定义一个位置
    let current = this.head //先让current为第一个节点
    while (index++ < position) {
      current = current.next
    }
    str += current.data
    return str
  }

  //5.update方法
  LinkedList.prototype.update = function (position, data) {
    //对position进行越界判断和长度判断
    if (position < 0 || position >= this.length) return false

    let index = 0 //自己定义一个位置
    let current = this.head //先让current为第一个节点
    while (index++ < position) {
      current = current.next
    }
    current.data = data
  }

  //6.indexOf方法
  LinkedList.prototype.indexOf = function (data) {
    //从第一个开始找
    let index = 0
    //一个链表中可能存在几个相同的几个值，将其位置全部存放在一个数组中
    let arr = []
    let current = this.head
    while (index < this.length) {
      //符合的位置全部push到数组中
      if (current.data == data) {
        arr.push(index)
      }
      current = current.next
      index++
    }
    // return index
    // 循环结束后再根据数组中的数来做判断
    if (arr.length == 0) {
      return -1
    } else if (arr.length == 1) { //如果只有一个的话就不返回数组，直接返回这个位置
      return arr[0]
    } else {
      return arr
    }
  }

  //7.removeAt(position)
  LinkedList.prototype.removeAt = function (position) {
    //对position进行越界判断和长度判断
    if (position < 0 || position >= this.length) return false

    let index = 0 //前一个的位置
    let current = this.head //先让current为第一个节点
    //如果删除的是第一个节点
    if(position === 0) {
      this.head = this.head.next 
    }else {
      while (index++ < position - 1) {//找到要删除节点的前一个节点
        current = current.next
      }
          /**
     * 将链表断开
     */
      let mid = current.next
      current.next = mid.next
      mid.next = null
    }
    this.length -= 1
    return true
  }

  //8.remove()
  LinkedList.prototype.remove = function(ele) {
    //直接调用indexOf()与removeAt()
    const position = this.indexOf(ele)
    console.log(position);
    if(position === -1) {
      return false
    }else if(position instanceof Array) {
      position.forEach((item) => {
        this.removeAt(item)
        this.remove(ele)
      })
    }else {
      this.removeAt(position)
    }
    return true
  }
}