Explain the concept of a Least Recently Used (LRU) cache and how it can be implemented using data structures like a hash table and a doubly-linked list.?

A Least Recently Used (LRU) cache is a type of cache that keeps track of the most recently accessed items. It has a maximum capacity and if this capacity is exceeded, it removes the least recently used item from the cache to make room for the new item. The LRU cache is commonly used in computer systems and software to optimize the use of memory.

To implement an LRU cache, two data structures are typically used: a hash table and a doubly-linked list. The hash table is used to store the key-value pairs, while the doubly-linked list is used to maintain the order of the items in the cache.

When an item is accessed in the cache, it is moved to the front of the doubly-linked list to indicate that it is the most recently used item. If the cache is at its maximum capacity and a new item needs to be added, the least recently used item from the end of the doubly-linked list is removed.

The time complexity of the LRU cache implementation is O(1) for both get and put operations when using a hash table and a doubly-linked list. The space complexity is O(n) since it requires space to store the key-value pairs in the hash table and the order of the items in the doubly-linked list.

Here is an example of an LRU cache implementation in Java:

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;
    private int capacity;

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

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        // Move the node to the front of the list to indicate it is the most recently used item
        remove(node);
        setHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, value);
            map.put(key, node);
            if (map.size() > capacity) {
                // Remove the least recently used item from the end of the list
                map.remove(tail.key);
                remove(tail);
            }
        } else {
            // Update the value of an existing node and move it to the front of the list
            node.value = value;
            remove(node);
        }
        setHead(node);
    }

    private void remove(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }

    private void setHead(Node node) {
        node.next = head;
        node.prev = null;
        if (head != null) {
            head.prev = node;
        }
        head = node;
        if (tail == null) {
            tail = head;
        }
    }

    private static class Node {
        private int key;
        private int value;
        private Node prev;
        private Node next;

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