Search code examples
javaalgorithmcachinglruevict

LRU Cache Evict method implementation

If we are implementing a LRU cache using HashMap and DoublyLinkedList, What is the best way to implement evict() method with O(1) time complexity?

Solution

  • LinkedList from Java didn't expose the Node type (which is a private static inner class).

    So you can't remove it in in O(1), because a sequential scan is required.

    To get O(1), you need to be able to access the Node type, so that could remove it without scan.

    You have to write it by yourself. Fortunately, a doubly linked list is relatively easy to write, and it's a pretty beneficial & fun task to do.

    How to remove with a given Node?

    Refer to this answer: https://stackoverflow.com/a/54593530

    The method LinkedList.java -> removeNode() remove a given node, without sequential scan.

    The code in this answer is for a singly linked list, the remove for a doubly linked list is even simpler in some case.

    Tips:

    • If the given node is the end node in linked list, then you need the previous node too.
      But that's for singly linked list, for a doubly linked node, the node itself contains the previous node, so you don't have to pass previous node to the removeNode() method.

    BTW

    • Why it's beneficial?
      linked list is the most basic structure (except array and bits), that some other very basic structures could built base on.
      e.g both queue and stack could be implemented easily with a linked list.
    • Concurrent access
      java.util.LinkedList is not thread-safe, your LRU might needs some concurrent control, but I'm not sure.
      If need, then java.util.concurrent.ConcurrentLinkedDeque is a good example to refer to.

    @Update LinkedHashMap

    java.util.LinkedHashMap, is a combination of hashtable & doubly linked list.

    Mechanism:

    • It extends HashMap to get the O(1) complexity for the common operations.
    • And use doubly linked list to keep track of insertion order.
      head is the eldest item, and tail is the newest item.

    It can be used to impl some kind of cache, though I am not sure will it be fully qualified for your requirement.