Java LRU cache using LinkedList

Question

new to stack-overflow so please dont mind my noob way of asking this. I'm trying to implement LRU caching using a linked list, I've seen other implementations here using linkedHashMap and other data structures but for this case i'm trying to create the best optimized version using linked lists as i was asked during a technical round.

I've limited the cache size here to 3

Is there any way to better optimize this LRU implementation ?

Also what will be the time complexity for this implementation ? will it be of the order O(N) without considering the for-loops which are simply printing the values in the linkedList?

public class LRU {
    public static void main(String[] args) {

        LinkedList list = new LinkedList();
        int[] feed = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };
        for (int i = 0; i < feed.length - 1; i++) {
            if (list.size() <= 2) {
                list.add(feed[i]);
                System.out.println();
                System.out.println("Added " + feed[i]);
                System.out.println("size of list is " + list.size());
                System.out.print("this is list ");
                for (int k = 0; k < list.size(); k++) {
                    System.out.print(" " + list.get(k));
                }
            }

            System.out.println();
            if (list.size() >= 3) {
                System.out.println();
                System.out.println("feed is *" + feed[i + 1] + "*");

                Integer value1 = (Integer) list.get(0);
                Integer value2 = (Integer) list.get(1);
                Integer value3 = (Integer) list.get(2);
                if ((feed[i + 1] != value1) || (feed[i + 1] != value2)
                        || (feed[i + 1] != value3)) {
                    list.removeLast();
                    list.addLast(feed[i + 1]);
                    list.set(0, value2);
                    list.set(1, value3);
                    list.set(2, feed[i + 1]);
                }
                if (feed[i + 1] == value1) {
                    list.removeLast();
                    list.addLast(value1);
                    list.removeFirst();
                    list.addFirst(value2);
                    list.set(1, value3);
                }
                if (feed[i + 1] == value2) {
                    list.removeLast();
                    list.addLast(value2);
                    list.set(1, value3);
                    list.removeFirst();
                    list.addFirst(value1);
                }
                if (feed[i + 1] == value3) {
                    list.set(0, value1);
                    list.set(1, value2);
                }
            }
            System.out.println("Current elements in cache at " + i);
            for (int t = 0; t < list.size(); t++) {
                System.out.print(" " + list.get(t));
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("------------------------------");
        System.out.println("current elements in cache ");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(" " + list.get(i));
        }
    }
}

Your program will not compile because of 3 identical statements like -- int value1 = (int) list.get(0); -- Reason: Cannot cast from Object to int -- Update it to -- Integer value1 = (Integer ) list.get(0); — Nikhil Joshi
– Nikhil Joshi, Commented Jul 31, 2014 at 9:23
@NikhilJoshi so i updated the changes to Integer but the program will still not compile on the mac term it gives error "Note: LRU.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details." however the code runs okay on eclipse IDE — tmax
– tmax, Commented Jul 31, 2014 at 9:39
These are not compile errors, but warnings. It tells that your code smells bad, but the compiler do process it anyway. And you may get rid of these by doing LinkedList<Object> list = new LinkedList<>(); (look for Java Generics for its meaning) — SJuan76
– SJuan76, Commented Jul 31, 2014 at 9:41
@tmax, SJuan76 LinkedList declaration will work only if you are on Java-7. Otherwise use -- LinkedList<Object> list = new LinkedList<Object>(); — Nikhil Joshi
– Nikhil Joshi, Commented Jul 31, 2014 at 9:49
Well your code does not design a cache object, it describes a procedure. What is your cache objects ? What are its method ? On a sidenote : your implementation looks like it could use stack semantics, and luckily enough, LinkedList is a stack implementation of some sort. — GPI
– GPI, Commented Jul 31, 2014 at 9:50

Enno Shioji · Accepted Answer · 2014-08-01 10:00:23Z

2

First of all you want to define an interface. Right now I can't see how you are supposed to use your cache or in fact what you are doing. Try to implement the following class:

class LRUCache {
    final int size;
    Cache(int size){
        this.size = size;
    }
    void put(String key, Integer value){
        //
    }
    Integer get(String key){
        //
    }
}

EDIT (Response to comment):
Whatever the problem is, first step is to define the interface (by which I don't mean Java interfaces, just something that communicates what's going on). In your case, try implementing this then.

class MRU {
    final int size;
    MRU(int size){
        this.size = size;
    }

    void put(Integer value){
        //
    }

    Set<Integer> mostRecentlyUsed(){
        //
    }
}

edited Aug 1, 2014 at 10:00

answered Jul 31, 2014 at 10:07

Enno Shioji

26.9k13 gold badges77 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

tmax Over a year ago

i agree creating an interface sounds the right way, at this point the use of the cache is just feeding in a string of numbers and retaining the least frequently used number in the linkedList. I guess there could be a different way of implementing this to make more sense where a number is referenced to the linked list which acts as cache and if the number is not found in the cache it will add a new entry to the cache else it will use the cache in this case

Enno Shioji Over a year ago

@tmax: added an response, HTH

bear · Accepted Answer · 2021-03-07 19:00:01Z

Here's my linkedlist impl of LRU cache, it won't pass the leetcode judge because the linkedlist takes too long (you'll get Time Limit Exceeded).

public class LRUCache {

    private Map<Integer, Integer> blocks = new HashMap<Integer,Integer>();
    private LinkedList<Integer> bru = new LinkedList<Integer>();
    private int capacity;
    private int length;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.length = 0;
    }

    public int get(int key) {
        Integer value = blocks.get(key);
        if (value != null) {
            bru.remove(value);
            bru.addFirst(value);
            return value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (blocks.containsKey(key)) {
            bru.remove(blocks.get(key));
            blocks.put(key, value);
        } else {
            if (length >= capacity) {
                blocks.remove(bru.removeLast());
                length--;
            }

            length++;
            blocks.put(key, value);
        }
        bru.addFirst(value);
    }
}

Ralf Wagner · Accepted Answer · 2014-07-31 10:16:01Z

0

I'd use

LinkedList<Integer> list = new LinkedList<>();

and instead of your implementation I'd use

if (list.size() >= 3) {
    System.out.println();
    System.out.println("feed is *" + feed[i + 1] + "*");

    // retrieve the next value from the feed
    Integer next = feed[i + 1];

    if (!list.remove(next)) {
        list.removeLast();
    }
    list.addFirst(next);

}

System.out.println("Current elements in cache at " + i);

In case the next value is in the list, it is removed and put as the first element in the list.

In case the next value is not in the list, the last element is removed and the next value is put as first element in the list.

When you then look up elements in the list, e. g. by indexOf(...) the list is searched from the newest to the oldest entry.

edited Jul 31, 2014 at 10:16

answered Jul 31, 2014 at 10:02

Ralf Wagner

1,52711 silver badges19 bronze badges

Collectives™ on Stack Overflow

Java LRU cache using LinkedList

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related