For this assignment, you are to write a program which implements a Sorted List data structure using a circular array-based implementation and a driver program that will test this implementation. The Sorted List ADT is a linear collection of data in which all elements are stored in sorted order. Your implementation has to store a single int value as each element of the list and support the following operations: 1. add(x) – adds the integer x to the list. The resulting list should remain sorted in increasing order. The time complexity of this operation should be 0(N), where N is the size of the list. 2. removeFirst() – deletes the first integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 3. removelast() – deletes the last integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 4. exists(x) – returns true if the integer x exists in the list and false otherwise. Time complexity of this operation should be O(log N). 5. tostring() – returns a string representing the sorted set as a space separated list. 0 (N). Requirements Your program should do the following: 1. Implement the Sorted List as the CircularArraySortedList dlass with all the operations implemented using separate methods. 2. In the main method of the same class, implement a driver program that first creates an empty CircularArraySortedList. Then, it repeatedly prompts the user for an input command, performs the corresponding operation, and prints the list to the screen. The prompts should stop when the user types "q". Your program should allow for the following operations to be entered: "ax", where x is some int value - this will perform the add(x) operation on the list "rf"- this will perform the removeFirst() operation and print the returned value to the screen "rl" - this will perform the removeLlast() operation and print the returned value to the screen "ex" - this will perform the exists(x) operation and print the return value ("true" or "false")

For this assignment, you are to write a program which implements a Sorted List data structure using a circular array-based implementation and a driver program that will test this implementation. The Sorted List ADT is a linear collection of data in which all elements are stored in sorted order. Your implementation has to store a single int value as each element of the list and support the following operations: 1. add(x) – adds the integer x to the list. The resulting list should remain sorted in increasing order. The time complexity of this operation should be 0(N), where N is the size of the list. 2. removeFirst() – deletes the first integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 3. removelast() – deletes the last integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 4. exists(x) – returns true if the integer x exists in the list and false otherwise. Time complexity of this operation should be O(log N). 5. tostring() – returns a string representing the sorted set as a space separated list. 0 (N). Requirements Your program should do the following: 1. Implement the Sorted List as the CircularArraySortedList dlass with all the operations implemented using separate methods. 2. In the main method of the same class, implement a driver program that first creates an empty CircularArraySortedList. Then, it repeatedly prompts the user for an input command, performs the corresponding operation, and prints the list to the screen. The prompts should stop when the user types "q". Your program should allow for the following operations to be entered: "ax", where x is some int value - this will perform the add(x) operation on the list "rf"- this will perform the removeFirst() operation and print the returned value to the screen "rl" - this will perform the removeLlast() operation and print the returned value to the screen "ex" - this will perform the exists(x) operation and print the return value ("true" or "false")

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter18: Stacks And Queues

Section: Chapter Questions

Problem 16PE: The implementation of a queue in an array, as given in this chapter, uses the variable count to...

See similar textbooks