This problem deals with List ADTs and implementations. $(30$ pts$)$

Consider the following scenarios, which include an application requiring the storage of a collection, as well as a proposed data structure from among those we have seen so far $($AUList$,$ ASList, LLUList, LLSList$).$ In each case, provide i$.$ at least one strength for the chosen structure, ii$.$ one weakness for the chosen structure, and iii. provide an example of a data structure $($among AUList, ASList, LLUList, LLSList$)$ that is better suited for the task, and explain why. Notes: there are no $$trick questions$$ each scenario does have a better choice of structure! Also, do not consider Stack or Queue implementations as alternatives, even if better suited.

a$.$ A user wants to keep track of a blood donor database associating individuals by name with their blood type $($O$+,$ O$-,$ A$+,$ A$-,$ B$+,$ B$-,$ AB$+,$ AB$-)$ such that

i$.$ Names are rarely added to or removed from the database $($a few per week at most$).$

ii$.$ Frequent searches are made within the list by name $($hundreds of times per day$).$

iii. There is an expected cap on the data size, meaning the max capacity is known in advance.

The chosen data structure for this task is the Array$-$based Unsorted List $($AUList$).$

b$.$ A user wants to keep track of a list of $100$ favorite song titles such that

i$.$ Songs are frequently added to the list, up to the maximum of $100,$ which is never exceeded.

ii$.$ The list is frequently emptied out $($all at once$).$

iii. Searches for individual songs are almost never made.

iv$.$ The order of titles within the list is unimportant.

The chosen data structure for this task is the Linked$-$list Based Unsorted List $($LLUList$).$

c$.$ A user wants to place information about recent sightings of a particular animal $($ex: the location of the sighting$)$ within a collection such that

i$.$ Placing items within the list must be efficient $($O$(1)$ execution time$).$

ii$.$ The maximum number of items within the list is completely unknown in advance.

iii. General searches within the list are uncommon. Instead, it is important that items added to the list most recently are retrieved relatively quickly.

The chosen data structure for this task is the Linked$-$list based Sorted List $($LLSList$).$