LeetCode 146. LRU 缓存

原题网址：https://leetcode.cn/problems/lru-cache/

固定容量的缓存，如果满了后，再次添加新的，会删除最近最少使用的那个节点

要求是get,put都是O(1),

class LRUCache {
    
    // 用map保存数据；保证存取是O(1)
    // 双向链表保存顺序。

    ListNode head;
    ListNode tail;
    Map<Integer, ListNode> data;
    int capacity;

    public LRUCache(int capacity) {
    
        data = new HashMap<>();
        this.capacity = capacity;
    }

    private void removeNode(ListNode cur) {
    
        // 维护顺序
            ListNode next = cur.next;
            ListNode prev = cur.prev;

            if(prev != null) {
    
                prev.next = next;
                cur.prev = null;

            }else {
    
                // 说明删除的是头结点
                head = next;
                // cur.next = null;

            }

            if(next != null){
    
                next.prev = prev;
                cur.next = null;
            }else {
    
                // 删除的是尾结点
                tail = prev;
            }
    }

    private void insertHead(ListNode cur) {
    
            cur.next = head;
            if(head != null) {
    
                head.prev = cur;
                head = cur;
            } else {
    
                head = tail = cur;
            }
    }
    
     public int get(int key) {
    
        ListNode cur = data.get(key);
        // 有值，则返回数据
        if(cur != null) {
    
            
            // 维护顺序
            removeNode(cur);

            insertHead(cur);
            return cur.value;
        }

        return -1;

    }
    
    public void put(int key, int value) {
    
        ListNode node = data.get(key);
        if(node != null) {
    
            node.value = value;
            removeNode(node);
            insertHead(node);
        } else {
    

             if(data.size()>= capacity) {
    
                node = tail;
                removeNode(tail);

                data.remove(node.key);
             } 

                node = new ListNode(key,value);
                data.put(key,node);
                insertHead(node);
        }
             
    }
}
class ListNode {
    
    int key;
    int value;
    ListNode prev;
    ListNode next;
    public ListNode(int key,int value) {
    
        this.key = key;
        this.value = value;  
    }
}