Lists, Maps & Sets Interview Questions & Answers

A unified set of interfaces and implementations for storing groups of objects. The root is Iterable -> Collection, which branches into:

• List — ordered, indexed, allows duplicates (ArrayList, LinkedList).
• Set — no duplicates (HashSet, TreeSet, LinkedHashSet).
• Queue/Deque — ordering for processing (ArrayDeque, PriorityQueue).

Map is part of the framework but not a Collection (it stores key->value pairs, not single elements).

List<String> list = new ArrayList<>();
Set<String> set   = new HashSet<>();
Map<String, Integer> map = new HashMap<>();

Programming to the interface (List not ArrayList) lets you swap implementations freely.

• List — an ordered, indexed sequence that allows duplicates. Access by position.
• Set — an unordered collection of unique elements (uniqueness defined by equals/hashCode).
• Map — key->value pairs with unique keys; not a Collection.

List.of("a", "a", "b");          // [a, a, b] — duplicates kept
Set.of("a", "a", "b");           // throws — duplicate in Set.of
new HashSet<>(List.of("a","a")); // {a} — duplicate dropped
Map.of("k1", 1, "k2", 2);        // {k1=1, k2=2}

Pick by need: ordered/indexed -> List; uniqueness/membership -> Set; lookups by key -> Map.

• ArrayList — backed by a resizable array. O(1) random access by index; O(1) amortized append; O(n) insert/remove in the middle (shifting). Cache-friendly, lower memory overhead.
• LinkedList — a doubly-linked list. O(1) insert/remove at the ends (or at a known node); but O(n) index access (must walk the chain) and higher per-element memory (node pointers).

List<Integer> a = new ArrayList<>();
a.get(1000);          // O(1)
List<Integer> l = new LinkedList<>();
l.get(1000);          // O(n) — walks 1000 nodes

In practice ArrayList wins almost always — its cache locality beats LinkedList even for many insert/remove patterns. Use LinkedList mainly as a Deque/queue.

A HashMap is an array of buckets. To store a key it computes hashCode(), spreads the bits, and maps it to a bucket index. Collisions (keys landing in the same bucket) are chained in a linked list, which converts to a balanced tree (red-black) once a bucket exceeds 8 entries (and the table is ≥64) — keeping worst-case lookups at O(log n) instead of O(n).

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);   // hash("a") -> bucket -> store entry
m.get("a");      // hash("a") -> bucket -> equals() scan -> 1

Lookup/insert are O(1) average. When the size exceeds capacity * loadFactor (default 16 * 0.75 = 12), the table resizes (doubles) and rehashes. This is why a correct hashCode/equals pair is essential.

• Capacity — the number of buckets (always a power of two, default 16).
• Load factor — the fullness threshold (default 0.75). When size > capacity * loadFactor, the map resizes (capacity doubles) and rehashes all entries.

// pre-size when you know roughly how many entries to avoid resizes
Map<String,Integer> m = new HashMap<>(64);

The 0.75 default trades space vs time: lower load factor = fewer collisions but more memory; higher = denser but slower lookups. Pre-sizing a known-large map avoids repeated O(n) resizes during population.

• HashMap — not synchronized, allows one null key and null values, fastest. Use single-threaded or with external synchronization.
• Hashtable — legacy, fully synchronized (every method locks the whole table), no null keys/values. Largely obsolete.
• ConcurrentHashMap — thread-safe with fine-grained locking (per-bin CAS, not a global lock), no null keys/values, high concurrency.

Map<String,Integer> safe = new ConcurrentHashMap<>(); // modern thread-safe choice

For concurrent code, prefer ConcurrentHashMap over Hashtable or Collections.synchronizedMap — it scales far better under contention.

• HashSet — backed by a HashMap; no ordering, O(1) add/contains.
• LinkedHashSet — HashSet + a linked list, so it preserves insertion order; O(1) with slightly more memory.
• TreeSet — a red-black tree; keeps elements in sorted order, O(log n) operations, requires Comparable/Comparator.

new HashSet<>(List.of(3,1,2));       // order undefined, e.g. [1,2,3] or other
new LinkedHashSet<>(List.of(3,1,2)); // [3, 1, 2] — insertion order
new TreeSet<>(List.of(3,1,2));       // [1, 2, 3] — sorted

Choose by requirement: speed -> HashSet; remember order -> LinkedHashSet; sorted/ range queries -> TreeSet.

They mirror the Set variants:

• HashMap — no order, O(1) average.
• LinkedHashMap — insertion order (or access order, enabling easy LRU caches), O(1).
• TreeMap — keys sorted, O(log n), supports range/navigation methods (firstKey, ceilingKey, subMap).

// LinkedHashMap as an LRU cache
var lru = new LinkedHashMap<String,Integer>(16, 0.75f, true) {
  protected boolean removeEldestEntry(Map.Entry<String,Integer> e) {
    return size() > 100;
  }
};

TreeMap's navigation API is its superpower; LinkedHashMap's access-order mode is the classic LRU trick.

Most collection iterators are fail-fast: they track a modCount, and if the collection is structurally modified during iteration (other than through the iterator's own remove), they throw ConcurrentModificationException — failing immediately rather than risking corrupt results.

for (String s : list) {
  if (s.isEmpty()) list.remove(s); // ConcurrentModificationException
}

Iterator<String> it = list.iterator();
while (it.hasNext()) {
  if (it.next().isEmpty()) it.remove(); // safe via the iterator
}
list.removeIf(String::isEmpty);          // cleanest

Fail-fast is best-effort (not guaranteed). Concurrent collections like CopyOnWriteArrayList/ConcurrentHashMap are fail-safe instead — they iterate over a snapshot and don't throw.

• Comparable<T> — the type's natural ordering, implemented by the class itself via compareTo. One ordering per class.
• Comparator<T> — an external ordering object via compare, so you can define many orderings without touching the class.

class User implements Comparable<User> {
  int age; String name;
  public int compareTo(User o) { return Integer.compare(age, o.age); } // natural
}
// alternate orderings without modifying User:
users.sort(Comparator.comparing(u -> u.name));
users.sort(Comparator.comparingInt((User u) -> u.age).reversed()
                     .thenComparing(u -> u.name));

Rule of thumb: one obvious default ordering -> Comparable; multiple/contextual orderings -> Comparator (which also composes nicely with thenComparing).

• Iterator — forward-only traversal of any Collection; supports hasNext, next, and remove.
• ListIterator — a List-only iterator that goes both directions (hasPrevious/previous), exposes indices (nextIndex), and can add and set elements during iteration.

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
  String s = it.next();
  if (s.isBlank()) it.set("(empty)"); // replace in place
}

Use ListIterator when you need to walk backward or modify elements while iterating a list.

An ArrayList holds an internal array. When it fills up, it allocates a larger array (~1.5×) and copies the elements over — an O(n) operation. But because growth happens rarely (geometrically), the average cost of add over many calls is O(1) amortized.

List<Integer> list = new ArrayList<>(1000); // pre-size: skip the resizes
for (int i = 0; i < 1000; i++) list.add(i);

If you know the final size, pass an initial capacity to avoid the repeated copies. Note size() (number of elements) differs from the internal capacity.

Generics give collections compile-time type safety and remove casts. Before generics, collections held Object, so you could insert anything and had to cast on the way out — risking ClassCastException at runtime.

List<String> names = new ArrayList<>();
names.add("Ada");
String s = names.get(0);   // no cast; adding an Integer won't compile

List raw = new ArrayList(); // raw type — unsafe, avoid
raw.add(42);
String bad = (String) raw.get(0); // compiles, ClassCastException at runtime

Generics catch type errors at compile time and make code self-documenting.

Java generics are a compile-time feature. After type checking, the compiler erases type parameters — List<String> and List<Integer> both become raw List at runtime, with casts inserted automatically. This keeps backward compatibility with pre-generics code.

List<String> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();
a.getClass() == b.getClass();  // true — same runtime class

// consequences of erasure:
// new T[]      -> illegal
// x instanceof List<String> -> illegal (only List<?>)

Erasure is why you can't do new T(), create generic arrays, or check a generic type with instanceof — the type info simply isn't there at runtime.

Bounded wildcards control what you can read/write through a generic reference:

• ? extends T — an unknown subtype of T; you can read Ts out, but can't add (the exact type is unknown). A Producer.
• ? super T — an unknown supertype of T; you can add Ts, but reads come back as Object. A Consumer.

The mnemonic is PECS — Producer extends, Consumer super:

void copy(List<? extends Number> src, List<? super Number> dst) {
  for (Number n : src) dst.add(n); // read from producer, write to consumer
}

src produces values (read-only), dst consumes them (write-ok). This is how Collections.copy and friends are typed.

• Queue — FIFO processing; offer/poll/peek. PriorityQueue orders by priority instead of arrival.
• Deque ("deck") — double-ended queue; add/remove at both ends. Works as a queue or a stack.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.pop();  // LIFO -> 2

Queue<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2); q.poll();           // FIFO -> 1

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.peek();        // 1 (smallest first)

Prefer ArrayDeque over the legacy Stack class (synchronized, extends Vector) for stack/queue needs.

• List.of / Set.of / Map.of (Java 9+) — concise, truly immutable, reject null and (for Set/Map) duplicates.
• Collections.unmodifiableList(...) — an unmodifiable view over an existing collection.
• List.copyOf(...) — an immutable copy of any collection.

List<String> a = List.of("x", "y");        // immutable
a.add("z");                                 // UnsupportedOperationException

List<String> backing = new ArrayList<>(List.of("x"));
List<String> view = Collections.unmodifiableList(backing);
backing.add("y");                           // view reflects this — it's a VIEW

Gotcha: unmodifiableList is a view — mutating the backing list still shows through it. List.of/copyOf are genuinely independent and immutable.

• HashMap — one null key, many null values. HashSet — one null element. ArrayList/LinkedList allow nulls.
• Hashtable, ConcurrentHashMap, TreeMap (keys) — no null (TreeMap can't compare null; concurrent maps disallow it to avoid ambiguity).
• List.of/Set.of/Map.of — reject null entirely.

new HashMap<>().put(null, 1);          //
new ConcurrentHashMap<>().put(null,1); // NullPointerException
List.of("a", null);                    // NullPointerException

Avoiding null (using Optional or sentinel objects) sidesteps a whole class of these errors.

java.util.Collections is a toolbox of static helpers that operate on collections: sort, reverse, shuffle, min/max, binarySearch, frequency, unmodifiableXxx, synchronizedXxx, and emptyList()/ singletonList().

List<Integer> nums = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(nums);                 // [1, 2, 3]
Collections.reverse(nums);              // [3, 2, 1]
int max = Collections.max(nums);        // 3

Don't confuse Collections (utility class, plural) with Collection (the interface). Arrays is its array-focused sibling (Arrays.sort, Arrays.asList).

Arrays.asList returns a fixed-size list backed by the array — not a normal ArrayList. You can set elements (it writes through to the array) but can't add/remove (throws UnsupportedOperationException).

List<Integer> l = Arrays.asList(1, 2, 3);
l.set(0, 9);   // writes through to the backing array
l.add(4);      // UnsupportedOperationException

// also: a primitive array gives a 1-element List<int[]>, not List<Integer>!
List<int[]> oops = Arrays.asList(new int[]{1, 2, 3}); // size 1

List<Integer> real = new ArrayList<>(Arrays.asList(1, 2, 3)); // mutable copy

Wrap it in new ArrayList<>(...) for a fully mutable list, and remember autoboxing: pass Integer[], not int[].

A HashSet (backed by a HashMap) treats two elements as duplicates when their hashCode() matches and equals() returns true. So uniqueness depends entirely on a correct equals/hashCode implementation.

class P { int x;
  // no equals/hashCode -> identity-based, "duplicates" stay
}
Set<P> s = new HashSet<>();
s.add(new P()); s.add(new P());  // size 2 (different objects)

If you forget to override them, two logically-equal objects are treated as distinct. If you override equals but not hashCode (or vice versa), the set may store duplicates or fail to find elements.

The map places the key in a bucket based on its hash at insertion time. If you then mutate the key so its hashCode changes, it ends up in the "wrong" bucket — the map can no longer find it, even with the same reference.

Map<List<Integer>, String> m = new HashMap<>();
List<Integer> key = new ArrayList<>(List.of(1));
m.put(key, "v");
key.add(2);                 // mutates the key -> hashCode changes
m.get(key);                 // null! lost in the wrong bucket

Rule: use immutable keys (String, Integer, records, frozen value objects). It's the same reason Python forbids list keys.

Don't call map.remove inside an enhanced-for over its entries — that throws ConcurrentModificationException. Use the iterator's remove, or the cleaner removeIf/entrySet().removeIf, or keySet/values views.

// iterator
Iterator<Map.Entry<String,Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
  if (it.next().getValue() == 0) it.remove();
}
// concise
map.values().removeIf(v -> v == 0);
map.entrySet().removeIf(e -> e.getValue() == 0);

For concurrent access from multiple threads, use ConcurrentHashMap, whose iterators are fail-safe.

Vector and its subclass Stack are legacy synchronized collections from Java 1.0. Every method is synchronized, so they pay locking overhead even in single-threaded code, and that per-method locking doesn't make compound operations atomic anyway.

Deque<Integer> stack = new ArrayDeque<>(); // modern stack
List<Integer> list = new ArrayList<>();    // modern list

Use ArrayList (unsynchronized list), ArrayDeque (stack/queue), and pick a concurrent collection or explicit synchronization when you genuinely need thread safety — not Vector/Stack.

Java 8 added convenience methods that simplify common map idioms:

• getOrDefault(k, d) — value for k, or d if absent.
• computeIfAbsent(k, fn) — compute and store a value only if k is missing; perfect for multimaps.
• merge(k, v, fn) — combine an existing value with a new one; perfect for counting.

// grouping (multimap)
map.computeIfAbsent(key, k -> new ArrayList<>()).add(item);

// frequency count
counts.merge(word, 1, Integer::sum);

int n = counts.getOrDefault("x", 0);

These replace verbose if (map.containsKey(...)) ... else ... blocks and are atomic on ConcurrentHashMap.

A PriorityQueue is a binary heap that always dequeues the highest- priority element (by natural order or a Comparator), not FIFO. offer/poll are O(log n); peek is O(1).

// min-heap (default): smallest first
Queue<Integer> min = new PriorityQueue<>();
// max-heap: reverse the comparator
Queue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
max.offer(1); max.offer(5); max.peek(); // 5

Caveat: it's only ordered at the head — iterating it does not yield sorted order. It's the go-to for "top-K", Dijkstra, and scheduling problems.

• Collections.synchronizedList/Map(...) — wraps a collection so each method locks the whole object. Simple, but compound operations (check-then-act, iteration) still need external synchronization, and there's no concurrency.
• Concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue) — designed for concurrency with fine-grained or lock-free strategies; far better throughput.

List<Integer> s = Collections.synchronizedList(new ArrayList<>());
synchronized (s) {                 // still must lock to iterate safely
  for (int x : s) { }
}
Map<String,Integer> c = new ConcurrentHashMap<>(); // no external lock needed

Prefer the concurrent collections in new code.

CopyOnWriteArrayList makes a fresh copy of the backing array on every mutation, so reads and iteration are lock-free and never throw ConcurrentModificationException (iterators see a stable snapshot). The cost: writes are O(n).

List<Listener> listeners = new CopyOnWriteArrayList<>();
for (Listener l : listeners) l.onEvent(); // safe even if another thread adds

Ideal for read-mostly, write-rarely scenarios with concurrent iteration — classically event-listener lists. Terrible for write-heavy workloads.

Hash-based collections (HashMap, HashSet) locate elements by hash first, then equals. If two equal objects have different hash codes, they land in different buckets and the collection can't recognize them as the same — you get duplicates in a Set or failed lookups in a Map.

class Key {
  int id;
  Key(int id) { this.id = id; }
  @Override public boolean equals(Object o) {
    return o instanceof Key k && k.id == id;
  }
  // forgot hashCode -> equal Keys get different hashes
}
Map<Key,String> m = new HashMap<>();
m.put(new Key(1), "a");
m.get(new Key(1));   // null — wrong bucket

Always override both together, keeping them based on the same fields.

Because they're sorted, TreeMap/TreeSet (the NavigableMap/NavigableSet interfaces) offer range and neighbor queries that hash structures can't:

• first()/last(), floor(x) (≤ x), ceiling(x) (≥ x), lower(x) (< x), higher(x) (> x).
• headSet, tailSet, subSet / headMap, tailMap, subMap for ranges.

NavigableSet<Integer> s = new TreeSet<>(List.of(10, 20, 30));
s.floor(25);    // 20  (largest ≤ 25)
s.ceiling(25);  // 30  (smallest ≥ 25)
s.subSet(15, 35); // [20, 30]

These make TreeMap/TreeSet the choice for "nearest value", ranges, and ordered iteration — at O(log n) per operation.

Specialized, highly efficient collections for enum keys/elements. EnumSet is internally a bit vector; EnumMap is backed by a plain array indexed by ordinal(). Both are much faster and smaller than HashSet/HashMap for enums, and iterate in enum declaration order.

enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }
EnumSet<Day> weekend = EnumSet.of(Day.SAT, Day.SUN);
EnumMap<Day, String> plans = new EnumMap<>(Day.class);
plans.put(Day.MON, "gym");

Whenever your keys are enum constants, prefer these over the general-purpose collections.

Terminal collect with the Collectors factory turns a stream into a collection or grouped structure:

List<String> upper = names.stream()
    .map(String::toUpperCase)
    .collect(Collectors.toList());        // or .toList() (Java 16+)

Map<Boolean, List<Integer>> parts = nums.stream()
    .collect(Collectors.partitioningBy(n -> n % 2 == 0));

Map<Dept, List<Emp>> byDept = emps.stream()
    .collect(Collectors.groupingBy(Emp::dept));

Collectors covers toSet, toMap, groupingBy, partitioningBy, joining, and counting — declarative replacements for manual loop-and-add.

List has two overloads: remove(int index) removes by position, and remove(Object o) removes by value. With a List<Integer>, passing a primitive int calls the index version — not the value one.

List<Integer> list = new ArrayList<>(List.of(10, 20, 30));
list.remove(1);                 // removes INDEX 1 -> [10, 30]
list.remove(Integer.valueOf(10)); // removes the VALUE 10 -> [30]

To remove a value, box it explicitly with Integer.valueOf(x) (or cast to (Integer)). This is one of the most common surprise bugs with integer lists.

Match the data structure to the dominant operation:

• Ordered list, index access, mostly appends -> ArrayList.
• Unique elements, fast membership tests -> HashSet.
• Key->value lookups -> HashMap.
• Need sorted order or range queries -> TreeMap/TreeSet.
• Preserve insertion order -> LinkedHashMap/LinkedHashSet.
• FIFO queue / stack -> ArrayDeque; priority -> PriorityQueue.
• Concurrent access -> ConcurrentHashMap, CopyOnWriteArrayList.

Map<String,Integer> wordCount = new HashMap<>();   // counting
Set<String> seen = new HashSet<>();                // dedupe

Start from the access pattern (lookup? order? uniqueness? concurrency?) and the choice usually falls out.