Just a quick implementation of a LRU cache.

lru_cache.py

from pprint import pprint

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

    def __str__(self):
        prev_repr = 'None' if self.prev is None else str(id(self.prev))
        next_repr = 'None' if self.next is None else str(id(self.next))
        return 'Node %d: %s | %s | %s | %s' % (id(self), str(self.key), str(self.value), prev_repr, next_repr)

    def __repr__(self):
        return self.__str__()


# it could be said that we want LruCache to inherit from dict but then
# we'd have to support a whole mess of methods that come along with
# dict so we'll just have a dictionary memeber
class LruCache(object):            
    def __init__(self, max_size):
        self.lru_list_head = None
        self.lru_list_tail = None
        self.max_size = max_size
        self.cache_lookup = {}

    def get(self, key):
        node = self.cache_lookup[key]
        self._delete_node(node)
        self._insert_head(node)
        return node.value

    def set(self, key, value):
        if key in self.cache_lookup:
            node = self.cache_lookup[key]
            self._delete_node(node)
        else:
            if len(self.cache_lookup) >= self.max_size:
                self._delete_oldest()

            node = Node(key, value)
            self.cache_lookup[key] = node
        self._insert_head(node)

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        self.set(key, value)

    def dump(self):
        print 'LRU cache_values dump:'
        pprint(self.cache_lookup)
        print 'LRU list dump (head to tail):'
        cur_node = self.lru_list_head
        while cur_node is not None:
            print cur_node
            cur_node = cur_node.prev

    def _delete_oldest(self):
        oldest_node = self.lru_list_tail
        self._delete_node(self.lru_list_tail)
        if oldest_node:
            del(self.cache_lookup[oldest_node.key])

    def _delete_node(self, node):
        if id(self.lru_list_head) == id(node):
            self.lru_list_head = node.prev
        if id(self.lru_list_tail) == id(node):
            self.lru_list_tail = node.next
        if node.next:
            node.next.prev = node.prev
        if node.prev:
            node.prev.next = node.next

    def _insert_head(self, node):
        if self.lru_list_tail is None:
            self.lru_list_tail = node
        if self.lru_list_head:
            self.lru_list_head.next = node
        node.prev = self.lru_list_head
        self.lru_list_head = node


if __name__ == '__main__':
    cache = LruCache(4)
    cache[0] = '00'
    cache[1] = '11'
    cache[2] = '22'
    cache[3] = '33'
    cache[4] = '44'
    cache[5] = '55'
    print cache[4]
    print cache[2]
    try:
        print cache[1]
    except KeyError:
        print 'correctly failed at finding a value that was kicked out'
    cache.dump()