手写 LRU (Least Recently Used)

import java.util.HashMap;







/**

 * LRUCache

 * @author tonghua

 * @create 2020-03-14 16:53

 */

public class LRUCache {

    

    // 双向链表控制头尾

    private LinkedList list;

    // hashmap保存数据

    private HashMap map;

    // capacity限制LRUCache的大小

    private int capacity;




    public LRUCache(int capacity) {

        this.map = new HashMap();

        this.list = new LinkedList();

        this.capacity = capacity;

    }




    public class Node {

        public int key;

        public int val;

        Node pre;

        Node next;




        public Node(int key, int val) {

            this.key = key;

            this.val = val;

            this.pre = null;

            this.next = null;

        }

    }




    // head为最近最少使用的

    public class LinkedList {

        public Node head;

        public Node tail;




        public LinkedList() {

            this.head = null;

            this.tail = null;

        }

        

        // 最新使用的数据的话就需要把数据移动到尾

        public void moveToTail(Node n) {




            // 如果用的是头，那么把头往后移一个

            if (n == head) {

                head = n.next;

                head.next = null;

            } else {

                n.pre.next = n.next;

                n.next.pre = n.pre;

            }

            

            // 把对应的n移动到尾部

            tail.next = n;

            n.pre = tail;

            n.next = null;

            tail = n;

        }




        // 最新使用的新数据就加入到尾

        public void addToTail(Node n) {

            

            // 如果是第一个，头跟尾都是n

            if (head == null) {

                head = n;

                tail = n;

            } else {

                // 不是第一个就往尾后加n，尾后移一个

                tail.next = n;

                n.pre = tail;

                tail = tail.next;

            }

        }




        // 移除最近最少使用元素

        public Node removeHead() {

            Node n = head;

            // 这种情况只会出现在capacity=1的情况

            if (head == tail) {

                head = null;

                tail = null;

            } else {

                // 正常应该是把头移除，然后返回头（给hashMap移除用的）

                head = head.next;

                head.pre = null;

            }

            return n;

        }

    }




    public int get(int key) {

        if (!map.containsKey(key)) {

            return -1;

        } else {

            Node n = map.get(key);

            list.moveToTail(n);

            return n.val;

        }

    }




    public void put(int key, int val) {

        if (map.containsKey(key)) {

            Node n = map.get(key);

            n.val = val;

            list.moveToTail(n);

        } else {

            Node n = new Node(key, val);

            map.put(key, n);

            list.addToTail(n);




            if (map.size() > capacity) {

                map.remove(list.removeHead().key);

            }




        }

    }

}