LRU Cache

LRU cache.

Two operations

Doubly linked list can be used to implement a deque pronounced deck.

# Helper Node class
class Node:
	def __init__(self, key, value):
        self.key = key
		self.value = value 
		self.next = None # Pointer to next node
		self.prev = None # Pointer to previous node.

Traverse forward through doubly linked list

current = head
while current is not None:
  # Do something with current
  current = current.next

Traverse backwards through doubly linked list

current = tail
while current is not None:
  # Do something with current
  current = current.prev

Sanity check

Make sure the list is valid by traversing the list and making sure current.next.prev = current.

current = head
while current.next is not None:
  if current.next.prev is not current:
       return False
  current = current.next
return True

Deque class

class Deque:
	# initialize an empty deque
	def __init__(self):

	# is the deque empty?
	# returns a Boolean 
	def is_empty(self):

    # returns the number of items in the deque
	def size(self):

    # inserts item to the front of the deque
	def add_first(self, key, value):
	
	# inserts item at the end of the deque
	def add_last(self, key, value):

	# delete and return the key-value pair at the front of the deque 
	def remove_first(self):

	# delete and return the key-value at the end of the deque
	def remove_last(self):

Full Deque boiler plate code

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None


class Deque:
    # Initialize Deque
    def __init__(self):
        pass

    # Return Type: Boolean
    # Description: Return True if the deque is empty, else False
    def isEmpty(self):
        pass

    # Return Type: int
    # Description: Return the number of items in the deque
    def getSize(self):
        pass

    # Return Type: None
    # Description: Insert item to the front of the deque
    def addFirst(self, item):
        pass

    # Return Type: None
    # Description: Inserts item to the end of the deque
    def addLast(self, item):
        pass

    # Return Type: Object
    # Description: Delete and return the item at the front of the deque
    def removeFirst(self):
        pass

    # Return Type: List
    # Description: Construct a list holding all of the items in the deque from
    # front to end and return it.
    def asList(self):
        pass