Leetcode – LRU cache solution in Java

Tags: , , ,

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis

The popular method to implement an LRU cache is to use a bounded Queue. 

The key to for implementing an LRU is to put any recently used data at the head of the queue.

Before each insert, we check whether the queue is full. If the queue is full, we delete its last element, and insert the new node at the beginning of the queue.  

If the queue is not full, we just add the data at the beginning of the queue. 

When we want to delete a node or update a node, we need to quickly find the position of the node in the queue. So a HashTable or HashMap should be used to support the fast look up operation. In this case, the time complexity of the get operation is O(1). 

Since we also need to efficiently remove a node in the middle of the queue, so a double linked list is needed.

There are two cases we need to remove a node in the middle of the queue:

  1. The client specify that a node need to be removed. 
  2. A node is updated, it needs to be removed and insert at the head of the queue. 

By using a double linked list, once we use the HashMap to located the position of the node to be removed, we can remove the node from the queue in O(1) time. 

When we need update the cache for a key, we first use the HashMap to located the corresponding node, update the value, then we remove the node from the queue and put that node at the beginning of the Double Linked list.

The following diagram demonstrates how to use HashMap and Double Linked list to build an efficient LRU cache. 

LRU cache figure
Figure is From: http://androidsrc.net/lru-cache-java-implementation/

We implement the LRU Cache Algorithm in Java. The implementation is as follows:

We first define a double linked list node.

Here are the codes for LRU cache using HashMap and a double linked list. 

Each time we do get operation, we use the hashMap to location the position of the node in the queue, then we remove that list and insert it at the beginning of the queue. So it’s better to define two methods:

1. remove(node): remove a node from the doubled linked list
2. setHead(node): insert a node at the head of the double linked list.