Почему это работает
- Список держится в порядке использования: каждый get и put переносит свой узел сразу за head, поэтому узел прямо перед tail — всегда тот, которым пользовались давнее всех.
- Словарь даёт узел ключа за один шаг, а ссылки prev позволяют вынуть узел из середины двумя присваиваниями. Ничего не ищем, поэтому get и put — O(1).
- head и tail — фиктивные узлы: у узла всегда есть соседи с обеих сторон, поэтому вынуть единственный узел или вставить в пустой список можно без отдельного случая.
Сложность
Время O(1) на get и put: одно обращение к словарю и несколько ссылок. Память O(capacity): узел и запись в словаре на каждый ключ.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗