One fundamental choice in algorithm (or ADT) design is whether to use arrays or linked lists to store information. Both of these data types have advantages, and disadvantages, and choosing the appropriate one can make the different between constant and linear time operations. For reference, a standard implementation for the nodes of a singly linked list is given below: publ i c c l a s s LinearNode { p r i v a t e LinearNode next ; p r i v a t e T element ; publ i c LinearNode (T elem) { next = n u l l ; element = elem ; } publ i c LinearNode getNext ( ) { r e turn next ; } publ i c void setNext ( LinearNode node ) { next = node ; } publ i c T getElement ( ) { r e turn element ; } publ i c void setElement (T elem) { element = elem ; } } 1. If you needed to store 25 names of students, and wanted to access them quickly, would arrays or linked lists be better? Explain. [2 points]

2. The following snippet of code denes the Recorder interface. The recorder ADT is used to keep of various objects - it is a method of tagging. For example, one might need to keep track of which instant messages (objects) have been displayed to the user. This could be represented by adding items to a Recorder, with the Recorder oering additional functionality to check if a messages was displayed (contained), or undo adding the last element (e.g., window closed before read by user). publ i c i n t e f a c e Recorder { void add ( Item item ) ; //add an item boolean c ont a ins ( Item item) // i s item in the c o l l e c t i o n ? void undo ( ) ; // removes the l a s t item added . } Give an implementation of Recorder that allows the addition of elements in O(1), query of elements in O(n) time, and removing elements in O(1) time. [6 points]