class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self._map = {}
        self._head = Node()
        self._tail = Node()
        self._head.next = self._tail
        self._tail.prev = self._head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node

    def get(self, key):
        if key not in self._map:
            return None
        node = self._map[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        if key in self._map:
            node = self._map[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        node = Node(key, value)
        self._map[key] = node
        self._add_front(node)
        if len(self._map) > self.capacity:
            lru = self._tail.prev
            self._remove(lru)
            del self._map[lru.key]

    def peek(self, key):
        """Return the value WITHOUT changing recency, or None if absent."""
        # TODO: look up self._map.get(key); return its value (or None) — do NOT move it
        pass

    def __len__(self):
        """Number of entries currently cached."""
        # TODO
        pass

    def clear(self):
        """Remove all entries and reset the list to empty."""
        # TODO: clear self._map and re-link _head <-> _tail
        pass