Leetcode and Lintcode

LRU Cache

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.

Leetcode link
Lintcode likn

Solution:

To increase the efficiency, use a hash map to record each key to the corresponding node.
Use a double linked the list to store the key value pair, because it is quick for inserting and deleting nodes.
For each get operation, move node which contains the key to the head of the list.
For each set operation, if it is a new key, and the size will be greater than the capacity,
then delete the last node, and insert the new node to the head.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*************************************************************************
	> File Name: LRUCache.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Fri 20 Nov 13:34:31 2015
 ************************************************************************/

public class LRUCache{
	private class ListNode{
        int key;
        int value;
        ListNode prev;
        ListNode next;
        
        ListNode(int key, int value){
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
    
    HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
    ListNode head;
    ListNode tail;
    int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new ListNode(-1,-1);
        tail = new ListNode(-1,-1);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        
        ListNode node = map.get(key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        moveToHead(node);
        
        return node.value;
    }
    
    public void set(int key, int value) {
        ListNode node = null;
        
        if (get(key) != -1){ // Note this, use get key to update the node order
            map.get(key).value = value;
            return;
        } 
        
        if (map.size() == capacity){
            map.remove(tail.prev.key); //
            tail.prev.prev.next = tail;
            tail.prev = tail.prev.prev;
        }
        
       
        node = new ListNode(key,value);
        map.put(key, node);
        
        
        moveToHead(node);
    }
    
    public void moveToHead(ListNode node){
        node.next = head.next;
        node.next.prev = node;
        node.prev = head;
        head.next = node;
    }
}