class Node {
  constructor(key, data) {
    this.key = key
    this.data = data
    this.prev = null
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
  }

  append(key, data) {
    let node = new Node(key, data)

    if (this.head === null) {
      this.head = node
      this.tail = node
    } else {
      node.prev = this.tail
      this.tail.next = node
      this.tail = node
    }

    return node
  }

  remove(node) {
    let prev = node.prev
    let next = node.next
    if (prev) {
      node.prev.next = node.next
    } else {
      this.head = node.next
    }
    if (next) {
      node.next.prev = node.prev
    } else {
      this.tail = node.prev
    }
  }
}

class Cache {
  constructor(size) {
    this.size = size
    this.map = new Map()
    this.list = new LinkedList()
  }

  add(key, data) {
    if (this.map.has(key)) {
      const oldNode = this.map.get(key)
      this.list.remove(oldNode)
    } else {
      if (this.map.size === this.size) {
        this.map.delete(this.list.head.key)
        this.list.remove(this.list.head)
      }
    }

    const node = this.list.append(key, data)
    this.map.set(key, node)
  }

  get(key) {
    if (!this.map.has(key)) {
      return undefined
    }
    return this.map.get(key).data
  }
}