P24. 实现 LRU 缓存

https://algocasts.io/episodes/rLmP8moY

head 一直指向最久未使用节点,访问过的节点应该放 head 后面,3’02 这里说的是前面?3’23 又说移动到后面。

:+1:

看得真仔细,3’02 那里说「放在 head 前面」说错了,这个题目中 head 是以逆时针方向移动的,所以节点 C 移动到的位置应该视为 head 的后面。

感谢提出来,我回头打个勘误到视频里。

P.S. 这个是早期制作的视频,现在看来那个图画得好丑,有时间我打算重做一个视频。

public void put(int key, int value) {
      if (map.containsKey(key)) {
        Node cur = map.get(key);
        cur.val = value;
        move2Head(cur);
      } else {
        if (head.val != -1) map.remove(head.key);
        head.key = key;
        head.val = value;
        map.put(key, head);
        head = head.prev;
      }
    }

所以head = head.prev 应该该为 head = hext.next 吗?

@791783391
不是,代码是没有问题的。

所以prev是逆时针箭头往前走,next是顺时针箭头往后走对吧你画的ABCD图可能用顺时针的方式画好像才正确? 如下

public LRUCache(int capacity) {
Node cur = head;
for (int i = 0; i < capacity-1; ++i) {
cur.next = new Node(-1, -1, cur, null);
cur = cur.next; // 顺时针往后走
}
cur.next = head;
head.prev = cur;
}