For this assignment, you will implement a
SpliceString class that provides much of the functionality of the
String class, but utilizes structure sharing in order to optimize splicing. Internally, your
SpliceString class should utilize a singly-linked list of strings, with references to the front and back of the list. For example, the
sstr1 object below represents the string "ACGTA" using a linked structure with only one node. The
sstr2 object represents the string "TACCGGCCGA" using a linked structure with two nodes.
Since objects of the same class are able to view each other's private data, it is possible to splice one
SpliceString object onto the end of another without having to copy any strings or nodes. Instead, the links in one are connected to the other, as shown below:
As a result, it is possible to splice one
SpliceString object onto the end of another in O(1) time. Likewise, it is possible to splice into the middle of another
SpliceString object in better than O(N) time, where N is the number of characters in the string.
Warning: one consequence of structure sharing is that you should never attempt to splice a
SpliceString (or any portion of that
SpliceString object) onto itself. Otherwise, infinite data structures may result!
SpliceString class (which will be expanded in HW4) should implement the following constructors and methods:
public SpliceString(String str)
public boolean empty()
SpliceStringobject represents the empty string. Note: this should be O(1).
public int length()
SpliceStringobject. Note: this should be O(1).
public void splice(SpliceString other)
SpliceStringonto the end of this
SpliceStringobject. 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)
Stringonto the end of this
SpliceStringobject. Note: this should also be O(1).
public String toString()
As part of your submission, you should include a simple driver class that tests each of these constructors and methods.