ArrayList, LinkedList, HashSet, Vector

ArrayList, LinkedList, HashSet, Vector Interview with follow-up questions

1. What is the difference between ArrayList and LinkedList in Java?

Both implement List, but differ in their backing data structure and performance:

  • ArrayList — backed by a resizable array. O(1) random access by index (get(i)); amortized O(1) append; but O(n) insert/remove in the middle (elements shift). Cache-friendly and compact.
  • LinkedList — a doubly-linked list. O(1) insert/remove at the ends (and at a known node via an iterator); but O(n) access by index (it walks the chain). Higher per-element memory overhead (node objects + pointers).
ArrayList LinkedList
get(i) O(1) O(n)
add at end O(1)* amortized O(1)
insert/remove middle O(n) (shift) O(n) to find + O(1) to unlink
memory low higher

The practical 2026 framing interviewers want: default to ArrayList — it's faster in the vast majority of real cases (better cache locality), even for many insertions. LinkedList is rarely the right choice; its theoretical insert advantage is undercut by the O(n) traversal to reach the position and poor cache behavior. Reach for LinkedList mainly when you need a Deque/queue with frequent add/remove at both ends — and even then ArrayDeque is usually the better queue/stack implementation. So the honest answer is "ArrayList for almost everything; ArrayDeque for queues; LinkedList seldom."

↑ Back to top

Follow-up 1

How does insertion and removal in ArrayList and LinkedList differ?

Insertion and removal operations in ArrayList and LinkedList have different performance characteristics.

  • ArrayList: Insertion and removal at the end of the list (appending) is fast, as it can be done in constant time. However, inserting or removing elements in the middle of the list requires shifting all subsequent elements, which can be slow and has a time complexity of O(n).

  • LinkedList: Insertion and removal at both ends of the list (head and tail) is fast, as it can be done in constant time. Insertion or removal in the middle of the list requires traversing the list to find the desired position, which has a time complexity of O(n).

In summary, ArrayList is more efficient for appending elements or performing operations at the end of the list, while LinkedList is more efficient for inserting or removing elements at the beginning or end of the list.

Follow-up 2

In what scenarios would you prefer LinkedList over ArrayList?

LinkedList is preferred over ArrayList in the following scenarios:

  1. When frequent insertion or removal of elements at the beginning or end of the list is required, as LinkedList provides constant time complexity for these operations.

  2. When memory efficiency is a concern, as LinkedList uses more memory than ArrayList due to the additional pointers required for maintaining the linked structure.

  3. When the list size is expected to change frequently, as LinkedList does not require resizing like ArrayList.

However, it's important to note that LinkedList has slower performance for random access and iteration compared to ArrayList, so it should be used judiciously based on the specific requirements of the application.

Follow-up 3

How does the performance of ArrayList and LinkedList vary?

The performance of ArrayList and LinkedList varies based on the type of operations performed:

  • Random Access: ArrayList provides fast random access to elements based on their index, as it uses an underlying array. The time complexity for random access is O(1). LinkedList, on the other hand, requires traversing the list from the head or tail to reach the desired index, resulting in a time complexity of O(n).

  • Insertion and Removal: ArrayList performs well for insertion and removal at the end of the list (appending), as it can be done in constant time. However, inserting or removing elements in the middle of the list requires shifting all subsequent elements, resulting in a time complexity of O(n). LinkedList performs well for insertion and removal at both ends of the list, as it can be done in constant time. Insertion or removal in the middle of the list requires traversing the list, resulting in a time complexity of O(n).

In summary, ArrayList is more efficient for random access and iteration, while LinkedList is more efficient for insertion and removal at the beginning or end of the list.

2. What is a HashSet in Java and when should it be used?

A HashSet is a Set implementation backed by a hash table (internally a HashMap). It stores unique elements (no duplicates), gives average O(1) add/remove/contains, does not maintain order, and permits a single null.

Set tags = new HashSet<>();
tags.add("java"); tags.add("java");   // second add ignored
tags.contains("java");                // O(1) average

Use it when you need fast membership testing or deduplication and don't care about order — e.g. "have I seen this id?", removing duplicates from a list (new HashSet<>(list)).

The crucial gotcha interviewers probe: uniqueness relies on hashCode() and equals() — a HashSet first buckets by hashCode, then compares with equals. So for custom objects you must override both consistently, or duplicates will sneak in / lookups will fail. (Records do this automatically.)

Worth contrasting the alternatives: LinkedHashSet preserves insertion order (slightly more memory), and TreeSet keeps elements sorted (O(log n), requires Comparable/Comparator, no nulls). A modern note: Java 21 added SequencedSet (with LinkedHashSet implementing it) for first/last access and reversed views. Pick HashSet for speed, LinkedHashSet for order, TreeSet for sorting.

↑ Back to top

Follow-up 1

How does HashSet handle duplicate elements?

HashSet does not allow duplicate elements. When an element is added to a HashSet, it checks if the element already exists in the set by calling the equals() and hashCode() methods of the element. If the element is already present, the add() method returns false and the element is not added to the set.

Follow-up 2

What is the impact of null values in a HashSet?

HashSet allows null values. It can store at most one null element. If you try to add multiple null elements to a HashSet, only one null element will be stored as HashSet does not allow duplicate elements.

Follow-up 3

How does HashSet achieve constant time performance for basic operations?

HashSet achieves constant time performance for basic operations by using a hash table data structure. When an element is added to a HashSet, its hash code is calculated using the hashCode() method. The hash code is used to determine the index of the element in the hash table. HashSet uses separate chaining to handle collisions, where multiple elements have the same hash code. This allows HashSet to maintain constant time performance for add, remove, contains, and size operations, even with a large number of elements.

3. What is a Vector in Java and how does it differ from ArrayList?

Vector is a resizable array implementing List — functionally like ArrayList, but with two differences: it's synchronized (every method is thread-safe via locking) and it doubles its capacity when it grows (ArrayList grows ~50%).

Vector ArrayList
Thread safety synchronized (per-method) not synchronized
Growth doubles capacity +50%
Performance slower (locking overhead) faster (single-threaded)
Era legacy (Java 1.0) modern (Java 1.2 Collections)

The crucial 2026 framing interviewers want: Vector is legacy — don't use it in new code. Its per-method synchronization is both slow and insufficient for real concurrency: individual methods are atomic, but compound operations (e.g. "check then add", or iterating) still need external locking, so the built-in synchronization gives a false sense of safety and just adds overhead.

The modern alternatives:

  • Single-threaded → use ArrayList.
  • Concurrent → use CopyOnWriteArrayList (read-heavy) or a proper concurrent collection, or wrap with Collections.synchronizedList(...) if you must — and still lock around compound operations.

Same goes for Vector's subclass Stack (also legacy) — prefer ArrayDeque for stack/queue use. So the answer: Vector ≈ a synchronized ArrayList, but it's outdated; choose ArrayList or a concurrent collection instead.

↑ Back to top

Follow-up 1

Is Vector thread-safe and how does it achieve it?

Yes, Vector is thread-safe. It achieves thread-safety by using synchronized methods. All the public methods of Vector are synchronized, which means only one thread can access the Vector object at a time. This ensures that multiple threads can safely modify the Vector without causing any data corruption or inconsistency.

Follow-up 2

What is the impact on performance due to Vector's thread-safety?

The thread-safety of Vector comes at a performance cost. Since Vector uses synchronized methods, only one thread can access the Vector at a time, even if multiple threads are only reading the data. This can lead to decreased performance in scenarios where thread-safety is not a requirement. If thread-safety is not needed, it is recommended to use ArrayList instead, which is not synchronized and generally faster.

Follow-up 3

How does the capacity growth of Vector and ArrayList differ?

The capacity growth strategy of Vector and ArrayList is different. When a Vector needs to grow its capacity, it doubles the current capacity. This means that if the current capacity is 10, it will be increased to 20. On the other hand, ArrayList increases its capacity by 50% of the current capacity. For example, if the current capacity is 10, it will be increased to 15. This difference in capacity growth strategy can have an impact on memory usage and performance in certain scenarios.

4. How does the performance of ArrayList, LinkedList, HashSet, and Vector compare?

Performance depends on the operation; here's the Big-O picture interviewers expect:

Operation ArrayList LinkedList HashSet Vector
get by index O(1) O(n) n/a (no index) O(1)
add at end O(1)* O(1) O(1) avg O(1)*
insert/remove middle O(n) O(n) find + O(1) unlink n/a O(n)
contains O(n) O(n) O(1) avg O(n)
add/remove/lookup — — O(1) avg —
thread-safe no no no yes (slow)

(*amortized)

Key takeaways:

  • ArrayList — best all-rounder: O(1) indexed access, cache-friendly. Default choice for lists.
  • LinkedList — O(1) ends, but O(n) indexed access and poor cache locality; rarely worth it (use ArrayDeque for queues).
  • HashSet — O(1) average membership/dedup, but no indexing and no order; degrades if hashCode() is poor (collisions → toward O(n), mitigated since Java 8 by treeifying dense buckets to O(log n)).
  • Vector — like ArrayList but synchronized → slower; legacy, avoid.

The framing interviewers reward: choose by access pattern, not folklore — ArrayList for indexed/iteration-heavy work, HashSet for fast lookup/uniqueness, ArrayDeque for stack/queue, and a concurrent collection (not Vector) when you need thread safety. And remember average vs worst case for hash-based structures depends on good hashCode/equals.

↑ Back to top

Follow-up 1

What factors influence the performance of these collections?

The performance of ArrayList, LinkedList, HashSet, and Vector can be influenced by several factors:

  • Size of the collection: The larger the collection, the more time it may take to perform certain operations like insertion, removal, or searching.

  • Type of operations: Different collections have different strengths and weaknesses when it comes to specific operations. For example, ArrayList is efficient for random access, while LinkedList is efficient for insertion and removal.

  • Thread-safety: Synchronized collections like Vector may have slower performance compared to their unsynchronized counterparts due to the overhead of synchronization.

  • Memory usage: The choice of collection can impact the memory usage, especially when dealing with large collections or limited memory resources.

Follow-up 2

How does the choice of collection impact memory usage?

The choice of collection can impact memory usage in several ways:

  • ArrayList and Vector: These collections store elements in a contiguous block of memory, which can result in more memory usage compared to LinkedList. Additionally, Vector is synchronized, which can further increase memory usage.

  • LinkedList: This collection stores elements in separate nodes, which can result in less memory usage compared to ArrayList and Vector. However, each node requires additional memory to store the reference to the next node.

  • HashSet: The memory usage of HashSet depends on the number of elements and the hash table's load factor. As the number of elements increases, the hash table may need to be resized, resulting in increased memory usage.

It's important to consider the trade-off between memory usage and performance when choosing a collection.

Follow-up 3

In what scenarios would you choose one collection over another?

The choice of collection depends on the specific requirements and characteristics of the scenario. Here are some scenarios where one collection may be preferred over another:

  • ArrayList: Use ArrayList when random access to elements by index is a common operation, and the collection does not require thread-safety.

  • LinkedList: Use LinkedList when frequent insertion or removal of elements in the middle of the collection is required, and random access by index is not a common operation.

  • HashSet: Use HashSet when the collection needs to store unique elements and the order of elements is not important.

  • Vector: Use Vector when thread-safety is required, and the performance cost of synchronization is acceptable.

It's important to analyze the specific requirements and characteristics of the scenario to make an informed decision about the choice of collection.

5. How can you iterate over these collections in Java?

Several idioms, from most modern to classic:

// 1. Enhanced for-each (most readable; works for any Iterable)
for (String s : list) { use(s); }

// 2. forEach with a lambda/method reference (Java 8+)
list.forEach(System.out::println);

// 3. Stream API — when you also filter/map/collect
list.stream().filter(s -> s.length() > 3).forEach(this::use);

// 4. Iterator — needed for SAFE removal during iteration
Iterator it = list.iterator();
while (it.hasNext()) { if (cond(it.next())) it.remove(); }

// 5. Index loop (List only, where you need the index)
for (int i = 0; i < list.size(); i++) { use(list.get(i)); }

The gotchas interviewers really want:

  • Don't modify a collection while iterating it with a for-each/stream — it throws ConcurrentModificationException (fail-fast). To remove during iteration, use Iterator.remove() or, more simply, collection.removeIf(predicate) (Java 8+).
  • The index loop is poor for LinkedList (O(n) get(i) → O(n²) overall) — use the iterator/for-each there.
  • HashSet has no index, so only for-each / iterator / stream apply, and order isn't guaranteed.

The current best-practice answer: prefer the for-each loop or forEach for simple traversal, streams for transformation pipelines, and the Iterator/removeIf for modification-during-iteration. This applies across ArrayList, LinkedList, HashSet, and Vector since all are Iterable.

↑ Back to top

Follow-up 1

What are the different ways to iterate over a collection in Java?

There are several ways to iterate over a collection in Java:

  1. Using the enhanced for loop (for-each loop)
  2. Using the Iterator interface
  3. Using the ListIterator interface (for lists only)
  4. Using the Stream API (Java 8 and above)
  5. Using the forEach() method (Java 8 and above)

Follow-up 2

How does the choice of iteration method impact performance?

The choice of iteration method can impact performance in Java. Here are some considerations:

  1. Enhanced for loop (for-each loop): This is the simplest and most readable way to iterate over a collection. However, it may not be the most efficient for large collections, as it creates an Iterator behind the scenes.

  2. Iterator interface: This is a more flexible way to iterate over a collection, as it allows for removal of elements during iteration. It is generally efficient for most collections.

  3. ListIterator interface: This is similar to the Iterator interface, but it is only available for lists. It allows for bidirectional iteration and modification of elements.

  4. Stream API: This is a powerful way to process collections in Java 8 and above. It provides various methods for filtering, mapping, and reducing elements. However, it may have some overhead compared to other iteration methods.

  5. forEach() method: This is a concise way to iterate over a collection using lambda expressions. It is generally efficient for most collections, but it may have some overhead compared to other iteration methods.

Follow-up 3

What precautions should be taken when iterating over a collection?

When iterating over a collection in Java, there are some precautions to consider:

  1. Avoid modifying the collection during iteration: Modifying the collection (e.g., adding or removing elements) while iterating over it can lead to unexpected behavior or even throw a ConcurrentModificationException. If modification is necessary, use the appropriate methods of the Iterator or ListIterator interface.

  2. Use the correct iteration method: Choose the appropriate iteration method based on the requirements of the task. For example, if bidirectional iteration is needed, use the ListIterator interface.

  3. Handle exceptions: Some iteration methods, such as the Iterator interface, may throw NoSuchElementException if there are no more elements to iterate over. Make sure to handle such exceptions appropriately.

  4. Consider performance: Depending on the size of the collection and the specific requirements, choose the iteration method that provides the best performance. For large collections, the enhanced for loop may not be the most efficient choice.

  5. Be aware of thread safety: If the collection is accessed by multiple threads, make sure to use appropriate synchronization mechanisms to ensure thread safety.

6. How does HashMap work internally in Java?

A perennial interview favorite. HashMap stores key/value entries in an array of buckets. To put/get, it computes the key's hashCode(), spreads the bits (to reduce collisions), and maps it to a bucket index. Within a bucket, multiple entries (collisions) are chained:

  1. Buckets + collisions — colliding entries form a linked list; since Java 8, once a bucket exceeds a threshold (8 entries, with table size ≥ 64) it converts to a balanced tree (red-black), improving worst-case lookup from O(n) to O(log n).
  2. Lookup — find the bucket by hash, then use equals() to match the exact key. This is why hashCode()/equals() must be consistent.
  3. Resizing — when size exceeds capacity × load factor (default 0.75), the table doubles and entries are rehashed.

Performance: average O(1) get/put, degrading toward O(log n) under heavy collisions. Gotchas interviewers probe: a bad hashCode() (e.g. constant) degrades it to a list; mutable keys whose hash changes after insertion break lookups; and HashMap is not thread-safe — use ConcurrentHashMap for concurrency (never the legacy Hashtable). Keys may be null (one), as may values.

↑ Back to top

Live mock interview

Mock interview: ArrayList, LinkedList, HashSet, Vector

Intermediate ~5 min Your own free AI key

Your voice and your AI key never touch our servers; the key stays in this browser and is sent only to Google. Only your round scores are saved to track progress.