Cache란?

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

	public static final int CAPACITY = 4;

	private int actualSize;
	private Map<Integer, Node> map;
	private DoublyLinkedList linkedList;

	public LRUCache() {
		this.map = new HashMap<>();
		this.linkedList = new DoublyLinkedList();
	}

	static class Node {

		private int id;
		private String data;
		private Node prevNode;
		private Node nextNode;
		
		public Node() {
			
		}

		public Node(int id, String data) {
			this.id = id;
			this.data = data;
		}

		public int getId() {
			return id;
		}

		public void setId(int id) {
			this.id = id;
		}

		public String getData() {
			return data;
		}

		public void setData(String data) {
			this.data = data;
		}

		public Node getPrevNode() {
			return prevNode;
		}

		public void setPrevNode(Node prevNode) {
			this.prevNode = prevNode;
		}

		public Node getNextNode() {
			return nextNode;
		}

		public void setNextNode(Node nextNode) {
			this.nextNode = nextNode;
		}

		@Override
		public String toString() {
			return "Node [id=" + id + ", data=" + data + "]";
		}
	}

	static class DoublyLinkedList {
		private Node headNode;
		private Node tailNode;

		public Node getHeadNode() {
			return headNode;
		}

		public void setHeadNode(Node headNode) {
			this.headNode = headNode;
		}

		public Node getTailNode() {
			return tailNode;
		}

		public void setTailNode(Node tailNode) {
			this.tailNode = tailNode;
		}

	}

	private void add(Node newNode) {

		newNode.setNextNode(this.linkedList.getHeadNode());
		newNode.setPrevNode(null);

		if (linkedList.getHeadNode() != null) {
			linkedList.getHeadNode().setPrevNode(newNode);
		}

		linkedList.setHeadNode(newNode);

		if (linkedList.getTailNode() == null) {
			linkedList.setTailNode(newNode);
		}

		this.map.put(newNode.getId(), newNode);

	}

	private void update(Node node) {

		Node prevNode = node.getPrevNode();
		Node nextNode = node.getNextNode();

		if (prevNode != null) {
			prevNode.setNextNode(nextNode);
		} else { // head 노드인 경우
			this.linkedList.setHeadNode(nextNode); // 다음노드를 head 노드로 세팅
		}

		if (nextNode != null) {
			nextNode.setPrevNode(prevNode);
		} else { // tail 노드인 경우
			this.linkedList.setTailNode(prevNode); // tail 노드를 이전노드로 변경
		}

		add(node);
	}

	private void removeTail() {

		Node lastNode = this.map.get(this.linkedList.getTailNode().getId());

		this.linkedList.setTailNode(linkedList.getTailNode().getPrevNode());

		if (this.linkedList.getTailNode() != null) {
			this.linkedList.getTailNode().setNextNode(null);
		}

		lastNode = null; 
	}

	public void put(int id, String data) {

		if (map.containsKey(id)) {
			Node node = this.map.get(id);
			node.setData(data);
			update(node);
			return;
		}

		Node newNode = new Node(id, data);

		if (this.actualSize < CAPACITY) {
			this.actualSize++;
			add(newNode); // 삽입
		} else { 
			System.out.println("cache is full... remove tail");
			removeTail(); // 마지막 노드 제거
			add(newNode); // 삽입
		}
	}

	public Node get(int id) {

		if (!this.map.containsKey(id)) {
			return null;
		}

		Node node = this.map.get(id);
		update(node);
		return node;
	}

	public void show() {
		Node actualNode = this.linkedList.getHeadNode();
		while (actualNode != null) {
			System.out.print(actualNode + " <--> ");
			actualNode = actualNode.getNextNode();
		}
		System.out.println();
	}

	public static void main(String[] args) {
		LRUCache cache = new LRUCache();

		cache.put(0, "A");
		cache.show();
		cache.put(1, "B");
		cache.show();
		cache.put(2, "C");
		cache.show();
		cache.put(3, "D");
		cache.show();

		cache.put(4, "E");
		cache.show();

		cache.put(5, "F");
		cache.show();

		cache.put(6, "G");
		cache.show();

		System.out.println(cache.get(6));
		cache.show();

		System.out.println(cache.get(3));
		cache.show();

		System.out.println(cache.get(4));
		cache.show();
	}

}