SA-4

Exercises

1. Make a new generic class SinglyLinkedHT<T> that keeps track of not just the head but also the tail of the list. If the list is empty, the tail is just null; else it is the last element in the list. When adding and removing elements, the tail will have to be updated properly.
2. Draw box-and-pointer diagrams showing the linked list elements and the head and tail pointers after each of the following method calls:

   SinglyLinkedHT<String> list = new SinglyLinkedHT<String>();
   list.add(0, "a");
   list.add(1, "b");
   list.add(0, "c");
   list.remove(0);
   list.remove(1);
   list.remove(0);

3. We can use the tail pointer to to provide an efficient way to append two lists. Draw box and pointer diagrams (with linked elements and head and tail pointers) for one list with {a,b,c} and another with {x,y,z}. Now show how to manipulate the pointers, without looping over either list, such that the second list is "glued" onto the end of the first list, i.e., the first list is now {a,b,c,x,y,z}.
4. Write a method append such that calling list1.append(list2) would manipulate the pointers according to your diagram. As in the diagram, your code should not loop over either list. Be sure to update list size and handle cases where either or both lists are empty.

The code is largely based on SinglyLinked. You can do that yourself, or start with this copy SinglyLinkedHT.java, which includes some testing code, a placeholder for the new method, and a reminder that you'll have to update some old methods too. Also download a simpler version of our List interface that does not have an iterator (a topic we will cover next class) called SimplerList.java.

Submission Instructions

Turn in your completed Java code and results from the test case. For the diagrams, you may draw on paper or with a drawing program or with a word processor (in which case it's fine to just write text with "->", etc.). Either way, the submission is still electronic, so if you draw on paper than scan it in or take a respectable picture with your phone.