双向链表

链表长度为0
- 索引为0, 设置头部和尾部都为插入节点
- 索引不为0, 抛出异常
链表长度不为0
- 索引为0, 设置头部 ( H ) 的上一位为插入节点 ( I ) , 设置插入节点 ( I ) 的下一位为头部 ( H ) , 设置头部 ( H ) 为插入节点 ( I )
- 索引为链表长度, 设置尾部 ( T ) 的下一位为插入节点 ( I ) , 设置插入节点 ( I ) 的上一位为尾部 ( T ) , 设置尾部 ( T ) 为插入节点 ( I )
- 索引在中间, 取出上个节点 ( P ) , 还有当前节点 ( N ) , 因为需要插入到中间所以把这个当前位置的节点当做下个节点 ( N ) , 把上个节点 ( P ) 的下一个节点改为插入节点 ( I ) , 把当前节点 ( N ) 的上一个节点改为插入节点 ( I ) , 设置插入节点 ( I ) 的上一个节点为上个节点 ( P ) , 设置插入节点 ( I ) 的下一个节点为当前节点 ( N )

get

直接调用 #getNode 函数获取节点然后再调用 getValue 方法即可

indexOf

直接从 0 开始循环, 然后结束是到链表长度, 如果相等就返回当前的索引值, 如果循环结束还没找到那就返回 -1

update

直接取出传入的索引对应的节点, 然后调用 setValue 方法即可

remove

直接通过 indexOf 获取当前值的索引值, 判断是否为 -1 如果是那就返回 false 如果不为 -1 那么就调用 this.removeAt 方法, 把 indexOf 获得的索引值传给他

removeAt

可能遇到的情况:

链表长度为0
- 索引为0, 设置头部和尾部都为 null
- 索引不为0, 抛出异常
链表长度不为0
- 索引为0, 设置头部 ( H ) 的头部的下一个节点 ( N )
- 索引为链表长度 - 1, 设置上个节点 ( P ) 的下一节点为 null , 设置尾部为上个节点 ( P )
- 索引在中间, 取出上个节点 ( P ) , 还有下下个节点 ( N ) , 把上个节点 ( P ) 的下一个节点改为下下个节点 ( N ) , 把下下个节点 ( N ) 的上一个节点设置为上个节点 ( P )

toString

根据传入的参数 direction 来判断是从前往后 ( PN ) 还是从后往前 ( NP ) , 如果是从前往后 ( PN ) 就让开始的 current 是头部, 然后 while 里修改的 current 也就是 getNext() 反之亦然

TS实现

namespace 双向链表 {
  /**
   * 判断是否为-0
   */
  const isNegativeZero = (num: number) => num === 0 && 1 / num < 0

  export class Node {
    #value: any
    #next: Node | null
    #prev: Node | null

    constructor(value: any) {
      this.#value = value
      this.#next = null
      this.#prev = null
    }

    setValue(value: any) {
      this.#value = value
      return value
    }

    getValue() {
      return structuredClone(this.#value)
    }

    setNext(next: Node | null) {
      this.#next = next
      return next
    }

    getNext() {
      return this.#next
    }

    setPrev(prev: Node | null) {
      this.#prev = prev
      return prev
    }

    getPrev() {
      return this.#prev
    }
  }

  export class DoublyLinkedList {
    #head: Node | null = null
    #tail: Node | null = null
    #length = 0

    #getNode(index: number) {
      const getNode = (index: number) => {
        if (!isNegativeZero(index) && index >= 0) {
          let current: Node | null = this.#head
          for (let i = 0; i < index; i++) {
            if (current === null) return current
            current = current.getNext()
          }
          return current
        } else {
          let current: Node | null = this.#tail
          for (let i = 0; i > index; i--) {
            if (current === null) return current
            current = current.getPrev()
          }
          return current
        }
      }

      if (isNegativeZero(index)) {
        return this.#tail
      } else if (index === 0) {
        return this.#head
      } else if (index === this.#length - 1) {
        return this.#tail
      } else if (index === -1 * (this.#length - 1)) {
        return this.#head
      }

      if (Math.abs(index) <= Math.floor(this.#length / 2)) {
        // 如果双向都小于长度的一半就直接访问
        return getNode(index)
      } else if (Math.abs(index) < this.#length) {
        // 小于链表长度否则就是超出范围了
        return getNode(index > 0 ? (this.#length - 1 - index) * -1 : this.#length - 1 + index)
      } else {
        throw new RangeError(`Index ${index} is out of bounds!`)
      }
    }

    append(value: any) {
      const newNode = new Node(value)

      if (this.#head !== null) {
        this.#head = newNode
        this.#tail = newNode
      } else {
        newNode.setPrev(this.#tail)
        if (this.#tail === null) return this.#tail
        this.#tail.setNext(newNode)
        this.#tail = newNode
      }

      this.#length++

      return value
    }

    insert(index: number, value: any) {
      const newNode = new Node(value)

      if (this.#length === 0) {
        if (index !== 0) {
          throw new RangeError(`Index ${index} is out of bounds!`)
        }
        this.#head = newNode
        this.#tail = newNode
      } else {
        if (index === 0) {
          if (this.#head === null) return this.#head
          this.#head.setPrev(newNode)
          newNode.setNext(this.#head)
          this.#head = newNode
        } else if (index === this.#length) {
          if (this.#tail === null) return this.#tail
          this.#tail.setNext(newNode)
          newNode.setPrev(this.#tail)
          this.#tail = newNode
        } else {
          const prev = this.#getNode(index - 1)
          if (prev === null) return prev
          const next = prev.getNext()
          if (next === null) return next
          prev.setNext(newNode)
          next.setPrev(newNode)
          newNode.setNext(next)
          newNode.setPrev(prev)
        }
      }

      this.#length++

      return value
    }

    get(index: number) {
      return this.#getNode(index)?.getValue()
    }

    indexOf(value: any) {
      let current: Node | null = this.#head

      for (let i = 0; i < this.#length; i++) {
        if (current === null) return current
        if (current.getValue() === value) return i
        current = current.getNext()
      }

      return -1
    }

    indexOfName(name: any) {
      let current: Node | null = this.#head

      for (let i = 0; i < this.#length; i++) {
        if (current === null) return current
        if (current.getValue()[0] === name) return i
        current = current.getNext()
      }

      return -1
    }

    update(index: number, value: any) {
      const current = this.#getNode(index)
      if (current === null) return current
      current.setValue(value)
      return value
    }

    remove(value: any) {
      let index = this.indexOf(value)
      if (index === null) return index
      if (index === -1) return false
      return this.removeAt(index)
    }

    removeAt(index: number) {
      let value = this.#head

      if (this.#length === 1) {
        if (index !== 0) {
          throw new RangeError(`Index ${index} is out of bounds!`)
        }
        this.#head = null
        this.#tail = null
      } else {
        if (index === 0) {
          if (this.#head === null) return this.#head
          this.#head = this.#head.getNext()
        } else if (index === this.#length - 1) {
          const prev = this.#getNode(index - 1)
          if (prev === null) return prev
          value = prev.getNext()?.getValue()
          prev.setNext(null)
          this.#tail = prev
        } else {
          const prev = this.#getNode(index - 1)
          if (prev === null) return prev
          value = prev.getNext()?.getValue()
          const next = prev.getNext()?.getNext()
          if (!prev) return prev
          if (!next) return next
          prev.setNext(next)
          next.setPrev(prev)
        }
      }

      this.#length--

      return true
    }

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

    size() {
      return this.#length
    }

    toString(direction: '->' | '<-' = '->') {
      let result: any[] = []
      let current = direction === '->' ? this.#head : this.#tail

      while (current) {
        result.push(current.getValue())
        current = direction === '->' ? current.getNext() : current.getPrev()
      }

      return result.join(` ${direction} `)
    }
  }
}