What data structure should I use to keep track of recently used items?

Question

I need something like a bounded queue where I can only insert say 10 elements. A new element should override the last inserted element. There should be only n distinct elements

I am looking for suggestions in Java by the way.

Answer 1

ITYM an implementation of a LRU algorithm.

• How to set up a simple LRU cache using LinkedHashMap

• Simple LRU Caching with Expiration

Answer 2

This is a classic application for a queue data structure. A stack of size 10 would keep track of the first 10 elements you added to it, whereas a queue of size 10 would keep track of the 10 most recent elements. If you are looking for a "recent items" list, as suggested by the title of your question, then a queue is the way to go.

edit: Here is an example, for visualization purposes:

Let's say you want to keep track of the most recent 4 items, and you access eight items in the following order:

F, O, R, T, Y, T, W, O

Here is what your data structures would look like over time:

access  item      queue          stack
  1      F     [ F . . . ]    [ . . . F ]
  2      O     [ O F . . ]    [ . . O F ]
  3      R     [ R O F . ]    [ . R O F ]
  4      T     [ T R O F ]    [ T R O F ]
  5      Y     [ Y T R O ]    [ Y R O F ]
  6      T     [ T Y T R ]    [ T R O F ]
  7      W     [ W T Y T ]    [ W R O F ]
  8      O     [ O W T Y ]    [ O R O F ]

Removing the top element from a stack removes the item that was most recently added, not the oldest item.

Removing one element from a queue removes the oldest item, so your queue will automatically hold the most recent items.

edit: with thanks to Adam Jaskiewicz, here is some documentation on Java's Queue implementation.