This is a screenshot of my Samsung Galaxy S3's home screen. I have (over a period of time) carefully curated my most recently used apps and placed them on the home screen. This save me a LOT of time, allowing me to quickly launch applications that I have recently accessed. Now wouldn't it be cool if Samsung's TouchWiz did this automatically? Imagine getting rid of all the frustration searching for an app you accessed only an hour ago?
The android home screen is a good use case for a very important data structure. In order to keep the most recently used apps on the home screen, we will need a data structure that keeps track of such applications and automatically removes the Least Recently Used (LRU) app. Our home screen has 12 slots, so the size of our LRU cache would 12. (Do not confuse this with a CPU cache, which needs guarantees of consistency and efficiency. I'm using the term "cache" to simply mean a list of our most recently used applications).
Let us now think about how we can implement an LRU cache. Our cache must support the following operations:
- Keep the most recently used apps at the front of the list.
- When the user opens an app not in the list, add this app to the front of the list.
- If the list is full, remove the least recently used app from the list.
One way to do this would be to use a Doubly Linked List (to store the apps) and a HashMap that stores the appID as the key and a reference to the node in the Doubly Linked List as the value. This would allow us to quickly look if an app (with a particular appID) is present in the list or not (making lookup an O(1) operation). If not present, adding a new node at the head of the list is an O(1) operation. If the list is full, removing+updating the tail of the list is again O(1). Using a doubly linked list also allows to remove a node from the list and promote it to the head of the list in constant time (hence using a singly linked list is not a good idea).
Fortunately for us, java.util provides a data structure that can be used an an LRU cache: the LinkedHashMap(http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html).The LinkedHashMap provides a special constructor to create a hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order).
The LinkedHashMap requires that the removeEldestEntry(Map.Entry) method be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. Here's a simple implementation of an LRU data structure using a LinkedHashMap :
In the implementation below: we pass capacity+1 to the super class because LinkedHashMaps first add a node before deleting the least recently used node.
OUTPUT:
newsstand, viber, whatsapp, maps, amazon, linkedin, youtube, outlook, kindle, facebook, camera, keep,
newsstand, viber, whatsapp, maps, amazon, linkedin, youtube, outlook, kindle, facebook, camera, keep,
RSS Feed
