Force buckle link

Method 1: use LinkedHashMap

public class LRUCache{
    int capacity;
    Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // Delete the old location before putting it in the new location
        Integer value = map.remove(key);
        map.put(key, value);
        return value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
            return;
        }
        map.put(key, value);
        // If the capacity is exceeded, delete the longest useless one, and use the iterator to delete the first one
        if (map.size() > capacity) {
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
}

If the interview management requires that LinkedHashMap cannot be used, then,

Method 2: use double linked list + HashMap

• The bottom layer should use a linked list to arrange the data according to the old and new degree. The old one is on the right, the new one is on the left, and the new one is added to the head (you can imagine drawing a linked list from the left). Deletion is to delete the tail. In addition to these two operations, there is also taking a data out of the middle and putting it on the head (this array is difficult to do)
• There is also a requirement to know whether the data exists in the linked list. If it is not in the linked list, add it to the header. If it is already in the linked list, just specify the location of the data. How to find out whether the data is in or not? Use the hash table.
• Considering the deletion operation, the pointer of the previous node of the current node should be changed to obtain the previous node. The convenient data structure is a two-way linked list.

Here I use the head insertion method to solve the problem:

When inserting, first judge whether the value in the map is full. If not, you also need to judge whether the value exists in the linked list. If it exists, delete it first and re insert it. If it does not exist, insert it directly. If the map is full, there are two situations. One is when the inserted value exists, update it, delete it first, and insert it into the head. If it does not exist, first remove the least commonly used value on the tail, and then insert it into the head!

When get ting, first judge whether the map exists or not, and return - 1. If it exists, update the current node, delete it first, and then add it to the header

Then insert, delete, and obtain the map according to its size

class LRUCache {
    class Node{
        public int key;
        public int val;
        public Node pre;
        public Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    Map<Integer,Node> map = new HashMap<>();
    int x ;
    Node head = new Node(-1,-1);
    Node tail = new Node(-1,-1);
    public LRUCache(int capacity) {
        this.x = capacity;
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            int sum = map.get(key).val;
            delete(key);
            add(key,sum);
            return sum;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.size() < x){
            if(map.containsKey(key)){
                delete(key);
                add(key,value);
            }else{
                add(key,value);
            }
            
        }else{
            if(map.containsKey(key)){
                delete(key);
                add(key,value);
            }else{
                Node node = tail.pre;
                Node cur = node.pre;
                tail.pre = cur;
                cur.next = tail;
                map.remove(node.key);
                add(key,value);
            }
        }
    }

    public void delete(int key){
        Node cur = map.get(key);
        Node node2 = cur.next;
        Node node1 = cur.pre;
        node1.next = node2;
        node2.pre = node1;
        map.remove(key);
    }

    public void add(int key,int value){
        Node cur = head.next;
        Node node = new Node(key,value);
        head.next = node;
        node.pre = head;
        node.next = cur;
        cur.pre = node;
        map.put(key,node);
    }
}