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.

In Java, String is an immutable object (its internal states, such as data structures, cannot be changed once it's created). Immutable means that once the constructor for an object has completed execution that instance can't be altered. This is useful as it means you can pass references to the object around, without worrying that someone else is going to change its contents. Any method that is invoked which seems to modify the value, will actually create another String. Your LinkedString class must be immutable as well.

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.

ADT Character String (LinkedString)Specification: 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.

ADT Character String Design:

Complete a UML diagram to include all classes that are needed

ADT Character String Reference-based Implementation:

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.

Implement all classes included the design. Javadoc comments should be included during this activity. Class comments must be included right above the corresponding class header. Method comments must be included right above the corresponding method header. All comments must be written in Javadoc format.

ADT Character String Test/Debug:

Note: It is required to store all testing data in a file.

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 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(); }

}

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.

*/

/**

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

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

list = createList(...);

9

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.

Olivia

Oliver

Amelia

Harry

Isla

Jack

Emily

George

Ava

Noah

Lily

Charlie

Mia

Jacob

Sophia

Alfie

Isabella

Freddie

Grace

Oscar