A simple LRU cache implementation in Python. See test_lru.py for an usage example.

lru.py

class Item:
    def __init__(self, key, value, previous, next):
        self.key = key
        self.value = value
        self.previous = previous
        self.next = next


class LRU:
    def __init__(self, maxlength=10):
        self.items = {}
        self.head = None
        self.tail = None
        self.maxlength = maxlength
        self.length = 0

    def get(self, key):
        item = self.items.get(key)
        if item is None:
            return None
        self.move_item_to_head(item)
        return item.value

    def put(self, key, value):
        item = self.items.get(key)
        if item is None:
            self.prepend_item(key, value)
            if self.length < self.maxlength:
                self.length += 1
            else:
                previous_tail = self.tail
                del self.items[previous_tail.key]
                tail = previous_tail.previous
                tail.next = None
                self.tail = tail
        else:
            item.value = value
            self.move_item_to_head(item)

    def move_item_to_head(self, item):
        if self.head is item:
            return
        if self.tail is item:
            self.tail = item.previous
            self.tail.next = None
            item.previous = None
            item.next = self.head
            self.head.previous = item
            self.head = item
        else:
            item.previous.next = item.next
            item.next.previous = item.previous
            item.previous = None
            item.next = self.head
            self.head.previous = item
            self.head = item

    def prepend_item(self, key, value):
        if self.head is None:
            item = Item(key=key, value=value, previous=None, next=None)
            self.head = item
            self.tail = item
        else:
            item = Item(key=key, value=value, previous=None, next=self.head)
            self.head.previous = item
            self.head = item
        self.items[key] = item

    def __iter__(self):
        now = self.head
        while now is not None:
            yield (now.key, now.value, )
            now = now.next

    def __len__(self):
        return self.length

test_lru.py

from lru import LRU

def test_lru():
    yeah = LRU(maxlength=20)
    for i in range(20):
        yeah.put(i, i * i)
    for i in range(20):
        assert yeah.get(i) == i * i
    assert len(yeah) == 20
    for i in range(20, 40):
        yeah.put(i, i * i)
    for i in range(20, 40):
        assert yeah.get(i) == i * i
    assert len(yeah) == 20
    for i in range(20):
        assert yeah.get(i) is None

    for i, (k, v) in enumerate(yeah):
        assert k == 39 - i