Which Structure for the Roster?

Back in the chapter on generics we set out to build a roster: a growable collection of Students. We used a DynamicArray<Student>, because at the time it was the only growable collection we had.

We now have a second option. A Student is Comparable by ID, so a SortedArray<Student> works as a roster too, and it keeps its students in ID order at all times. Now that we know the costs of each operation in each structure, we can reason about which structure the roster should use.

The answer is that it depends on how the roster is used.

Operation	`DynamicArray`	`SortedArray`
find a student	$O (n)$	$O (lo g n)$
add a student	$O (1)$	$O (n)$
remove a student	$O (n)$	$O (n)$

Removal costs $O (n)$ either way, so that row does not help us decide. The decision depends on which of the other two operations the roster does more of.

Think about two different courses. In the first one, enrollment closes on the first day. After that the roster hardly changes, but it gets looked up all term, every time a grade is entered or attendance is taken. This roster should be a SortedArray. The adds all happen once, at the start, and every lookup for the rest of the term is $O (lo g n)$ instead of $O (n)$ .

The second course might be a massive open online course (MOOC) where students can enroll and drop all year long. The roster is constantly changing, and lookups are rare. In this case, the roster should be a DynamicArray. The adds are $O (1)$ instead of $O (n)$ , and the occasional lookup is $O (n)$ instead of $O (lo g n)$ .