I'm working on a small feature for a search application: a "Recent Searches" list. The goal is simple: store the last few things a user searched for, make sure we don't have duplicates, and keep them in the order they were entered. It sounds trivial, but this is exactly where most developers waste time by picking the first collection that comes to mind rather than the one that actually fits the access pattern.

The temptation of the ArrayList

My first instinct is always ArrayList. It's the Swiss Army knife of Java. I'll just throw the search terms in there as they come in. Let's look at how that behaves:

List<String> history = new ArrayList<>();
history.add("Java Collections");
history.add("Spring Boot");
history.add("Java Collections"); // Oops, a duplicate

System.out.println(history); // [Java Collections, Spring Boot, Java Collections]

Right away, we have a problem. The user doesn't want to see "Java Collections" twice in their recent history. To fix this, I could manually check if the list already contains the term before adding it. But wait—ArrayList.contains() is a linear search. If this list grows, I'm iterating through the whole thing every single time the user hits "Enter". That's an $O(n)$ operation for every single insertion. Not ideal.

Trading order for uniqueness

Since I care about uniqueness, the obvious pivot is a HashSet. Sets are designed specifically to prevent duplicates, and they do it in constant time ($O(1)$).

Set<String> history = new HashSet<>();
history.add("Java Collections");
history.add("Spring Boot");
history.add("Java Collections");

System.out.println(history); // [Spring Boot, Java Collections] (maybe)

The duplicates are gone, but now I've hit a new wall: the order is completely unpredictable. A HashSet doesn't remember when I added "Java Collections" versus "Spring Boot". For a "Recent Searches" feature, the order is the entire point. If I can't tell the user what they searched for last, the feature is broken.

Finding the middle ground

This is where I usually stop and look at the hierarchy. I need the uniqueness of a Set, but the ordering of a List. Java has a specific tool for this: the LinkedHashSet. It maintains a doubly-linked list running through its entries, which preserves the insertion order.

Set<String> history = new LinkedHashSet<>();
history.add("Java Collections");
history.add("Spring Boot");
history.add("Microservices");
history.add("Java Collections"); // Duplicate, ignored

System.out.println(history); // [Java Collections, Spring Boot, Microservices]

Now we're getting somewhere. We have uniqueness and we have order. But I noticed one detail: if the user searches for "Java Collections" again, it stays at the top of the list (the oldest position) because it was already there. In a real-world app, a repeat search should probably bump that item to the "most recent" position.

To achieve that with a LinkedHashSet, I have to explicitly remove the item before re-adding it. It's a bit of a workaround, but it's still $O(1)$:

String term = "Java Collections";
history.remove(term); 
history.add(term); // Now it's at the end of the insertion order

When a simple set isn't enough

Now, let's say the requirements change. My boss wants to know when each search happened so we can show a timestamp (e.g., "Java Collections - 2 mins ago"). A Set can't do this because it only stores the key.

I could use a HashMap, but as we saw with HashSet, a standard HashMap destroys the order. If I want to map the search term to a timestamp while keeping the search history in order, I'll use a LinkedHashMap.

Map<String, LocalDateTime> history = new LinkedHashMap<>();
history.put("Java Collections", LocalDateTime.now());
history.put("Spring Boot", LocalDateTime.now());

// The LinkedHashMap remembers the order of the keys 
// and gives me the value (timestamp) for each.

When you're choosing your collection, don't just ask "Does this hold my data?" Ask:

• Do I need to prevent duplicates? (Set)
• Does the order of arrival matter? (Linked... or List)
• Do I need to associate this data with another piece of data? (Map)
• How often will I be searching for a specific item? (Set/Map vs List)

Picking the wrong one usually results in you writing a bunch of "helper" code to make the collection do something it wasn't designed for. Use the tool that fits the access pattern.

---

📋 Practical Task

Implement a Fixed-Size LRU (Least Recently Used) Cache

In this exercise, you will build a simplified "Recently Viewed Products" cache for an e-commerce site. The cache should store a maximum of 3 product IDs. If a 4th product is added, the oldest one (the one least recently accessed) should be removed.

Requirements:

• Use a LinkedHashMap to store the product IDs.
• The cache must maintain insertion order.
• Implement a method viewProduct(String productId) that:
  1. Adds the product to the cache.
  2. If the product was already in the cache, it should be moved to the "most recent" position.
  3. If the cache size exceeds 3, it must remove the oldest entry.

Starter Code:

import java.util.*;

public class ProductCache {
    private final int MAX_CAPACITY = 3;
    private LinkedHashMap<String, Boolean> cache = new LinkedHashMap<>();

    public void viewProduct(String productId) {
        // Your logic here:
        // 1. Handle potential duplicate to move it to the end
        // 2. Add the product
        // 3. Check size and remove the first (oldest) entry if necessary
    }

    public void printCache() {
        System.out.println("Recently Viewed: " + cache.keySet());
    }

    public static void main(String[] args) {
        ProductCache myCache = new ProductCache();
        myCache.viewProduct("Laptop");
        myCache.viewProduct("Mouse");
        myCache.viewProduct("Keyboard");
        myCache.printCache(); // Expected: [Laptop, Mouse, Keyboard]
        
        myCache.viewProduct("Laptop"); // Should move Laptop to the end
        myCache.printCache(); // Expected: [Mouse, Keyboard, Laptop]
        
        myCache.viewProduct("Monitor"); // Should remove Mouse
        myCache.printCache(); // Expected: [Keyboard, Laptop, Monitor]
    }
}