fork(5) download
copy 
  1. import java.util.HashMap;
  2.  
  3. /**
  4.  * Item Node structure in the LRU Cache
  5.  * @author Prateek
  6.  */
  7. class Item {
  8. 	public Item prev;
  9. 	public Item next;
  10. 	public String key;
  11. 	public String data;
  12.  
  13. 	public Item(){}
  14.  
  15. 	public Item(String key, String data){
  16. 		this.key = key;
  17. 		this.data = data;
  18. 	}
  19.  
  20. 	@Override
  21. 	public String toString(){
  22. 		return this.key+" : "+this.data;
  23. 	}
  24. }
  25.  
  26. /**
  27.  * LRU Cache implementation
  28.  * @author Prateek
  29.  */
  30. class LRUCache {
  31.  
  32. 	public Item head; 
  33. 	public Item tail;
  34. 	public int maxsize;
  35.  
  36. 	//to hold key for every item
  37. 	private HashMap<String,Item> hash;
  38.  
  39. 	public LRUCache(int size) {
  40. 		this.maxsize = size ;
  41. 		hash = new HashMap<String,Item>();
  42. 		head = new Item("0","0");
  43. 		tail = new Item("0","0");
  44. 		head.next = tail;
  45. 		tail.prev = head;
  46. 	}
  47.  
  48. 	/**
  49. 	 * Add item to the beggining of Linked List
  50. 	 * @param item
  51. 	 */
  52. 	public void addItemAtFirst(Item item){
  53. 		item.next = head.next;
  54. 		item.prev = head;
  55. 		head.next.prev = item;
  56. 		head.next = item;
  57. 	}
  58.  
  59. 	/**
  60. 	 * Remove item from the Linked List
  61. 	 * @param item
  62. 	 */
  63. 	public void removeItem(Item item){
  64. 		item.prev.next = item.next;
  65. 		item.next.prev = item.prev ;
  66. 	}
  67.  
  68. 	/**
  69. 	 * @return the value , and remove the node from between and add to the 
  70. 	 *                     the beggining
  71. 	 */
  72. 	public String get(String key){
  73.  
  74. 		Item item= hash.get(key);
  75. 		if(item!=null)
  76. 		{
  77. 			if(hash.size()==1)
  78. 				return item.data;
  79.  
  80. 			removeItem(item);
  81. 			addItemAtFirst(item);
  82. 			return item.data;
  83. 		}
  84. 		else
  85. 			return null;
  86. 	}
  87.  
  88. 	/**
  89. 	 * Insert to hashmap and linkedlist, if size is exceeded remove the tail element
  90. 	 */
  91. 	public void put(String key, String data){
  92. 		Item item = hash.get(key);
  93. 		if(item==null) //item not found 
  94. 		{
  95. 			item = new Item(key,data);
  96. 			hash.put(key,item);
  97. 			addItemAtFirst(item);
  98. 			if(hash.size() == maxsize)
  99. 			{
  100. 				hash.remove(tail.prev.key);
  101. 				removeItem(tail.prev);
  102. 			}
  103. 		}
  104. 		else //item found in the hashmap, update data
  105. 		{   item.data = data;
  106. 			removeItem(item);
  107. 			addItemAtFirst(item);
  108. 		}
  109. 	}
  110.  
  111. 	/**
  112. 	 * Display Cache Content
  113. 	 */
  114. 	public void displayLRUCache(){
  115. 		System.out.println("Items in the Cache");
  116. 		Item temp=head.next;
  117. 		while(temp.next!=null)
  118. 		{
  119. 			System.out.print(temp.data + " ");
  120. 			temp=temp.next;
  121. 		}
  122. 	}
  123.  
  124. 	public static void main(String[] args) {
  125. 		int size= 10 ;
  126. 		LRUCache cache = new LRUCache(size);
  127. 		cache.put( "1","1");
  128. 		cache.put( "2","2");
  129. 		cache.put( "3","3");
  130. 		cache.put( "4","4");
  131. 		cache.put( "5","5");
  132. 		cache.put( "5","15");
  133. 		cache.put( "6","6");
  134. 		cache.put( "7","7");
  135. 		cache.put( "8","8");
  136. 		cache.put( "9","9");
  137. 		cache.put( "10","10");
  138. 		cache.put( "11","11");
  139. 		cache.put( "12","12");
  140.  
  141. 		cache.displayLRUCache();
  142. 	}
  143. }
  144.  
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Items in the Cache
12 11 10 9 8 7 6 15 4
https://ideone.com/6aXkgJ
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!