I am solving leetcode LRU design problem – Leetcode LRU.

I designed it with using Queue and HashMap, and I was able to get 20/22 TC pass. However, the rest 4 TC are timing out. On googling, I found that doublelinkedlist is the best way to implement it. I am curious as why queue and hashmap is timing out and why doublelinkedlist is the best way to solve.

enter image description here

Below is my implementation for reference.

class LRUCache {

    int capacity=0;
    BlockingQueue<Integer> queue;
    //Stack<Integer> stack ;
    Map<Integer, Integer> map = new HashMap<>();

    public LRUCache(int capacity) {
        //System.out.println("capacity: "+capacity);
        this.capacity = capacity;
        queue = new ArrayBlockingQueue<Integer>(capacity);
        //stack =  new Stack<Integer>();
    }
    
    public int get(int key) {
        //System.out.print("get called: key:"+key+" queue:"+queue+" map:"+map);
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            //System.out.println(" if return: "+map.get(key));
            return map.get(key);
        }
        else
            //System.out.println(" -1 return");
            return -1;
    }
    
    public void put(int key, int value) {
        // System.out.println("put called: key:"+key+" value:"+value+" queue:"+queue+" map:"+map);
        //System.out.println("capacity:"+ capacity);
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            map.put(key, value);
        }
        else if(queue.size()<capacity){
            queue.add(key);
            map.put(key,value);
            
        }
        else{
            int oldKey = queue.remove();
            //System.out.println("popped: oldKey:"+oldKey);
             map.remove(oldKey);
            queue.add(key);
            map.put(key,value);
        }
    }


}

The result is as shown below
enter image description here