// Minimal Doubly Linked List implementation with: append, prepend, deleteHead, deleteTail and toArray (optional) methods.
// We will be only using the methods that helps to perform additions and removals from both ends.
class DoublyLinkedListMinimal {
  constructor(value) {
      this.head = null
      this.tail = null
      this.length = 0

      // make it optional to create Doubly Linked List with or without starter value
      if (value) {
          this.append(value)
      }
  }

  // Add to the end of list
  append(value) {
      // Initialize a newNode with value recieved
    const newNode = {
      value,
      next: null,
      prev: null
    }

      // Let's first check if Doubly Linked List is empty or not.
      if (!this.head) {
          // If there is no head (no elements) it is empty. In that case make the newNode as head
          // since it is the only node at this point and there is no tail either,
          // tail will also have the same value (both head and tail will point to same place in memory from now on):
          this.head = newNode
          this.tail = newNode
      } else {
          // Since the newNode will be the new tail, set the prev value to current tail before applying changes. Timing is important!
          newNode.prev = this.tail
          // we have this.tail = this.head is setup with first entry
          // at first we populate the this.tail.next with newNode. Since both are referencing the same object, both head and tail will look equal at this step:
          this.tail.next = newNode
          // at this step, we cleanup the tail by setting it to newNode. In other words we extended the head by using tail first, then cleaned up the tail by using newNode.
          this.tail = newNode
      }
      this.length++
      return this
  }

  // Add to the beginning of list
  prepend(value) {
      // Let's check first if Doubly Linked List is empty or not.
      // If that's the case, return here by using the append method instead

      if (!this.head) {
          return this.append(value)
      }

      // Initialize a newNode with value recieved
      const newNode = {
        value,
        next: null,
        prev: null
      }
      // apply a reference to newNode.next prop. When we add it at the start, naturally prepended node's next value should point to the this.head.
      newNode.next = this.head
      // Since the newNode will be the new previous for the current head, set the prev value of head to be newNode. We do this before changing the pointer of this.head to newNode. Timing is important!
      this.head.prev = newNode
      // now that newNode has the this.head as next and newNode as prev, we can set the this.head as newNode directly.
      this.head = newNode
      this.length++
      return this
  }

  // toArray - loop through nested objects, then return the values in an array
  toArray() {
      const array = []
      let currentNode = this.head

      while (currentNode !== null) {
          array.push(currentNode.value)
          currentNode = currentNode.next
      }
      return array
  }

  // Delete from beginning of list
  deleteHead() {
      // check the length - if zero return a warning
      if (this.length === 0) return 'List is empty'

      // If there is only one node left:
      if (this.length === 1) {
          const headVal = this.head.value
          this.head = null
          this.tail = null
          this.prev = null
          this.length--
          return headVal
      }

      // pick the current head value:
      const headVal = this.head.value
      // define newHead as this.head.next
      const newHead = this.head.next
      // make the new heads prev pointer null
      newHead.prev = null
      // now change the head pointer to newHead
      this.head = newHead
      this.length--
      return headVal
  }

  // Delete from the end of list
  deleteTail() {
      // check the length - if zero return a warning
      if (this.length === 0) return 'List is empty'

      // If there is only one node left:
      if (this.length === 1) {
          const tailVal = this.tail.value
          this.head = null
          this.tail = null
          this.prev = null
          this.length--
          return tailVal
      }

      // Define new tail by traversing to previous Node of tail idx
      // Note that, tail always points to null. (which is length).
      // length - 1 will point to last Node with a value. Therefore we need to target length - 2
      const tailVal = this.tail.value
      const newTail = this.tail.prev
      // Now, we can just simply update the pointer of newTail to null:
      newTail.next = null
      this.tail = newTail
      this.length--
      return tailVal
  }
}

class Deque {
  constructor() {
    this.items = new DoublyLinkedListMinimal()
  }

  addToFront(item) {
    this.items.prepend(item)
  }

  addToRear(item) {
    this.items.append(item)
  }

  removeFromFront() {
    const removedItem = this.items.deleteHead()
    return removedItem
  }

  removeFromRear() {
    const removedItem = this.items.deleteTail()
    return removedItem
  }

  peekFront() {
    return this.items.head.value
  }

  peekRear() {
    return this.items.tail.value
  }

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

  length() {
    return this.items.length
  }

  clear() {
    this.items = new DoublyLinkedListMinimal()
  }

  toArray() {
    return this.items.toArray()
  }
}

class Deque {
  constructor() {
    this.items = []
  }

  addToRear(item) {
    this.items.push(item)
  }

  addToFront(item) {
    this.items.unshift(item)
  }

  removeFromFront() {
    const removedItem = this.items.shift()
    return removedItem
  }

  removeFromRear() {
    const removedItem = this.items.pop()
    return removedItem
  }

  peekFront() {
    return this.items[0]
  }

  peekRear() {
    return this.items[this.items.length - 1]
  }

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

  length() {
    return this.items.length
  }

  clear() {
    this.items = []
  }

  toArray() {
    return this.items
  }
}