For this assignment, you will implement a LinkedString class that provides much of the functionality of the String class, but is optimized for splicing. In particular, it should be possible to splice one LinkedString object onto the end of another in O(1) time. Likewise, it should be possible to splice into the middle of another LinkedString object in better than O(N) time, where N is the number of characters in the string.

Internally, your LinkedString class should utilize a singly-linked list of strings, with references to the front and back of the list. For example, the string "CGCGAATTA" might be represented by the linked structure:

Your LinkedString class should have the following constructors and methods:

public LinkedString()

The default constructor should initialize the object to represent an empty string (as an empty linked list).

public LinkedString(String str)

The alternate constructor should initialize the object to represent the specified string (as a list with one node that stores str).

public void splice(LinkedString other)

Splices the other LinkedString onto the end of this LinkedString object. Note: no new nodes should be created when splicing - the operation should be accomplished in O(1) time by reconnecting list references.

public void splice(String other)

Splices the other String onto the end of this LinkedString object. Note: this should also be O(1).

public void splice(int index, LinkedString other)

Splices the other LinkedString into this LinkedString object, starting at the specified index. Note: this will involve traversing the linked list to find the node containing the insertion point, splitting that node if the insertion point appears in the middle of the node's string, and then reconnecting references to splice in the other LinkedString. If the index is negative or greater than the current number of characters stored, the method should throw an IndexOutOfBoundsException.

public void splice(int index, String other)

Splices the other String into this LinkedString object, starting at the specified index. If the index is negative or greater than the current number of characters stored, the method should throw an IndexOutOfBoundsException.

public boolean empty()

Returns true if this LinkedString object represents the empty string. Note: this should be O(1).

public int length()

Returns the number of characters stored in this LinkedString object. Note: this should be O(1).

public char charAt(int index)

Returns the character at the specified index. If the index is out of bounds, the method should throw an IndexOutOfBoundsException.

public String substring(int startInclusive, int endExclusive)

Returns the substring bounded by the specified indexes. If either index is out of bounds, or if startInclusive is greater than endExclusive, the method should throw an IndexOutOfBoundsException.

public String toString()

Returns the String representation of this LinkedString object.