How can I improve my lru implementation

Question

I've implemented LRU using hashtable+linked list.

The hash table has chaining. The structure for code is as follows:

struct Node{
int value;
struct Node *next;
struct Node* head;
struct Node* tail;

};



struct Node* lruhashtable[10];
struct Node* trackHead;
struct Node* trackTail;

The trackHead and trackTail pointers are to keep track of the sequence of insertions. This is used to remove the elements as per least recently used. I'm thinking that there are multiple replacement policies which are used and not one. Hence LRU is used with a combination of something. So if an element is to be removed from LRU as I access the element again then I need to remove it from LRU.

Inherently I'm maintaining the whole sequence and that is bad if there are millions of entries. Is there any way to improve on this besides using a priority queue+hashtable

Answer 1

You need to maintain the entire sequence, and it's not bad if there's millions of entries as long as you do it right.

The key is making the hashtable like you would any other hashtable. Then instead of iterating over the linked list to locate this recently-used node, you just use the reference in the hashtable. You de-link it from the middle and move it to the front.

Removing an element from a linked list is a constant time operation provided you can find the node to begin with. If didn't have the hashtable, you'd have to iterate (linear time) but since you do have the hashtable, you don't have to do any iterating.