Collections and Data Structures

Basic Q&A

What is a collection? It contains other objects.

Why does the abstract Collection<T> type exist? As a base class for the hierarchy, mostly for generic methods (e.g. "remove from List a the collection of elements from (List b, Set c, Queue d, …).

When do I need to use type X? Almost never! Very few types are mandatory to use in Java.

When should I use a List? To store sequential elements. The obvious case is when you really care about order (e.g., if you care what order elements were added in, or if you intend to sort the elements). Actually, many other use cases make sense for performance reasons.

When should I use a Set? When you care about uniqueness and “belongingness”. It’s reasonably common to copy everything in a List into a Set in order to remove duplicates. If you keep elements in a Set, it can efficiently answer questions like “is element x currently in the Set”?

When should I use a Queue (or Deque)? Queue describes a FIFO (first-in-first-out) queue, meaning that the intended operations involve adding elements to the “back” then removing them from the “front”. This is fairly common in Computer Science.

What about the Stack interface? No such thing; java.util.Stack is a class. Really, the core operations of a LIFO (last-in-first-out) stack are implemented by any reasonable List implementation: all you need are efficient methods to add or remove from the back.

When should I use a Map? When you need to map keys to values (name to phone number, misspelled word to corrected word, color name to color code, etc.)

Quiz: choosing data structures

Here are some scenarios. In each case, which data structure(s) would you use? Which data structure(s) are completely unnatural to use (meaning they are the wrong abstraction for the problem)?

Quiz, round two

Answer the questions above, but say which concrete implementations you would choose for the interfaces (ArrayList or LinkedList? HashSet or LinkedHashSet or TreeSet?).