> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/jian-guo/lru_cache.md).

# 146. LRU Cache

> Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.\
> set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

## Thoughts

实现least-recently-used cache，O(1)查找和添加，并且当cache容量达到限制时把最早没用过的元素踢出去。用双向链表配合hash表，用实体dummy head和tail能够不用检查next和pre是否为null，实现remove和add。O(1)找结点用hash map，每次接触过的节点放到头部，即调用一次remove和add。超出capacity就把tail前的元素移除。

## Code

```cpp
/*
 * @lc app=leetcode id=146 lang=cpp
 *
 * [146] LRU Cache
 */

// @lc code=start
class LRUCache {
public:
    class Node {
    public:
        int key, val;
        Node *pre = nullptr, *next = nullptr;
        Node(int k, int v): key(k), val(v) {} 
    };
    Node *head, *tail;
    unordered_map<int, Node*> m;
    int K;

    LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->pre = head;
        K = capacity;
    }

    void rm(Node *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void add(Node *node) {
        node->next = head->next;
        node->pre = head;
        head->next = node;
        node->next->pre = node;
    }

    void update(Node *node) {
        rm(node);
        add(node);
    }
    
    int get(int key) {
        if (!m.count(key)) return -1;
        auto node = m[key];
        update(node);
        return node->val;        
    }
    
    void put(int key, int value) {
        if (m.count(key)) {
            auto node = m[key];
            node->val = value;
            update(node);
        } else {
            Node *node = new Node(key, value);
            if (m.size() == K) {
                m.erase(tail->pre->key);
                rm(tail->pre);
            }
            add(node);
            m[key] = node;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end



```

```java
class LRUCache {
    private class ListNode {
        int key, val;
        ListNode prior, next;
        ListNode (int key, int val) {
            this.key = key;
            this.val = val;
            prior = null;
            next = null;
        }
    }

    Map<Integer, ListNode> map;
    ListNode head, tail = null;
    int capacity, size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new ListNode(-1, 0);
        tail = new ListNode(-1, 0);
        head.next = tail;
        tail.prior = head;
        map = new HashMap<>();
    }

    private void rmNode(ListNode node) {
        ListNode pre = node.prior;
        ListNode next = node.next;
        pre.next = next;
        next.prior = pre;
    }

    // Add the new node right after head;
    private void addNode(ListNode node) {
        node.next = head.next;
        node.prior = head;

        node.next.prior = node;
        head.next = node;
    }

    private void mv2Head(ListNode node) {
        this.rmNode(node);
        this.addNode(node);
    }

    private ListNode popTail() {
        ListNode res = tail.prior;
        rmNode(res);
        return res;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            mv2Head(map.get(key));
            return map.get(key).val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            mv2Head(node);
            node.val = value;
        } else {
            size++;
            ListNode node = new ListNode(key, value);

            if (size > capacity) {
                ListNode realTail = popTail(); 
                map.remove(realTail.key);
                size = capacity;
            }
            map.put(key, node);
            addNode(node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
```

## Analysis

每次set和get都是O(1).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/hash/jian-guo/lru_cache.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.