CODEWITHSUNDEEP
javadata-structures
Lester Gray
Lester Gray

Reputation: 337

LRU Cache is supposed to be (1) - Why does it contain an O(N) operation and still considered constant time?

I recently started a data structures course and have been trying to understand the most basic of caches - the LRU Cache. From my understanding, the LRU cache is considered attractive because it uses O(1) complexity by amalgamating the best of HashMap and LinkedList.

I wrote the code but for 1 operation - all operations are O(1). But doesnt the data structure base on the slowest man in the army in the sense if there is even 1 operation that is O(N) then the whole datastructure is O(N)? So because of the remove(key) in my code, wont LRU cache be infact O(N)?

    public void put(String key, String value) {
        if (!localCache.containsKey(key)) { // O(1)
            if (localCache.size() == MAX_SIZE) {
                String removedKey = localList.removeLast();
                localCache.remove(removedKey); // O(1)
            }
            localCache.put(key, value); // O(1))
            localList.addFirst(key); // O(1)
        } else {
            localCache.put(key, value); // O(1))
            localList.remove(key); // O(N). <<<<<--- THIS is O(N)
            localList.addFirst(key); // O(1)
        }
    }

Shouldn't LRU cache be O(N)

Upvotes: 0

Views: 889

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

You are correct that your put operation is O(N), but that's because you've implemented it incorrectly.

In an LRU cache, the hash map entry and the linked list node are the same object. When you find an entry in the cache via the hash map, you have also found the linked list node, and you can remove it directly with no search. The linkedList.remove(key) operation should never be called.

In Java, an LRU cache is implemented with LinkedHashMap.

Upvotes: 3

Related Questions