JAVA)

Implement the following String List ADT: A String List is a list (sequence) of strings with the following methods:

1. A constructor that initializes the list to be empty.

2. A boolean isEmpty() method that returns true if the list is empty. Otherwise, it returns false.

3. A boolean isFull() method that returns true if the list is full. Otherwise, it returns false.

4. An int size() method that returns the number of elements (strings) in the list.

5. A void clear() method that sets the list to be empty.

6. A void insert(String newStr, int position) method that throws a RuntimeException, if the position value is not valid in the list (i.e., beyond the current size of the list or being negative). It also throws a RuntimeException, if the list is full. Otherwise, it inserts newStr at position in the list. If position equals the current number of strings in the list, then newStr is simply appended to the list. Otherwise, newStr is inserted at position in the list, and the original string at position and the subsequent strings in the list are moved to the next position in the list. Note that position starts from 0. If, for example, the current number of strings in the list is 3, then a valid position value should be between 0 and 3, inclusively. In this example, if the position value is 3, then newStr will be appended to the end of the list. If the position value is, for example, 0, then newStr will be inserted at the beginning of the list while the original strings at positions 0, 1 and 2 are moved to positions 1, 2 and 3, respectively. In either case, the number of strings in the list becomes 4 after the insertion.

7. A void remove(int position) method that throws a RuntimeException, if the position value is not valid in the list (i.e., beyond the last position of the list or being negative). It also throws a RuntimeException, if the list is empty. Otherwise, it removes the string at position in the list. After the removal, strings that follow the deleted string at position in the list, if any, are moved backward by one position. Note that position starts from 0. If, for example, the current number of strings in the list is 3, then a valid position value should be between 0 and 2, inclusively. In this example, if the position value is 2, then the last string in the list will be simply removed. If the position value is, for example, 0, then the string at position 0 will be removed and the original strings at positions 1 and 2 will be moved to positions 0 and 1, respectively. In either case, the number of strings in the list is reduced to 2 after the removal.

8. A String retrieve(int position) method that throws a RuntimeException if the position value is not valid in the list (i.e., beyond the last position of the list or being negative). Otherwise, it returns the string at position in the list.

9. A void replace(String newStr, int position) method that throws a RuntimeException, if the position value is not valid in the list (i.e., beyond the last position of the list or being negative). Otherwise, it replaces the string at position with newStr. Note that certain methods (e.g., insert) in the ADT throw RuntimeException directly. This should NOT happen in a real implementation. You almost always need to implement your own exception types, which can be a subclass of Exception or RuntimeException depending on the situation. Since we have not covered how to define a new exception type, we use RuntimeException here. In this programming assignment, you are allowed to use RuntimeException. Once we have learned how to defined user exception types, you should not use RuntimeException directly in your solution anymore since the thrown exception should give more information about the error to the user.

Hints

1. You need to specify a default array size in the contiguous implementation since you need to create an array of strings for the list. For the purpose of this assignment, a default array size of 3 should be used. Usually, the default array size can be specified within the class declaration as a private, static and final value as follows:

private static final int DEFAULT_ARRAY_SIZE = 3;

2. You need to declare an instance variable count in the contiguous implementation to indicate the current number of strings in the array. For efficiency purpose, it is also desirable to declare such an instance variable in the linked implementation.

3. The insert method in both classes should check the validity of the position argument. A RuntimeException should be thrown if the position is invalid. For example, you can use

if (position < 0 || position > count) 

 throw new RuntimeException("Invalid position!");

 The remove, retrieve, and replace methods should have a similar implementation as follows:

if (position < 0 || position >= count) 

 throw new RuntimeException("Invalid position!");

4. Note that for the linked implementation, we can assume that it will never be full. Therefore, the implementation of the isFull() method of the LinkedStringList class should always return false.