链表

class LinkNode {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  head = null
  length = 0

  // 向链表尾部追加数据
  append(data) {
    const newNode = new LinkNode(data)
    // 链表为空，直接更新首节点
    if (this.length === 0) {
      this.head = newNode
    } else {
    // 链表不为空，遍历链表直到链表尾部(node.next为null)
      let currentNode = this.head
      while (currentNode.next) {
        currentNode = currentNode.next
      }
      currentNode.next = newNode
    }
    this.length++
  }

  // 在链表指定位置插入数据
  insert(position, data) {
    if (position < 0 || position > this.length) return new Error('索引越界')
    const newNode = new LinkNode(data)
    // 索引为0，直接更新首节点
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else {
      // 索引大于0，则以索引为终点遍历链表；
      // 定义当前节点的上一个节点，遍历过程中不断更新当前节点，
      // 遍历结束后，将新插入的节点next引用指向当前节点，上一个节点next则指向新插入的节点，以此可得到 上个节点->新节点->旧的'当前节点'，则新节点成功插入
      let index = 0
      let currentNode = this.head
      // 当前节点的上一个节点
      let prevNode = null
      while(index < position) {
        prevNode = currentNode
        currentNode = currentNode.next
        index++
      }
      newNode.next = currentNode
      prevNode.next = newNode
    }
    this.length++
    return newNode
  }

  // 移除指定位置的节点
  removeAt(position) {
    if (position < 0 || position > this.length) return new Error('索引越界')
    let currentNode = this.head
    // 索引为0，将当前的首节点替换为下一个节点
    if (position === 0) {
      this.head = currentNode.next
    } else {
      // 索引大于0，以索引为终点遍历链表；
      // 定义当前节点的上一个节点，将上一个节点的nex指向当前节点的next，则相当于在链表中移除了当前节点(因为链表中已无法再触达到当前节点,next引用已断开)
      let index = 0
      let prevNode = null
      while(index < position) {
        prevNode = currentNode
        currentNode = currentNode.next
        index++
      }
      prevNode.next = currentNode.next
    }
    // 断开被删除节点的链接；
    // tips: 此处可以不删除，为了避免垃圾回收机制失败后不能继续回收next引用的后续节点，删除更加安全
    currentNode.next = null
    this.length--
    return currentNode
  }

  // 删除指定数据的节点
  remove(data) {
    this.removeAt(this.findIndex(data))
  }

  // 更新链表指定位置的数据
  update(position, data) {
    if (position < 0 || position > this.length) return new Error('索引越界')
    if (position === 0) {
      this.head.data = data
      return
    }
    let index = 0
    let currentNode = this.head
    while(index < position) {
      currentNode = currentNode.next
      index++
    }
    currentNode.data = data
    return currentNode
  }

  // 查询数据在链表中的位置
  findIndex(data) {
    let index = 0
    let currentNode = this.head
    while(currentNode) {
      if (currentNode.data === data) return index
      currentNode = currentNode.next
      index++
    }
    return -1
  }

  // 根据索引查找链表中的数据
  findByIndex(position) {
    if (position < 0 || position > this.length) return new Error('索引越界')
    if (position === 0) {
      return this.head.data
    } else {
      let index = 0
      let currentNode = this.head
      while(index < position) {
        currentNode = currentNode.next
        index++
      }
      return currentNode?.data || null
    }
  }

  size() {
    return this.length
  }

  isEmpty() {
    return this.length === 0
  }

  // 以字符串形式输出链表数据
  toString() {
    let currentNode = this.head
    let res = ''
    while (currentNode) {
      res += currentNode.data + '->'
      currentNode = currentNode.next
    }
    return res
  }
}