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()
public LinkedString(String str)
str
).
public void splice(LinkedString 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)
String
onto the end of this LinkedString
object. Note: this should also be O(1).
public void splice(int index, LinkedString 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)
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()
LinkedString
object represents the empty string. Note: this should be O(1).
public int length()
LinkedString
object. Note: this should be O(1).
public char charAt(int index)
IndexOutOfBoundsException
.
public String substring(int startInclusive, int endExclusive)
startInclusive
is greater than endExclusive
, the method should throw an IndexOutOfBoundsException
.
public String toString()
LinkedString
object.
LinkedString
methods, such as indexOf
, contains
, and remove
.