1

I was trying to implement LRU Cache using HashMap and doubly linked list. I thought of creating the following class:-

public class LRUCache {
    List<V> list;  // LinkedList()
    Map<K, <Reference to list elements/nodes?>> map; // Hashtable()
}

I planned to use LinkedList class as doubly linked list and Hashtable class to store . However, I am unsure how to declare or define the reference to internal node elements in the list?

Below reference use internal Node class for implementation. Is this due to encapsulation of the LinkedList class that you can't access the internal data fields?

I know my understanding is partially right but need some confirmation as well. I was trying to solve this on leetcode but due to this issue I was stuck for long.

http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

LRU cache in Java with Generics and O(1) operations

// snippet below
public class LRUCache<K, V>{

// Define Node with pointers to the previous and next items and a key, value pair
class Node<T, U> {
Community
  • 1
  • 1
jaamit
  • 393
  • 3
  • 11

1 Answers1

0

No, you can't do what you're trying to do in Java; you can't access the internal nodes of a LinkedList. What you could do is use LinkedHashMap in LRU mode and then override removeEldestEntry to limit the cache size.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • This is due to encapsulation, Right? This implies if I want to write it from scratch I need to define my own Node class that can be used as reference later. – jaamit Feb 16 '16 at 06:21