双向链表

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

class DoublyLinkedList {
  head = null
  tail = null
  length = 0

  append(data) {
    const newNode = new DoublyLinkNode(data)
    if (this.length === 0) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
  }

  insert(position, data) {
    if (position < 0 || position > this.length) return new Error('索引越界')
    const newNode = new DoublyLinkNode(data)
    if (position === 0) {
      if (this.head === null) {
        this.head = newNode
        this.tail = newNode
      } else {
        newNode.next = this.head
        this.head.prev = newNode
        this.head = newNode
      }
    } else if (position === this.length) {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    } else {
      let index = 0
      let currentNode = this.head
      let prevNode = null
      while (index < position) {
        prevNode = currentNode
        currentNode = currentNode.next
        index++
      }
      newNode.next = currentNode
      currentNode.prev = newNode

      newNode.prev = prevNode
      prevNode.next = newNode
    }
    this.length++
    return newNode
  }

  removeAt(position) {
    if (position < 0 || position >= this.length) return null
    if (position === 0) {
      if (this.length === 1) {
        this.head = null
        this.tail = null
      } else {
        this.head = this.head.next
        this.head.prev = null
      }
    } else if (position === this.length - 1) {
      this.tail.prev.next = null
      this.tail = this.tail.prev
    } else {
      let index = 0
      let currentNode = this.head
      let prevNode = null
      while (index < position) {
        prevNode = currentNode
        currentNode = currentNode.next
        index++
      }
      // 跳过当前节点的链接，即将前一个节点跟下一个节点互相链接，并断开当前节点与前后节点的链接

      // prevNode的next指向当前节点的下一个节点
      // 断开当前节点的prev链接
      currentNode.prev = null
      prevNode.next = currentNode.next
      
      // 当前节点的下一个节点的prev指向prevNode
      // 断开当前节点的next链接
      currentNode.next.prev = prevNode
      currentNode.next = null
    }
    this.length--
  }

  remove(data) {
    this.removeAt(this.findIndex(data))
  }

  update(position, data) {
    this.removeAt(position)
    this.insert(position, data)
  }

  findIndex(data) {
    let index = 0
    let currentNode = this.head
    while(currentNode) {
      if (currentNode.data === data) return index
      currentNode = currentNode.next
      index++
    }
    return -1
  }

  size() {
    return this.length
  }
}