146. LRU Cache Leetcode Java

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:

Use a doubly linked list and hashmap together to realize the desired functions. A doubly linked list will make the insertion and deletion in O(1). And the get() requires not only retrieving the value but also updating the whole list, since this node is visited. Maintain two extra pointers pre and tail, to get fast insertion and deletion when overflowed. Since it is doubly linked list, we have to take care of the two corner cases: first element and last element. 

 public class LRUCache {  
   class ListNode{  
   int val;  
   ListNode next;  
   ListNode previous;  
   int key;  
   public ListNode(int key, int val) {  
     this.key=key;  
     this.val=val;  
     this.next=null;  
     this.previous=null;  
   }  
 }  
   ListNode pre;  
   ListNode tail;  
   HashMap<Integer,ListNode> map;  
   int capacity;  
   public LRUCache(int capacity) {  
     this.capacity=capacity;  
     this.map=new HashMap<Integer,ListNode>();  
     this.pre=new ListNode(0,0);  
     this.tail=pre;  
   }  
   public int get(int key) {  
     if(map.isEmpty() || !map.containsKey(key)) return -1;  
     ListNode cur=map.get(key);  
     if(cur.previous==pre) return cur.val;  
     if(cur==tail) tail=cur.previous;  
     cur.previous.next=cur.next;  
     if(cur.next!=null) cur.next.previous=cur.previous;  
     cur.next=pre.next;  
     if(pre.next!=null) pre.next.previous=cur;  
     pre.next=cur;  
     cur.previous=pre;  
     return cur.val;  
   }  
   public void set(int key, int value) {  
     if(this.capacity==0) return;  
     if(this.map.isEmpty()){  
       ListNode cur=new ListNode(key,value);  
       pre.next=cur;  
       cur.previous=pre;  
       tail=cur;  
       map.put(key,cur);  
     }  
     else if(this.map.containsKey(key)){  
       ListNode cur=map.get(key);  
       if(cur.previous==pre){  
         cur.val=value;  
         return;  
       }  
       if(cur==tail) tail=cur.previous;  
       cur.previous.next=cur.next;  
       if(cur.next!=null) cur.next.previous=cur.previous;  
       cur.next=pre.next;  
       if(pre.next!=null) pre.next.previous=cur;  
       pre.next=cur;  
       cur.previous=pre;  
       cur.val=value;  
     }  
     else{  
       if(map.size()>=capacity){  
         map.remove(tail.key);  
         tail=tail.previous;  
         tail.next=null;  
       }  
         ListNode cur=new ListNode(key,value);  
         cur.next=pre.next;  
         if(pre.next!=null) pre.next.previous=cur;  
         pre.next=cur;  
         cur.previous=pre;  
         if(map.isEmpty()) tail=cur;  
         map.put(key,cur);  
     }  
   }  
 }