CODEWITHSUNDEEP
linked-list
asndonsadoasndo231213
asndonsadoasndo231213

Reputation: 225

LRU cache with a singly linked list

Most LRU cache tutorials emphasize using both a doubly linked list and a dictionary in combination. The dictionary holds both the value and a reference to the corresponding node on the linked list.

When we perform a remove operation, we look up the node from the linked list in the dictionary and we'll have to remove it.

Now here's where it gets weird. Most tutorials argue that we need the preceding node in order to remove the current node from the linked list. This is done in order to get O(1) time.

However, there is a way to remove a node from a singly linked list in O(1) time here. We set the current node's value to the next node and then kill the next node.

My question is: why are all these tutorials that show how to implement an LRU cache with a doubly linked list when we could save constant space by using a singly linked list?

Upvotes: 4

Views: 4508

Answers (2)

Rann Lifshitz
Rann Lifshitz

Reputation: 4090

You are correct, the single linked list can be used instead of the double linked list, as can be seen here:

The standard way is a hashmap pointing into a doubly linked list to make delete easy. To do it with a singly linked list without using an O(n) search, have the hashmap point to the preceding node in the linked list (the predecessor of the one you care about, or null if the element is at the front).

Retrieve list node:
hashmap(key) ? hashmap(key)->next : list.head

Delete:
successornode = hashmap(key)->next->next
hashmap( successornode ) = hashmap(key)
hashmap(key)->next = successornode
hashmap.delete(key)

Why is the double linked list so common with LRU solutions then? It is easier to understand and use.

If optimization is an issue, then the trade off of a slightly less simple solution of a single linked list is definitely worth it.

Upvotes: 4

joop
joop

Reputation: 4523

There are a few complications for swapping the payload

  • The payload could be large (such as buffers)
  • part of the application code may still refer to the payload (have it pinned)
  • there may be locks or mutexes involved (which can be owned by both the DLL/hash nodes and/or the payload)

In any case, modifying the DLL affects at most 2*2 pointers, swapping the payload will need (memcpy for the swap +) walking the hash-chain (twice), which could need access to any node in the structure.

Upvotes: 2

Related Questions