LRU cache

LRU Cache 코드

DoubleLinkedList + HashMap 이용!!

HashMap의 value를 Double LinkedList를 가리키게 한다
그리고 queue처럼 put의 경우는 맨 뒤에 삽입을 하고,
get의 경우는 값이 있다면 반환을 하고난뒤에, 그 위치의 값을 제거한다

그러기 위해서는, Double LinkedList를 삽입 삭제해주는 메소드 2개가 구현되어야한다
head가 가장 안쓴거, tail이 가장 빈번하게 쓰는거라고 정의를 하면
결국 put을 할때는 가장 최근에 들어간거, 즉 가장 최근에 적게 사용이 되었다는 말이므로 맨 뒤에 tail쪽에 넣는거고,
get을할때는 hashtable에서 특정 위치를 찾은 다음에 그 위치의 앞뒤를 제거하고
새롭게 get을 했으니까, 사용이 되었다는 의미가 된다. 그래서 맨 앞으로 옮긴다
즉,put은 tail쪽에 삽입을 하고, 삽입을 했으니, map에 (key,Node)를 등록하고
만약 꽉찼다면, 가장 덜 안중요한 head를 앞으로 옮겨야 하니, 옮기고, map에서 하나 지운다
그렇지않다면, 새롭게 노드를 만든후 삽입을 하자

get은 Double Linked List에서 위치를 찾은후, 맨 뒤로 옮겨주자!!
왜냐하면, 가장 최근에 사용이 되었기 때문이다

by Java

class LRUCache {
        // put의 경우 맨 뒤에 넣는다, 근데 만약에 꽉찼으면, head를 제거하고 맨 뒤에 넣는다
        // get의 경우 제거를 하는데, 그 위치값을 제거를 한다
        
        class Node {
            int key;
            int value;
            Node prev;
            Node next;
            Node(int key,int value) {
                this.key = key;
                this.value = value;
            }
        }
        Node head=null;
        Node tail = null;
        Map<Integer,Node> map = new HashMap<>(); // initialize
        int capacity=0; //initialize
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if(map.get(key)==null) return -1;
            
            Node cur = map.get(key);
            removeNode(cur);
            putNode(cur);
            return cur.value;
        }
        
        public void put(int key, int value) {
            if(map.get(key)!=null) {
                //이미 존재를 하니까, 기존에 있는 위치에 있는것을 지우고
                // 맨뒤에 새로운 value를 삽입
                Node cur = map.get(key);
                cur.value = value;
                
                removeNode(cur);
                putNode(cur);
            }
            else {
                //존재를 안하니까 , 그냥 넣으면 되는데, 사이즈가 크면 안됨
                //사이즈가 크면, head를 움직인다
                if(map.size()>=capacity) {
                    map.remove(head.key);
                    removeNode(head);
                }
                // 그다음에 끝에 넣는다
                Node cur = new Node(key,value);
                putNode(cur);
                map.put(key,cur);
            }
            
        }
        
        private void removeNode(Node cur) {
            // 만약 이전이 null이 아님 ->  
            if(cur.prev!=null) {
                cur.prev.next = cur.next;
            }
            //null이면 지워야하는 위치가 head임
            else {
                head = cur.next;
            }
            // 만약 다음이 null이 아님
            if(cur.next!=null) {
                cur.next.prev = cur.prev;
            }
            //지워야하는 위치가 꼬리
            else {
                tail = cur.prev;
            }
        }
        private void putNode(Node cur) {
            //끝에 넣는다
            if(tail!=null) {
                tail.next = cur;
                cur.prev = tail;
                cur.next = null;
            }
            tail = cur;
            //만약 head가 null이면 head와 tail이 똑같겠지 그리고, head는 가만히 우선은 정지해있지
            if(head==null) {
                head = tail;
            }
        }
    }
    
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */

참고 : https://www.programcreek.com/2013/03/leetcode-lru-cache-java/

(Thanks for Posting)