Removing an element form linked list in java, unexpected behavior

Question

I am trying to implement lru cache in java using hashmap and linkedlist:

public static class LRUCache{
    LinkedList<Integer> ll;
    HashMap<Integer, Integer> map;
    //HashSet<Integer> map;
    int size;
    LRUCache(int n){
        ll = new LinkedList<>();
        map = new HashMap<>();
        size=n;
    }

    int refer(int page){
        
        if(map.containsKey(page)){
            Integer it = map.get(page);
            //System.out.println("m.get(page)= " + map.get(page));
            //System.out.println(it + " it+page " + page);
            ll.remove(it);
        } else{
            if(map.size() >= size){
                map.remove(ll.getLast());
                ll.removeLast();
            }
        }
        ll.addFirst(page);
        //System.out.println(page + " page+peek " + ll.peekFirst());
        map.put(page, ll.peekFirst());
        return page;
    }

}

In the refer function above, for the if condition where page is found in the map the value is getting successfully removed from the linked list, which I think should not work as I am keeping only the page value in the map. Now interestingly when I put ll.remove(page); in the above code it breaks although the value of both page and it are same.

int refer(int page){

        if(map.containsKey(page)){
            Integer it = map.get(page);
            //System.out.println("m.get(page)= " + map.get(page));
            //System.out.println(it + " it+page " + page);
            ll.remove(page);
        } else{
            if(map.size() >= size){
                map.remove(ll.getLast());
                ll.removeLast();
            }
        }
        ll.addFirst(page);
        //System.out.println(page + " page+peek " + ll.peekFirst());
        map.put(page, ll.peekFirst());`enter code here`
        return page;
    }

I am really surprised by this behavior.

For the below test case, the first price of code works but the second doesn't, the only difference is ll.remove(it) and ll.remove(page) ,the values of it and page are same.

        void printCache(){
        System.out.print("| ");

        for(int i=0;i<ll.size();i++){
            System.out.print(ll.get(i) + " |" + " ");
        }
        System.out.println();
    }

}

public static void main(String[] args) {
    LRUCache lruCache = new LRUCache(4);


    lruCache.refer(11);
    lruCache.refer(12);
    lruCache.refer(13);
    lruCache.printCache();
    lruCache.refer(11);
    lruCache.printCache();
    lruCache.refer(14);
    lruCache.printCache();
    lruCache.refer(13);
    lruCache.printCache();
    lruCache.refer(15);
    lruCache.printCache();
}

Answer 1

Without diving into too much details of your code, there is very big difference between which method is being called when invoking ll.remove(page) and when involing ll.remove(it).

When calling ll.remove(it), the type of it is Integer, so the method called is LinkedList.remove(Object). From the documentation of this method:

Removes the first occurrence of the specified element from this list, if it is present....

While when you call ll.remove(page), the type of page is int, so you actually call: LinkedList.remove(int). From the documentation of this method:

Removes the element at the specified position in this list....

One method is removing the index at page, while the other is removing the value matching it.

I think what you might wanted to do in the call to ll.remove(page) to achieve similar behavior is ll.remove(new Integer(page))

Here is a simple code that demonstrates this issue:

public static void foo(int x) {
    System.out.println("Called foo(int)");
}
public static void foo(Integer x) {
    System.out.println("Called foo(Integer)");
}
public static void main (String[] args) throws java.lang.Exception
{
    int page = 5;
    Integer it = new Integer(10);
    foo(page);
    foo(it);
    foo(new Integer(page));
}