Java Data Structures: Choose Lists, Sets, Maps and Queues - Yenra

Choose the interface before the implementation

A collection interface describes behavior; its implementation supplies a storage strategy. A List keeps positions and permits duplicates. A Set represents unique elements. A Map associates keys with values, and is a separate hierarchy from Collection. A Deque supports insertion and removal at both ends, so it can express a queue or stack. See the official Collections Framework overview.

On a narrow screen, scroll the table horizontally. Keyboard users can focus the table and use the arrow keys.

Declare variables using the interface when client code only needs that contract. Choose a concrete implementation at construction. This keeps storage decisions visible without coupling every method to them.

Use one input four ways

This invented visitor list includes Ada twice. Java 25 and a plain-text editor are sufficient; the program uses only JDK classes. Save the file as CollectionsDemo.java, or extract the download.

Download the collection example and instructions (ZIP)

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<String> visits = new ArrayList<>(List.of("Ada", "Lin", "Ada", "Sam"));
        Set<String> firstSeen = new LinkedHashSet<>(visits);
        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String name : visits) counts.merge(name, 1, Integer::sum);
        Deque<String> waiting = new ArrayDeque<>(firstSeen);

        System.out.println("Visits: " + visits);
        System.out.println("First seen: " + firstSeen);
        System.out.println("Counts: " + counts);
        System.out.println("Next: " + waiting.removeFirst());
        System.out.println("Waiting: " + waiting);

        List<String> snapshot = List.copyOf(visits);
        visits.add("Jo");
        System.out.println("Snapshot size: " + snapshot.size());
        if (!counts.equals(Map.of("Ada", 2, "Lin", 1, "Sam", 1)))
            throw new AssertionError("Incorrect counts");
        if (snapshot.size() != 4 || visits.size() != 5)
            throw new AssertionError("Snapshot should retain four entries");
    }
}

javac CollectionsDemo.java
java CollectionsDemo

Visits: [Ada, Lin, Ada, Sam]
First seen: [Ada, Lin, Sam]
Counts: {Ada=2, Lin=1, Sam=1}
Next: Ada
Waiting: [Lin, Sam]
Snapshot size: 4

The list retains all four observations. The linked set retains three unique names in first-seen order. The map increments the value already associated with each name using merge. The deque starts from the unique visitors and removes Ada from the front. That choice means this queue serves each named visitor once, while the original list remains a visit log.

Changing the set and map to hash-based implementations without ordering would preserve membership and counts, but the printed iteration order would become unspecified. A stable-looking order in one run is insufficient evidence of an ordering guarantee.

Define what counts as the same key

For strings, equality compares content. For a custom key type, decide whether identity means a database ID, a composite value or a particular object instance. If two keys compare equal, their hash codes must match. Fields participating in that equality should stay stable while the key is in a hash-based map or set.

For example, a customer record keyed by an immutable customer ID keeps its identity even when its display name changes. Using a mutable name field as part of a key can make an entry difficult to find after an update. The guide to immutable map keys explains the failure mechanism. A record containing immutable components can be a useful value key; a record containing a mutable list still needs careful ownership.

Sorting also participates in identity for sorted sets and maps. A comparator that compares people only by last name treats two people with the same last name as equivalent for that sorted structure. Add a stable distinguishing field if both must coexist. Check this with two deliberately colliding examples before loading real data.

Interpret complexity with the actual workload

ArrayList.get takes constant time; appending has amortized constant cost, while inserting or removing inside the list can shift many elements. Hash-map lookup has expected constant cost under suitable hash distribution. A TreeMap supplies logarithmic lookup and update with sorted keys. These describe how work tends to scale with element count, not a stopwatch result for your machine.

The implementation contracts are documented in ArrayList, HashMap and TreeMap. Memory layout, allocation and the cost of comparing keys also matter. A linked list can unlink a node cheaply once its position is known, but walking to an indexed position still costs time.

Write down your dominant operations: 100,000 appends followed by sequential reading is different from repeated insertion at known positions or sorted range queries. Measure a representative workload only after verifying that both candidate implementations produce the same result. A tiny loop with no warmup is a poor basis for a general performance ranking.

Keep mutation and concurrency explicit

In the example, List.copyOf(visits) creates an unmodifiable snapshot of the list contents. Appending Jo to the original list leaves the snapshot size at four. The copied references still refer to the same element objects, so a snapshot of mutable objects does not freeze their internal fields. The List.copyOf contract also specifies rejection of null elements.

Ordinary ArrayList, HashMap and ArrayDeque instances need an explicit sharing policy when multiple threads mutate them. A concurrent collection can protect its individual operations, but a multi-step business rule may still require an atomic operation or a lock. The concurrency guide demonstrates why reading and then writing a shared value can lose an update.

Try three checks: add another Ada and verify that the visit count grows while unique membership stays the same; replace first-insertion order with alphabetical order; and remove items until the queue is empty. For an empty queue, pollFirst returns null while removeFirst throws. Choose the behavior your calling code can handle, then test it deliberately.