Implement simple LRU cache. Explain HashMap + LinkedList data structure.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // duy trì thứ tự insertion
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    // di chuyển về cuối (mới dùng nhất)
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    // xóa phần tử đầu (ít dùng nhất) nếu vượt capacity
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}