# [Python] Dict + Double-linkedlist, O(1) get and set

• I have read the existing python solutions using Dict + deque, or ordered dict. Dict + Deque has complexity of O(1) set and O(N) get, since moving an element from middle to one end takes O(N). Ordered Dict may have O(N) complexity as well depending on its implementation. Since python does not have a built-in double linked list, I implemented my own.

The idea behind is simple, use a Hashmap to track where the node is, O(1), and change the order of the node and access the last node exploiting Double linked list

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

class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.count = 0
self.tail = ListNode(None, 0)
self.table = {}

def detachNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
self.count -= 1

def attachNode(self, node):
node.next.prev = node
self.count += 1

def get(self, key):
"""
:rtype: int
"""
if key in self.table:
node = self.table[key]
self.detachNode(node)
self.attachNode(node)
return node.val
else:
return -1

def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
if key in self.table:
node = self.table[key]
self.detachNode(node)
self.attachNode(node)
node.val = value
else:
node = ListNode(key, value)
if self.count == self.cap:
lastNode = self.tail.prev
self.table.pop(lastNode.key)
self.detachNode(lastNode)
self.table[key] = node
self.attachNode(node)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.