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.

Solution:
LRU: Least Recently Used: when new item needs to put into cache, and the cache is full, we remove the item which the least recently used.
When an item is used, I move it at the tail of list. So when the cache is full, remove the head.
thoughts: 
Singly Linked List uses O(N) time to move an item to the end of a list, it is time consuming.
The key to this question is to use doubly linked list.

public class LRUCache {
    
    int capacity;
    doublyLinkedNode head;
    doublyLinkedNode tail;
    HashMap map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap();
    }
    
    // move the newest used node to tail
    public int get(int key) {
        if(map.containsKey(key)){
            doublyLinkedNode cur = map.get(key);
            
            // move newly added node to the end
            if(cur == head){
                doublyLinkedNode newHead = head.next;
                
                tail.next = cur;
                cur.prev = tail;
                tail = cur;
                
                // if head's next is null, then we won't update head
                if(newHead != null)
                    head = newHead;
            }
            else if (cur == tail){
                //return cur.val;
            }
            else{
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                
                tail.next = cur;
                cur.prev = tail;
                cur.next = null;
        
                tail = cur;
            }
            // newly added node is always located at the end
            return tail.val;
        }
        // map doesn't contain the key
        else{
            return -1;
        }
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key)){
            map.get(key).val = value;
            // update position in doubly linked list
            this.get(key);
        }
        else{
            doublyLinkedNode node = new doublyLinkedNode(value);
            map.put(key,node);
            
            // when head and tail have been initialized
            if(map.size() == 1){
                head = node;
                tail = node;
                return;
            }
            
            // update tail
            tail.next = node;
            node.prev = tail;
            tail = node;
            
            // delete head if it is over size
            if(map.size() > capacity){
                doublyLinkedNode newHead = head.next;
                // remove by values rather than keys
                map.values().remove(head);
                head = newHead;
            }
        }
        
    }
}

// not public
class doublyLinkedNode{
    int val;
    doublyLinkedNode prev;
    doublyLinkedNode next;
    public doublyLinkedNode(int v){
        val = v;
    }
}