1. 使用LinkedList实现

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws Exception {
        cacheLRU cache = new cacheLRU(3);
        cache.add(1);
        cache.add(2);
        cache.add(3);
        System.out.print(cache.get(1));
        System.out.print(cache.get(2));
        System.out.println(cache.get(3));
        // 123 3->2->1
        cache.add(4); // 4->3->2
        System.out.print(cache.get(2));
        System.out.print(cache.get(3));
        System.out.print(cache.get(4));
        // 234 4->3->2
    }
}

class cacheLRU {
    LinkedList<Integer> linkedList = new LinkedList<>();
    private int cap;

    public cacheLRU(int cap) {
        this.cap = cap;
    }

    public boolean add(Integer num) {
        if (linkedList.size() >= cap) {
            linkedList.removeLast();
        }
        linkedList.addFirst(num);
        return true;
    }

    public int get(Integer num) {
        if (!linkedList.contains(num)) {
            return -1;
        }
        linkedList.remove(num);
        add(num);
        return num;
    }
}

2. 双向链表+哈希表 力扣146

力扣原题点这

class LRUCache {
    Node head;
    Node tail;
    int cap;
    Map<Integer, Node> map;

    class Node {
        int key;
        int value;
        Node next;
        Node pre;
        public Node() {
            this.next = null;
            this.pre = null;
        }
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
            this.pre = null;
        }
    }
    public LRUCache(int capacity) {
        this.head = new Node();
        this.tail = new Node();
        this.cap = capacity;
        this.map = new HashMap<>();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        // 从链表中删除
        removeNode(node);
        // 添加到链表头
        addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 有
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            // 从链表中删除
            removeNode(node);
            // 添加到链表头
            addHead(node);
            return;
        }

        // 无
        Node newNode = new Node(key, value);
        // 添加到链表头
        addHead(newNode);
        map.put(key, newNode);
        if (map.size() > cap) {
            // 移除最后一个节点
            removeLast();
        }
    }

    public void removeLast() {
        Node temp = tail.pre;
        temp.pre.next = tail;
        tail.pre = temp.pre;
        map.remove(temp.key);
    }

    public void addHead(Node node) {
        Node temp = head.next;
        head.next = node;
        node.pre = head;
        node.next = temp;
        temp.pre = node;
    }

    public void removeNode(Node node) {
        Node pre = node.pre, next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
    }
}

/**
 * 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);
 */