LRU Cache (Least Recently Used) adalah cache berkapasitas tetap yang membuang item paling lama tidak digunakan ketika penuh.

Konsep ini dipakai di mana-mana — browser cache, Memcached, Redis maxmemory-policy allkeys-lru, database query cache, sampai halaman virtual memory di OS.

Tujuan

Punya dua operasi, keduanya O(1):

Mengapa harus kombinasi dua struktur?

Satu struktur saja tidak cukup:

• Hash Map saja: lookup O(1), tapi tidak tahu mana yang paling lama tidak dipakai — O(n) untuk cari.
• Linked List saja: bisa jaga urutan "baru → lama", tapi lookup key = O(n).

Solusinya: Hash Map + Doubly Linked List.

• Hash Map: key → node untuk lookup O(1).
• Doubly Linked List: menjaga urutan akses. Kepala = paling baru, ekor = paling lama.

Saat get(key): lookup lewat map → pindahkan node ke kepala list. Saat put(key, value) dan cache penuh: hapus node ekor, hapus entry-nya dari map, pasang yang baru di kepala.

Karena node linked list menyimpan pointer prev dan next, memindahkan dan menghapus bisa O(1) asal kita punya pointer langsung ke node-nya — dan itu yang diberikan oleh hash map.

Implementasi dengan Map JavaScript

JavaScript punya kelebihan praktis: Map mempertahankan urutan insertion. Kita bisa pakai itu sebagai pengganti doubly linked list — hapus-lalu-set memindahkan key ke posisi "paling baru".

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    // Refresh posisi — hapus lalu set agar jadi paling baru
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key); // buang posisi lama
    } else if (this.map.size >= this.capacity) {
      // Buang yang paling lama — iterator pertama Map
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
    this.map.set(key, value);
  }
}

Contoh penggunaan:

const cache = new LRUCache(2);
cache.put(1, "A");
cache.put(2, "B");
cache.get(1);      // "A" — sekarang 1 paling baru
cache.put(3, "C"); // kapasitas penuh → buang 2 (paling lama)
cache.get(2);      // -1 (sudah dievict)

Kompleksitas

Dengan implementasi "manual" pakai HashMap + DoublyLinkedList, kompleksitas tetap O(1) tanpa bergantung pada perilaku insertion-order Map.

Kapan pakai LRU Cache?

• Halaman yang sering dikunjungi — cache hasil render supaya tidak recompute
• Image/thumbnail cache — batasi memori, buang gambar yang tidak dilihat lagi
• Database query cache — query yang sama dalam waktu singkat tidak perlu pukul DB dua kali
• API response cache di sisi client — mobile app dengan data terbatas

Trivia interview: LRU Cache adalah LeetCode 146 — salah satu soal yang paling sering keluar untuk posisi mid/senior. Intinya: tunjukkan kamu paham kenapa satu struktur tidak cukup.

🎭 Analogi sehari-hari: LRU = lemari baju yang penuh. Mau tambah baju baru? Buang baju yang paling lama gak dipakai (di tumpukan paling bawah). Setiap pakai baju → taruh paling atas. Yang sering dipakai naik terus, yang dilupakan turun terus sampai dibuang.

💡 Trik JS Map: Map di JS pertahankan insertion order. Hapus-lalu-set bikin entry pindah ke "paling baru". Inilah kenapa contoh ini bisa O(1) tanpa linked list manual — JS Map kebetulan sudah punya semantik yang dibutuhkan.

⚠️ Jebakan umum:

• Pakai Object bukan Map — Object tidak menjamin urutan, jadi gak bisa "ambil yang paling lama"
• Lupa refresh posisi di get() — kalau cuma map.get() tanpa delete+set, item populer tetap kelihatan "lama" dan bisa dievict
• Kapasitas 0 atau negatif = edge case yang sering bug
• Concurrent access di multi-thread = race condition. Implementasi ini single-threaded (JS aman, bahasa lain hati-hati)

🎯 LRU vs LFU vs FIFO cache:

• LRU (Least Recently Used): buang yang paling lama gak diakses → cocok untuk pola "popular gets popular"
• LFU (Least Frequently Used): buang yang paling jarang diakses → cocok untuk hot keys persistent
• FIFO: buang yang paling lama masuk → simpel tapi kurang adaptif

TL;DR: LRU = cache yang buang "paling lama gak dipakai". O(1) dengan HashMap + DoublyLinkedList (atau JS Map). LeetCode 146 wajib jago.