Java Collections: Pick by Access Pattern, Not Habit

Quick Answer

Choose by the question your code asks. List keeps order and allows duplicates, Set answers membership, Map answers lookup by key. Default to ArrayList, not LinkedList: LinkedList's O(1) insert only applies through an iterator, and get(i) walks the chain. HashMap guarantees no iteration order, LinkedHashMap keeps insertion order, TreeMap keeps sorted order and rejects null keys. Any object used as a hash key must override equals and hashCode together, and must not change afterwards.

List, Set and Map answer three different questions

Pick the interface by the question your code actually asks, not by whichever class you typed last time.

• List answers "what is at position 3?" and "keep things in the order I added them". Duplicates are allowed.
• Set answers "have I seen this before?". No duplicates, no positions.
• Map answers "what value belongs to this key?". Keys are unique, values need not be.

The most common avoidable performance bug in beginner Java is asking a List a Set question.

// registered is an ArrayList
for (String roll : incoming) {
    if (registered.contains(roll)) {     // scans the whole list every time
        markDuplicate(roll);
    }
}

ArrayList.contains is a linear scan. With 50,000 registered rolls and 50,000 incoming ones, that inner scan runs 50,000 times, so you do billions of string comparisons for a job in which each check should have been a single hash lookup. Change one line, Set<String> registered = new HashSet<>(list);, and each check becomes roughly constant time. Nothing else in the loop changes.

Declare variables by the interface and construct with the class. Then swapping the implementation is a one-word edit rather than a refactor.

List<String> cities = new ArrayList<>();
Map<String, Integer> marks = new HashMap<>();
Set<String> seen = new HashSet<>();

Two factory methods that look interchangeable and are not. List.of(...) is fully immutable and rejects null elements with a NullPointerException. Arrays.asList(...) is a fixed-size view backed by the original array, so set works and writes through, but add and remove do not.

List<String> view = Arrays.asList("Pune", "Kochi");
view.set(0, "Surat");     // allowed
view.add("Nagpur");       // UnsupportedOperationException

List<String> fixed = List.of("Pune", "Kochi");
fixed.set(0, "Surat");    // UnsupportedOperationException

When you need a mutable copy of either, wrap it: new ArrayList<>(List.of("Pune", "Kochi")). Returning an immutable list from a method is usually the right default, as long as the method name or documentation says so.

ArrayList vs LinkedList: the O(1) that is not

The textbook line is that LinkedList inserts in O(1) and ArrayList in O(n), so students reach for LinkedList whenever they expect a lot of insertions. The catch is in the wording. That O(1) applies only when you are already holding the node, which in practice means inserting through an Iterator or ListIterator. Reaching position i in the first place takes O(i), because the list has to walk the chain from the nearer end.

List<Integer> marks = new LinkedList<>(source);

for (int i = 0; i < marks.size(); i++) {
    process(marks.get(i));    // each get() walks the chain: O(n squared) overall
}

The identical loop over an ArrayList is O(n), because get(i) is an array index. If you must use a LinkedList, iterate it with a for-each loop or an explicit iterator; indexed access is the trap.

Memory layout matters as much as the big-O. An ArrayList is one contiguous Object[]. A LinkedList allocates a separate node object per element, each holding the value plus two references. The CPU prefetches contiguous memory, so scanning an array is dramatically friendlier to the cache than chasing pointers scattered across the heap. That is why LinkedList tends to lose even in situations where the complexity looks equal.

ArrayList's real cost is the resize: when the backing array fills, it allocates a larger one, roughly half again as big, and copies. If you know roughly how many elements are coming, pass a capacity, new ArrayList<>(10_000), and the copying disappears. Note also that removing from the middle of an ArrayList is a single bulk memory move, not a per-element loop, which makes it far cheaper than the O(n) label suggests.

Where a linked structure is genuinely right is a queue or a deque with heavy adding and removing at both ends. Even there, ArrayDeque is normally the better choice: it is a circular array with no per-element node object.

Deque<String> queue = new ArrayDeque<>();
queue.addLast("Aarav");
queue.addLast("Ishita");
String next = queue.pollFirst();   // Aarav

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
String top = stack.pop();          // second

The practical rule, for placements and for production: default to ArrayList, use ArrayDeque for stacks and queues, and reach for LinkedList almost never. One last trap that applies to every list: removing an element while a for-each loop is running throws ConcurrentModificationException.

for (String c : cities) {
    if (c.startsWith("P")) cities.remove(c);   // ConcurrentModificationException
}

cities.removeIf(c -> c.startsWith("P"));       // correct

HashMap, LinkedHashMap and TreeMap

All three implement Map and all three give you get and put. They differ in iteration order and in what they demand from your keys.

• HashMap: no order guarantee at all. Roughly constant-time get and put. Allows one null key and any number of null values.
• LinkedHashMap: a HashMap plus a linked list threaded through the entries, so iteration follows insertion order. Slightly more memory.
• TreeMap: a balanced tree sorted by the key's natural order or by a Comparator. Logarithmic get and put. Rejects null keys with a NullPointerException.

The assumption that costs marks in interviews is that a HashMap or HashSet is sorted, because with small integer keys it often looks sorted.

Set<Integer> ints = new HashSet<>(List.of(5, 3, 1, 4));
System.out.println(ints);    // [1, 3, 4, 5] - looks sorted

Set<String> cities = new HashSet<>(List.of("Pune", "Kochi", "Surat", "Mumbai"));
System.out.println(cities);  // [Kochi, Pune, Surat, Mumbai] - neither insertion nor alphabetical

That is a coincidence of Integer.hashCode returning the value itself and the bucket index being derived from the low bits of the hash. Add a larger number, or add enough entries to trigger a resize, and the illusion vanishes. The strings show how convincing the accident can be: drop Mumbai and the remaining three happen to print in alphabetical order, purely because of where their hash codes land in a sixteen-bucket table. Never rely on hash iteration order. If order matters, say which order you want by choosing LinkedHashMap or TreeMap.

The second surprise is that the tree collections decide equality with compareTo, not equals. Two objects that are not equal but compare as zero are treated as the same key.

List<BigDecimal> values = List.of(new BigDecimal("1.0"), new BigDecimal("1.00"));

System.out.println(new HashSet<>(values).size());   // 2 - equals compares scale
System.out.println(new TreeSet<>(values).size());   // 1 - compareTo ignores scale

Neither answer is wrong, but only one of them is what you expected, and the difference is invisible in the declaration. The same applies to any class whose compareTo looks at fewer fields than its equals.

TreeMap earns its extra cost when you need range questions: firstKey, floorKey, ceilingKey, headMap, tailMap, subMap, descendingMap. A HashMap cannot answer "the nearest slot before 6 pm" without scanning every entry.

LinkedHashMap has one more trick. Constructed in access order, with an eviction hook, it is an LRU cache in a handful of lines.

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true);   // true = iterate in access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Your keys decide whether any of this works

HashMap and HashSet find an entry in two steps: hashCode picks the bucket, then equals confirms the match inside it. Override one and not the other and the collection breaks silently.

class Student {
    private final String roll;

    Student(String roll) { this.roll = roll; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Student s && s.roll.equals(roll);
    }
    // hashCode not overridden: inherits the identity hash
}

Set<Student> set = new HashSet<>();
set.add(new Student("CS21"));
System.out.println(set.contains(new Student("CS21")));   // false

The two equal objects landed in different buckets, so contains never reached the equals check at all. The contract is short: equal objects must have equal hash codes; unequal objects may share one, which is just a collision. Generate both together with your IDE, or with Objects.hash and Objects.equals, or let a record write them for you from its components.

record Student(String roll, String name) {}   // equals, hashCode and toString included

The other half of the contract is that the key must not change while it is inside the collection. This is easy to violate with a mutable object or a collection used as a key.

Set<List<String>> seen = new HashSet<>();
List<String> group = new ArrayList<>(List.of("Aarav"));

seen.add(group);
group.add("Ishita");                        // the hash code changes

System.out.println(seen.contains(group));   // false
System.out.println(seen.size());            // 1 - the entry is stranded in the old bucket

The entry is now unreachable by lookup and cannot be removed either, which is a slow memory leak in a long-running service. Prefer immutable keys: String, boxed numbers, enums, or a record whose components are themselves immutable. If a key object genuinely must be mutable, base equals and hashCode only on fields that never change, normally an id.

For sorted collections the equivalent trap is a comparator that is inconsistent, for example one that returns a value based on a mutable field or that is not transitive. Java detects some of these and throws IllegalArgumentException: Comparison method violates its general contract! from the sort. That message is about your comparator, not about your data, and subtracting two ints inside a comparator is a frequent cause because the subtraction can overflow. Use Integer.compare(a, b) instead.

Choosing under time pressure

Reduce the decision to the access pattern and it takes two seconds instead of two minutes.

• Look a value up by a key: HashMap.
• "Have I seen this before?": HashSet.
• Ordered items, read by index, appended at the end: ArrayList.
• Lookup by key but insertion order preserved when you iterate: LinkedHashMap.
• Sorted iteration, nearest-key or range queries: TreeMap or TreeSet.
• Stack, queue or sliding window: ArrayDeque.
• Repeatedly take the smallest or largest remaining item: PriorityQueue.
• Keys are the constants of an enum: EnumMap, which is array-backed and iterates in declaration order.
• Shared between threads: ConcurrentHashMap, not Collections.synchronizedMap.

Sizing matters only when the collection is large. A HashMap rehashes once it is about three-quarters full, so give it headroom above the count you expect. For ten configuration values, none of this matters.

Map<String, Integer> counts = new HashMap<>(200_000);
List<String> rows = new ArrayList<>(expectedRows);

In an interview, three sentences separate a memorised answer from one that shows you have debugged this: say explicitly that HashMap guarantees no iteration order, that ArrayList.contains is linear, and that a custom key needs equals and hashCode together. Those are the three facts that actually cause production bugs.

Finally, the legacy classes. Vector, Hashtable and Stack synchronise every individual method, which is both wasted work when you are single-threaded and insufficient when you are not: two synchronised calls in sequence are still a race, because another thread can act between them. Use ArrayList, HashMap and ArrayDeque for ordinary code, and the java.util.concurrent classes when state is genuinely shared.

Frequently Asked Questions