Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- All operations have O(1) time complexity
- Space Complexity : O(capacity)
- */
- class LRUCache {
- private class Node {
- int key;
- int value;
- Node prev;
- Node next;
- public Node(int k, int v) {
- key = k;
- value = v;
- prev = null;
- next = null;
- }
- }
- HashMap<Integer, Node> map;
- Node head;
- Node tail;
- int maxCapacity;
- public LRUCache(int capacity) {
- map = new HashMap<Integer, Node>();
- head = new Node(0, 0);
- tail = new Node(0, 0);
- head.next = tail;
- tail.prev = head;
- maxCapacity = capacity;
- }
- private void addToHead(Node node) {
- node.next = head.next;
- head.next.prev = node;
- node.prev = head;
- head.next = node;
- }
- private void deleteNode(Node node) {
- node.next.prev = node.prev;
- node.prev.next = node.next;
- node.prev = null;
- node.next = null;
- }
- private void moveToHead(Node node) {
- deleteNode(node);
- addToHead(node);
- }
- public int get(int key) {
- if (!map.containsKey(key)) {
- return -1;
- }
- Node cur = map.get(key);
- moveToHead(cur);
- return cur.value;
- }
- public void put(int key, int value) {
- if (maxCapacity <= 0) {
- return;
- }
- if (map.containsKey(key)) {
- Node cur = map.get(key);
- cur.value = value;
- moveToHead(cur);
- return;
- }
- if (map.size() == maxCapacity) {
- map.remove(tail.prev.key);
- deleteNode(tail.prev);
- }
- Node node = new Node(key, value);
- map.put(key, node);
- addToHead(node);
- }
- }
- /**
- * 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);
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement