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)); } } }