Design Data Structure (Part I: LRU Cache)

LRU Cache

LeetCode 146. LRU Cache (Medium): https://leetcode.com/problems/lru-cache/

  • 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: https://svn.python.org/projects/python/trunk/Lib/collections.py

  • Code

Software Engineer