Implement the ADT character string type, LinkedString , as another implementation of class String in Java. A doubly linked list must be used, as the data structure, to store a list of characters (there is ONLY one external reference, head, to the linked list). This class must be implemented as an immutable class as java class String.

The LinkedString class uses a different data structure, a doubly linked list. This data structure is LinkedString s internal state. An immutable LinkedString object means its linked list cant be altered once the object is created. All characteristics and behaviors of LinkedString objects must be the same as Java String objects. When a LinkedString object calls a method, this LinkedString object and LinkedString object(s) passed into this method must be unchanged during invocation of this method. If the method returns a LinkedString object, a new LinkedString object must be made without changing this LinkedString object and other LinkedString existing objects.

Specify operations to Three overloading constructors: create an empty LinkedString instance. A new character linked list is allocated so that it represents the sequence of 0 characters currently contained in the character list argument. (LinkedString()). create a LinkedString instance containing a sequence of characters. A new character linked list is allocated so that it represents the sequence of characters currently contained in the character list argument. (LinkedString(char[])). create a LinkedString instance containing same sequence of characters as a String instance. A new character linked list is initialized so that it represents the same sequence of characters as the String argument (LinkedString(String)). Other methods (MUST be implemented to enforce object immutability): return the char value at the specified index. The first character in this linked character string is in position zero. (char charAt(int)). Note: This linked string must be kept immutable. concatenate the specified linked character string to the end of this linked character string (LinkedString concat(LinkedString)). Note: This linked string and the specified linked string must be kept immutable. returns true if, and only if, length() is 0. (boolean isEmpty()). Note: This linked string must be kept immutable. return the length of this linked character string (int length()). Note: This linked string must be kept immutable. return a new linked character string that is a substring of this linked character string (LinkedString substring(int, int)). Note: This linked string must be kept immutable.

A doubly linked list must be used, as the data structure, to store a list of characters (there is ONLY one external reference, head, to the linked list). A doubly linked list must be designed and implemented first, and then it can be uses as the data structure of ADT Character String. The design of doubly linked list has been discussed in class, you must implement it, and use it as part of this project. Use Object as the element type of a node in a doubly linked list. Implement LinkedString so that it is consistent with the String class. A LinkedString object must be an immutable object.

To test LinkedString design, all operations in the design must be tested. This can be done as follows: Create an array list of LinkesString objects using testing data stored in a text file, and check emptiness of all linked strings. Display all linked strings and their lengths in the array list. Retrieve the last character or mid character of each LinkedString object from the array list, and display them. Display all linked strings in the array list again to make sure that all objects are not changed. Concatenate a linked string with next linked string, and display the concatenated string, repeat for the entire array list. Display all linked strings in the array list again to make sure that all objects are not changed. Get sub strings and display both substrings and original strings. Test other methods. It is not efficient to let main to do all. Method main should be very small and should be the only method in the class. It should invoke a method (start) that is decomposed into more methods (createList, displayList,) in a separate class. Every method should be designed as a single-minded method. For example, Class LinkedStringTest contains method main; class LinkedStringUtility is a helper class. Both classes are used for testing.

public class LinkedStringTest{

public static void main(String[] args){

LinkedStringUtility.start();

} }

Note: This class shows only two methods. You must design/implement the rest of the class.

public class LinkedStringUtility {

/** * Creates a list of LinkedString objects and operates on them. */

public static void start(){

ArrayList list;

/** * Create an array list of LinkesString objects using testing data * stored in a text file. */

list = createList();

/** * Display all linked strings in the array list. */

10 displayList(list);

//The rest of the testing methods must be completed by yourself. }

}

Testing data file: A linked string can be made with a string or an array of characters. To test the design of ADT Character String, you may store a list of names like this in a file. Read some of them as strings, and create linked strings with them. Continue to read more strings, convert them into char arrays, and use char arrays to make more linked strings.

Josh

Ahmad

Mike

Sarah

Ali

David