你好，我是zhenguo
今天结合一道leetcode有意思的题目，设计和实现一个  LRU (最近最少使用) 缓存机制，顺便和读者们加强下双向链表、字典这些数据结构的应用能力。链表增删操作时间复杂度都是O(1)，这是它最强的地方，尤其追求卓越性能的算法场景，应用广泛。同时，在面试中也经常会考察到。但是，链表比较容易出错，如果在项目中应用，务必要多多测试。

1 问题

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 
int get(int key)  如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。

当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
你是否可以在 O(1) 时间复杂度内完成这两种操作？
链接：https://leetcode-cn.com/problems/lru-cache

2 链表

这道题最高效的O(1)实现需要基于链表结构，因此再温习一下链表的基本操作。
链表是一种节点传递结构，所谓的"传递"是靠next变量，以此建立指向下一个节点的关系，可以理解为一条边，仅此而已。
如果想令j节点指向i节点，需要如何做？如果对链表不熟悉，可能想当然的这么操作：
node_j.next = node_i

上面操作后实现效果如下：
这是不对的，节点i指向节点j的边还存在，这不是我们想要的结果！因此，我们需要摘除这条边，那么如何摘除？实际这才是链表的灵活之处，所谓的摘除只不过是一个None赋值操作：
node_i.next = 
None
上面赋值实现的效果如下：
你看到吗？剪断后，节点i和节点j之间不再有链接关系。所以j节点指向i节点的完整代码如下：
node_i.next = 
None
node_j.next = node_i

3 实现思路

下面我们再回头问题，要想在O(1)时间复杂度内求解，需要借助字典和双向链表，问题涉及的主要操作包括：
(1). put操作 加入键值对分两种情况讨论：
  • (1).1 键不存在
  • (1).2 键存在
(2).get操作，get操作除了具备dict.get的功能外，此处需要定制一个新的功能，即最近使用的节点需要移动到热点区域。而我们知道链表的增删时间复杂度都是O(1)，所以根据这个定制化需求，使用链表是再自然不过的了！

4 完整代码

classNode(object):
"""

    定义双向链表

    """

def__init__(self, val, pre, next):
        self.val = val

        self.pre = pre

        self.next = next

LRUCache缓存类：
classLRUCache:
def__init__(self, capacity: int):
        self.cache_dict = {}

        self.linked_dict = {}

        self.capacity = capacity

        self.head, self.tail = 
None
, 
None
put操作对应代码，主要解决三种情况，这和题目是完整一一对应的，分别为：
  • 如果关键字已经存在，则变更其数据值
  • 如果关键字不存在，则插入该组「关键字-值」
  • 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

defput(self, key: int, value: int) -> None:
if
 key 
in
 self.cache_dict:  
# 如果关键字已经存在，则变更其数据值
            self.cache_dict[key] = value

            self._move_to_tail(key)

elif
 len(self.cache_dict) < self.capacity:  
# 如果关键字不存在，则插入该组「关键字-值」
            self.cache_dict[key] = value

            self.linked_dict[key] = Node(key, 
None
, 
None
)

ifnot
 self.head:

                self.head = self.linked_dict[key]

if
 self.tail:

                self.tail.next = self.linked_dict[key]


            tmp = self.tail

            self.tail = self.linked_dict[key]

if
 tmp:

                self.linked_dict[key].pre = tmp

                tmp.next = self.linked_dict[key]


else
:  
# 当缓存容量达到上限时，
# 它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
            self.cache_dict[key] = value

            self.linked_dict[key] = Node(key, 
None
, 
None
)

            del_key = self.head.val

            self.cache_dict.pop(del_key)

            pre, next = self.linked_dict[del_key].pre, self.linked_dict[del_key].next

ifnot
 pre 
andnot
 next:  
# 删除节点无头无尾
                self.head = self.linked_dict[key]

elifnot
 pre:  
# 删除元素是头节点
                next.pre = 
None
                self.head = next

elifnot
 next:  
# 删除元素是尾节点
                pre.next = 
None
                self.tail = pre

else
:

                pre.next = next

                next.pre = pre


# 然后在尾部连接上key节点
            self.tail.next = self.linked_dict[key]

            self.linked_dict[key].pre = self.tail

            self.linked_dict[key].next = 
None
            self.tail = self.linked_dict[key]

# 最后再从linked_dict中移除key
            self.linked_dict.pop(del_key)

get操作，
defget(self, key: int) -> int:
if
 key 
in
 self.linked_dict 
and
 self.tail != self.linked_dict[key]:

            self._move_to_tail(key)

return
 self.cache_dict.get(key, 
-1
)

简单重构一下，抽离出一个移动节点i到tail处的方法_move_to_tail：
def_move_to_tail(self, key):
"""

        移动key节点到tail

        :param key:

        :return:

        """

        pre, next = self.linked_dict[key].pre, self.linked_dict[key].next

# 从链表中隔断key节点
if
 pre 
and
 next:

            pre.next = next

            next.pre = pre

elif
 next:

            next.pre = 
None
            self.head = next

# 如果key节点不在尾部，则移动key节点到尾部
if
 self.tail != self.linked_dict[key]:

            self.linked_dict[key].pre = self.tail

            tmp = self.tail

            self.tail = self.linked_dict[key]

if
 tmp:

                tmp.next = self.tail

            self.linked_dict[key].next = 
None

5 后记

链表操作比较容易出错，平时需要多加练习，才能在实际项目和面试中，使用得心应手。
其实链表的应用极为广泛，包括我们熟知的版本管理软件git，里面的多分支和某个分支的管理，都是基于链表操作的。牢固的掌握链表才算是深度掌握算法和数据结构的第一步。
继续阅读
阅读原文