interface DoublyLinkedListNode<T> {
  value: T
  next: () => DoublyLinkedListNode<T> | null
  prev: () => DoublyLinkedListNode<T> | null
}

export class DoublyLinkedList<T> {
  private nodes: Array<DoublyLinkedListNode<T>> = []

  constructor(nodes?: Array<T>) {
    this.nodes = []

    if (nodes) {
      for (const node of nodes) {
        this.push(node)
      }
    }
  }

  get size() {
    return this.nodes.length
  }

  get head() {
    return this.size ? this.nodes[0] : null
  }

  get tail() {
    return this.size ? this.nodes[this.size - 1] : null
  }

  insertAt(index: number, value: T) {
    const prevNode = this.nodes[index - 1] || null
    const nextNode = this.nodes[index] || null
    const node: DoublyLinkedListNode<T> = {
      value,
      next: () => nextNode,
      prev: () => prevNode,
    }

    if (prevNode) {
      prevNode.next = () => node
    }
    if (nextNode) {
      nextNode.prev = () => node
    }
    this.nodes.splice(index, 0, node)
  }

  shift(value: T) {
    this.insertAt(0, value)
  }

  push(value: T) {
    this.insertAt(this.size, value)
  }

  getAt(index: number) {
    return this.nodes[index]
  }

  removeAt(index: number) {
    const prevNode = this.nodes[index - 1] || null
    const nextNode = this.nodes[index + 1] || null

    if (prevNode) {
      prevNode.next = () => nextNode
    }

    if (nextNode) {
      nextNode.prev = () => prevNode
    }

    return this.nodes.splice(index, 1)
  }

  clear() {
    this.nodes = []
  }

  toArray() {
    return this.nodes.map(node => node.value)
  }

  *[Symbol.iterator]() {
    yield* this.nodes
  }
}