Design Data Structure (Part I: LRU Cache)

LRU Cache

LeetCode 146. LRU Cache (Medium):

  • Description in short:

a. Solution I, using one dictionary and one doubly LinkedList

  • Diagram:
  • Solution:

Use 1 dictionary and 1 Doubly Linked List:

Add node to head:

Remove from tail:

Remove node:

  • Code:

ListNode class:

LRUCache class:

b. Solution II, using Python OrderedDict

Note. this is not the solution the interviewer is looking for. Also, Python’s OrderedDict is implemented using a dictionary and a doubly linked list. See source code:

  • Code

Software Engineer