Segment 18.3 considered three ways to avoid the pitfall of a sorted list inheriting the add-by-position and replace-by-position operations from the ADT list. Revise the class SortedList that Segment 18.1 describes by overriding add and replace and changing their behaviours as follows:
An application profiler measures the time or space complexity of a piece of software. Implement an application profiler that uses simulation to assess the time complexity of various implementations of the ADT sorted list. In particular, consider an application that uses a sorted list of integers in the following way:
65% of the sorted list operations add new entries to the list
10% of the sorted list operations remove entries from the list
15% of the sorted list operations retrieve either the entry at a given position or the position of a given entry
10% of the sorted list operations test whether an entry is in the list
To begin the simulation, create a sorted list of 5,000 randomly generated integers between 0 and 10,000. Then, inside a loop, randomly generate an integer, an Entry, between 0 and 10,000, and randomly choose a sorted list operation based on the previous percentages. Next, perform the operation with an Entry. Simulate between 100,000 and 1 million operations and record the total time used. Use LinkedSortedList from Chapter 17 and then repeat the simulation using LinkedSortedList that you completed in Project 1 of this chapter. Which implementation of the ADT sorted list performs the best?