js-03-lru-cache

# LRU cache

Implement an ES module **`solution.js`** exporting a least-recently-used cache class:

```js
export class LRUCache {
  constructor(capacity) { /* ... */ }
  get(key) { /* ... */ }
  put(key, value) { /* ... */ }
}
```

`capacity` is a positive integer — the maximum number of entries the cache holds.

- **`get(key)`** returns the stored value, or `undefined` if the key is not present. A successful
  `get` counts as a use: it marks the key as the **most recently used**.
- **`put(key, value)`** inserts or updates the entry and marks it most recently used. If adding a
  **new** key would exceed `capacity`, evict the **least recently used** entry first. Updating an
  existing key never changes the number of entries (and refreshes its recency).

"Recently used" is updated by **both** `get` and `put`. Keys may be any value usable as a `Map` key.

Example:
```js
const c = new LRUCache(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");       // => 1   (now "a" is most-recently-used, "b" is least)
c.put("c", 3);    // capacity exceeded -> evicts "b"
c.get("b");       // => undefined
c.get("a");       // => 1
c.get("c");       // => 3
```

import { test } from "node:test";
import { strict as assert } from "node:assert";
import { LRUCache } from "./solution.js";

test("stores and retrieves a value", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  assert.equal(c.get("a"), 1);
});

test("missing key returns undefined", () => {
  const c = new LRUCache(2);
  assert.equal(c.get("nope"), undefined);
});

test("evicts the least-recently-used entry at capacity", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("c", 3); // exceeds capacity -> "a" (oldest) evicted
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
  assert.equal(c.get("c"), 3);
});

test("get refreshes recency so a different key is evicted", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.get("a"); // "a" now most-recently-used, "b" least
  c.put("c", 3); // evicts "b"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 1);
  assert.equal(c.get("c"), 3);
});

test("updating an existing key does not grow size and refreshes recency", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10); // update -> "a" most-recently-used, size stays 2
  c.put("c", 3); // evicts "b", not "a"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("c"), 3);
});

test("capacity of 1 keeps only the latest entry", () => {
  const c = new LRUCache(1);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
});

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```js
export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.list = new List();
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.list.moveToFront(node);
    return node.value;
  }

  put(key, value) {
    let node = this.map.get(key);
    if (node) {
      node.value = value;
      this.list.moveToFront(node);
      return;
    }
    if (this.map.size >= this.capacity) {
      const tail = this.list.tail;
      if (tail) {
        this.map.delete(tail.key);
        this.list.remove(tail);
      }
    }
    node = new ListNode(key, value);
    this.map.set(key, node);
    this.list.addToFront(node);
  }
}

class ListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

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

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

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

  moveToFront(node) {
    this.remove(node);
    this.addToFront(node);
  }
}
```