Java data structures

›Short versionOpen if you only have a minute.

Pick a structure for the operation you repeat, and name that operation’s cost.
ArrayList: get and set by index are constant time. An insert or remove in the middle shifts the tail.
LinkedList is the wrong default list. Index access walks the chain.
HashSet and HashMap answer membership and lookup in average constant time. Order is a separate choice.
TreeSet and TreeMap keep keys sorted at logarithmic cost. Comparison must agree with equality.
LinkedHashMap iterates in insertion order, or in access order when that mode is on.

You have a few thousand names. The next line either jumps to name number 400 or asks whether “Ada” is already present. Those are different questions. A is the layout you choose so the question you actually ask stays cheap.

The collections library answers the common questions with a , a , and a . Under those names sit arrays, hash tables, and trees. The interface on the variable is the contract. The class after new is the .

The cost that matters

An and an ArrayList built on one both answer get(i) in constant time, because the index is an offset into a contiguous row. Inserting at the front of that row slides every later element forward, so the cost grows with the length.

A hash table answers contains and get(key) in constant time on average, when equal objects share a hash code and the codes spread out. A balanced tree answers the same calls in logarithmic time and can walk the keys from smallest to largest.

A diagram of LinkedList shows an insert that only rewires two links. That insert is cheap when you already stand on the node. Finding the node by index is a walk. For a list you read by position, start with ArrayList.

Match the question to the class

Declare the variable with the interface, and construct the class that matches the question you will repeat.

Choose.java

List<String> byPosition = new ArrayList<>();
Set<String> seen = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();
NavigableSet<Integer> scores = new TreeSet<>();

You append names all evening, then later you read them by index in a tight loop. Which list do you construct, and which cost are you protecting?

Construct an ArrayList. Appending is amortized constant time, and each later get(i) is constant time. A LinkedList would turn every index read into a walk from the nearer end.