辞書と双方向リストで LRU キャッシュを設計する

ops = ["LRUCache", "put", "put",
  "get", "put", "get", "get",
  "get"]
args = [[2], [1, 10], [2, 20],
  [1], [3, 30], [2], [1], [3]]

ops = ["LRUCache", "put", "put",
  "put", "put", "get", "get",
  "get"]
args = [[2], [1, 1], [2, 2],
  [1, 5], [3, 3], [1], [2], [3]]

ops = ["LRUCache", "put", "get"]
args = [[0], [7, 70], [7]]

from types import (
    SimpleNamespace,
)

def new_node(k, v):
    return SimpleNamespace(
        key=k, val=v,
        prev=None, next=None,
    )

def unlink(nd):
    nd.prev.next = nd.next
    nd.next.prev = nd.prev

def to_front(head, nd):
    nd.prev = head
    nd.next = head.next
    head.next.prev = nd
    head.next = nd

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.map = {}
        h = new_node(0, 0)
        t = new_node(0, 0)
        h.next = t
        t.prev = h
        self.head = h
        self.tail = t

    def get(self, key):
        nd = self.map.get(key)
        if nd is None:
            return -1
        unlink(nd)
        to_front(self.head, nd)
        return nd.val

    def put(self, key, val):
        if self.cap == 0:
            return
        m = self.map
        if key in m:
            unlink(m.pop(key))
        if len(m) == self.cap:
            old = self.tail.prev
            unlink(old)
            del m[old.key]
        nd = new_node(key, val)
        m[key] = nd
        to_front(self.head, nd)

function newNode(key, val) {
  return {
    key, val,
    prev: null, next: null,
  };
}

function unlink(nd) {
  nd.prev.next = nd.next;
  nd.next.prev = nd.prev;
}

function toFront(head, nd) {
  nd.prev = head;
  nd.next = head.next;
  head.next.prev = nd;
  head.next = nd;
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = newNode(0, 0);
    this.tail = newNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(k) {
    const nd = this.map.get(k);
    if (!nd) return -1;
    unlink(nd);
    toFront(this.head, nd);
    return nd.val;
  }

  put(k, v) {
    if (this.cap === 0) return;
    const { head, tail } = this;
    const m = this.map;
    if (m.has(k)) {
      unlink(m.get(k));
      m.delete(k);
    }
    if (m.size === this.cap) {
      const old = tail.prev;
      unlink(old);
      m.delete(old.key);
    }
    const nd = newNode(k, v);
    m.set(k, nd);
    toFront(head, nd);
  }
}

type lruNode struct {
	key, val   int
	prev, next *lruNode
}

func unlink(n *lruNode) {
	n.prev.next = n.next
	n.next.prev = n.prev
}

func toFront(
	h, n *lruNode,
) {
	n.prev, n.next = h, h.next
	h.next.prev = n
	h.next = n
}

type LRUCache struct {
	cap        int
	m          map[int]*lruNode
	head, tail *lruNode
}

func newLRUCache(
	capacity int,
) *LRUCache {
	h := &lruNode{}
	t := &lruNode{}
	h.next, t.prev = t, h
	return &LRUCache{
		cap:  capacity,
		m:    map[int]*lruNode{},
		head: h,
		tail: t,
	}
}

func (c *LRUCache) Get(
	key int,
) int {
	n, ok := c.m[key]
	if !ok {
		return -1
	}
	unlink(n)
	toFront(c.head, n)
	return n.val
}

func (c *LRUCache) Put(
	key, value int,
) {
	if c.cap == 0 {
		return
	}
	if n, ok := c.m[key]; ok {
		unlink(n)
		delete(c.m, key)
	}
	if len(c.m) == c.cap {
		old := c.tail.prev
		unlink(old)
		delete(c.m, old.key)
	}
	n := &lruNode{key: key}
	n.val = value
	c.m[key] = n
	toFront(c.head, n)
}