Subj : Re: best data structure for LRU cache?
To   : alt.comp.lang.learn.c-c++,comp.programming
From : Alex Fraser
Date : Sun Aug 07 2005 10:16 am

"Digital Puer" <digital_puer@hotmail.com> wrote in message
news:1123382742.905087.69870@g44g2000cwa.googlegroups.com...
> Can someone recommend the best data structure to implement
> an LRU cache?

Probably a list, plus a hash table or balanced tree (of pointers to list
items). A hash table will need to be rebuilt every so often as it
accumulates deleted entries, but aside from that is O(1).

if (requested item in cache) {
    move item to head of list
} else {
    if (list size == max cache entries) {
        delete item at list tail from list
        delete pointer from hash table/tree
    }
    read item
    add item to head of list
    add pointer to hash table/tree
}
/* requested item now at head of list */

Alex

.