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:
/**
* 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.
The body of your method should contain approximately a half dozen lines of code. I strongly suggest drawing out two linked lists and drawing arrows to figure out what references need to be changed and in what order.
After you have written the append method,
add the following main method to SentinelDLL.java to test your code.
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);
}
Turn in
Submit via Canvas the a file that contains
your modified SentinelDLL.java, and a file or a screen shot that shows the output from your test run.