SA-4, due Sep 30
This assignment gives you practice manipulating linked lists.
Assignment
You are to add a method to SentinelDLL.java to append two
lists. The JavaDoc comments and header for the method are:
<![CDATA[
/**
* Appends the list "other" to the end of the list "this",
* and sets the "other" to an empty list.
* the current element of "this" remains the current element of the combined list.
* @param other the list to be appended to this list.
*/
public void append(SentinelDLL<T> other)
]]>
Your code should take constant time. This means that it cannot
remove items one at a time from the second list and add them to the first. It must
manipulate references to combine the two lists. Several references will
need to be changed. I strongly suggest drawing out two linked lists and
drawing arrows to figure out what needs to change and how.
After you have written the append method,
add the following main method to SentinelDLL.java to test your code.
<![CDATA[
public static void main(String [] args) {
SentinelDLL<String> lst1 = new SentinelDLL<String>();
SentinelDLL<String> lst2 = new SentinelDLL<String>();
lst1.append(lst2);
System.out.println("lst1:\n" + lst1);
System.out.println("lst2:\n" + lst2);
lst1.addFirst("cat");
lst1.addLast("dog");
lst1.append(lst2);
System.out.println("lst1:\n" + lst1);
System.out.println("lst2:\n" + lst2);
lst1.clear();
lst2.addFirst("cat");
lst2.addLast("dog");
lst1.append(lst2);
System.out.println("lst1:\n" + lst1);
System.out.println("lst2:\n" + lst2);
lst2 = new SentinelDLL<String>();
lst2.addFirst("eagle");
lst2.addLast("sheep");
lst1.append(lst2);
System.out.println("lst1:\n" + lst1);
System.out.println("lst2:\n" + lst2);
System.out.println("lst1 in reverse:");
for (Element<String> x = lst1.sentinel.previous; x != lst1.sentinel; x = x.previous)
System.out.println(x.data);
}
]]>
Blackboard submission
Submit via Blackboard the zip file of a folder that contains
(1) your modified SentinelDLL.java, and (2) output from your test run.