Design Questions

LeetCode 146. LRU Cache

I have 2 solutions:

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

class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.data = dict()
        self.head = Node('dummy', 0)
        self.tail = Node('dummy', 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.data:
            node = self.data[key]
            self._tweak(node)
            return self.head.next.value
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.data:
            node = self.data[key]
            node.value = value
            self._tweak(node)
        else:
            node = Node(key, value)
            self.data[key] = node
            self._add(node)

        if len(self.data) > self.capacity:
            leastNode = self.tail.prev
            del self.data[leastNode.key]
            self._remove(leastNode)

    def _add(self, node):
        # always move current node to the head
        headNext = self.head.next
        self.head.next = node
        headNext.prev = node
        node.next = headNext
        node.prev = self.head


    def _remove(self, node):
        # delete last element of the list
        prevNode = node.prev
        prevNode.next = self.tail
        self.tail.prev = prevNode
        node.prev = None
        node.next = None

    def _tweak(self, node):
        # always move current node to the head
        nextNode = node.next
        prevNode = node.prev
        headNext = self.head.next
        if node != headNext:
            self.head.next = node
            node.prev = self.head
            node.next = headNext
            headNext.prev = node

            prevNode.next = nextNode
            nextNode.prev = prevNode

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.stamp = 0
        self.size = capacity
        self.data = {}


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.data:
            self.stamp += 1
            self.data[key]['time'] = self.stamp
            return self.data[key]['value']
        else:
            return -1


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        self.stamp += 1
        if len(self.data) < self.size or key in self.data:
            self.data[key] = {
                'value':    value,
                'time':     self.stamp
            }
        else:
            recent = self.stamp
            for _key in self.data.keys():
                if self.data[_key]['time'] < recent:
                    recentkey = _key
                    recent = self.data[_key]['time']
            del self.data[recentkey]
            self.put(key, value)