LRU

Least Recently Used Cache

1. Introduction

LRU(Least Recently Used) Cache is a caching algorithm which will discard items that are not recently used. It is implemented by HashMap(For searching in O(1) time) and Double Linked List(For insertion and deletion in O(1) time).

The recently used item will always add to the head of linked list, so that we will remove item from the end of the list when we run out of capacity.

2. Implementation

public class LRUCache {
    class Node {
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int capacity;
    Map<Integer, Node> map;
    Node head;
    Node tail;

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

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            setHead(node);
            return node.value;
        }
        return -1;
    }

    public void remove(Node node) {
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        else {
            head = node.next;
        }

        if (node.next != null) {
            node.next.pre = node.pre;
        }
        else {
            tail = node.pre;
        }
    }

    public void setHead(Node node) {
        node.next = head;
        node.pre = null;

        if (head != null) {
            head.pre = node;
        }

        head = node;

        if (tail == null) {
            tail = node;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            setHead(node);
        }
        else {
            Node newNode = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(tail.key);
                remove(tail);
            }
            setHead(newNode);
            map.put(key, newNode);
        }
    }
}

3. Time & Space Complexity

1. get(): O(1)

2. put(): O(1)

3. Space: O(n), where n is the capacity