约 909 字大约 3 分钟

2023-11-28

介绍

优点: 可以从头到尾也可以从尾到头

缺点: 占用的内存会多一些

image-20231129094805554

image-20231129102812053

函数讲解

isNegativeZero

用来判断是 0 还是 -0 这样可以判断是从头部开始的第 0 位还是从尾部开始的第 0

#getNode

这是我写的一个内部方法, 通过给定的索引, 找到 node 后返回, 如果越界了就跑出一个 RangeError 的错误

里面做了一些优化性能的操作

  • 判断是否小于链表的长度处于二, 如果小于就从前往后循环获取, 否则就是从后往前循环
  • 判断是否为头部或尾部, 直接返回

append

可能遇到的情况:

  • 链表为空, 设置头部和尾部都为插入节点
  • 链表不为空, 设置插入节点的上一位为尾部, 然后设置尾部的下一位为插入节点, 然后设置尾部为插入节点

insert

可能遇到的情况:

  • 链表长度为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实现

/**
 * 判断是否为-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
  #tail: Node = null
  #length = 0

  #getNode(index: number) {
    const getNode = (index: number): Node => {
      if (!isNegativeZero(index) && index >= 0) {
        let current = this.#head
        for (let i = 0; i < index; i++) {
          current = current.getNext()
        }
        return current
      } else {
        let current = this.#tail
        for (let i = 0; i > index; i--) {
          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) {
      this.#head = newNode
      this.#tail = newNode
    } else {
      newNode.setPrev(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) {
        this.#head.setPrev(newNode)
        newNode.setNext(this.#head)
        this.#head = newNode
      } else if (index === this.#length) {
        this.#tail.setNext(newNode)
        newNode.setPrev(this.#tail)
        this.#tail = newNode
      } else {
        const prev = this.#getNode(index - 1)
        const next = prev.getNext()
        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 = this.#head

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

    return -1
  }

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

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

    return -1
  }

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

  remove(value: any) {
    let index = this.indexOf(value)
    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) {
        this.#head = this.#head.getNext()
      } else if (index === this.#length - 1) {
        const prev = this.#getNode(index - 1)
        value = prev.getNext().getValue()
        prev.setNext(null)
        this.#tail = prev
      } else {
        const prev = this.#getNode(index - 1)
        value = prev.getNext().getValue()
        const next = prev.getNext().getNext()
        prev.setNext(next)
        next.setPrev(prev)
      }
    }

    this.#length--

    return true
  }

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

  size() {
    return this.#length
  }

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

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

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