JS实现单向链表与LRU缓存淘汰算法

class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}
class LinkedList {
  constructor() { this.head = null; this.size = 0; }
  addAtHead(val) { this.head = new ListNode(val, this.head); this.size++; }
  remove(val) {
    if (!this.head) return;
    if (this.head.val === val) { this.head = this.head.next; this.size--; return; }
    let cur = this.head;
    while (cur.next && cur.next.val !== val) cur = cur.next;
    if (cur.next) { cur.next = cur.next.next; this.size--; }
  }
  toArray() { const arr = []; let cur = this.head; while (cur) { arr.push(cur.val); cur = cur.next; } return arr; }
}

// LRU Cache 使用 Map（有序）
class LRUCache {
  constructor(capacity) { this.capacity = capacity; this.cache = new Map(); }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

链表适用于：频繁插入删除的场景、文件系统、内存管理、撤销功能。