Chapter 4 introduced the ADT sorted list, which maintains its data in sorted order. For example, a sorted list of names would be maintained in alphabetical order, and a sorted list of numbers would be maintained in either increasing or decreasing order. The operations for a sorted list are summarized on page 234.

Some operations- sortedisEmpty, sorted Size, and sorted Get, fa- exampleare just like those for the ADT list. Insertion and deletion operations, however, are by value, not by position as they are for a list. For example, when you insert an item into a sorted list, you do not specify where in the list the item belongs. Instead, the insertion operation determines the correct position of the item by comparing its value with those of the existing items on the list. A new operation, locateindex, determines from the value of an item its numerical position within the sorted list.

Note that the specifications given in Chapter 4 do not say anything about duplicate entries in the sorted list. Depending on your application, you might allow duplicates, or you might want to prevent duplicates from entering the list. For example, a sorted list of Social Security numbers probably should disallow duplicate entries. In this example, an attempt to insert a Social Security number that already exists in the sorted list would fail.

Write a no recursive, reference-based implementation of the ADT sorted list of objects as a Java class SortedListRefBased such that

a. Duplicates are allowed

b. Duplicates are not allowed, and operations must prevent duplicates from entering the list.