Name______________________________Name______________________________This lab covers some of the important ideas related to Linked Lists. Here is a link to the API documentation in case you need it. The overall task is to gain experience working with linked lists. There is a file provided to get you started. Create a project for the lab with this file (LinkedList.java).
P1: We will start with a simple linked list. This is already partially implemented for you. The first task involves making all of the methods work as expected. What does the output from the initial testing point out?
Answer: You need to override _____________________ which is inherited from _______________.
Implement this override to display a nice representation of the list (i.e. [this, is, a, list]).
Examine the addFirst method. This creates a Node and assigns its data members in subsequent statements. Add a constructor to the Node class to allow the instantiation and member assignment to occur in a single statement. Replace all four statements in addFirst with a single statement using the new constructor. You can eliminate the local variable temp.
You will have compile errors until you add a second constructor (parameterless) to the Node class. Explain why this is suddenly required.
Answer:
Did you notice that the list displayed on the screen is in the opposite order of the names in the array used to load the ArrayList? Why is this?
Answer:
Change the method called in the first loop in main to use addLast instead of addFirst. Compare the output to what you observed before and to the original array. What do you notice?
Answer:
Adding to the front is easy in a linked list. It requires O(1) (constant) work. Contrast this to adding to the front of a list stored in an array (which requires shifting). How much work is required for adding to the front of an array when it has n elements?
Answer: O(______)
Adding to the end is more work. It is a O(n) operation. Contrast this to adding to the end of a list stored in an array. This will require how much work if the array has n elements?
Answer: O(______)
Study the addLast method. It contains a loop with an important technique, the trailing pointer trick. Notice how last is always one node behind current (last is often called previous for this reason). When current "falls off the end of the list," last is left pointing to the last node of the list.
Adding to the end can be made O(1) through the use of an extra list entry point, a reference to the last item of the list. Add another data member to the LinkedList class (called last) that will always point to the last node in the linked list. Initialize it in the constructor. Modify the addFirst method to maintain this variable correctly.
Add this statement to the end of the addFirst method just for testing:
System.out.println("Added: "+e+" and last node is "+last.data);
Modify the call in your main loop to use addFirst and test. The above line should display the same name as last each time addFirst is called if you are maintaining last correctly. In this method, it only changes when the new item being added is both the first and the last item in the list.
Move the test line to the end of the addLast method, again, just for testing, and change the main loop to use addLast again. You must rewrite addLast without a loop. Be sure you have removed the local declaration of the variable last; you want to use the class's data member instead. Remember that last is either null, or is a reference to the last node of the existing list. Modify addLast to add the new item, and update last appropriately. You should also condense the three statements at the beginning to use your enhanced constructor.
Change main to use addLast inside the first loop. Your test output (last statement of addLast) should display the same name twice in each output.
Change the loop in main to alternate between addFirst and addLast (start with addFirst). Use a boolean to select which add to use, toggling it on each repetition. Who is the first and last person displayed in the list?
Answer: First ________________________ Last ______________________
Add one more method to the class, remove (uncomment it now). This will remove the first occurrence of an item passed in as an argument. It returns true if successful, false if the item is not found. The method will traverse the list until the item is found (use .equals) and then remove it from the list. You will use a trailing pointer. Remember that removing the first item in a list will be a special case. Because we are also tracking the last item, removing the last item will also be a special case. Sometimes removing the first item also removes the last. Be sure first and last are updated correctly. Uncomment the test of remove at the end of main and verify that everything works correctly. Document and print this file.
P2: Three common improvements/enhancements to the standard linked list are to add a dummy header node, to make the list bi-directional, and to make the list circular (removing all null references). This is called a doubly-linked circular list with dummy header node.
Here is a picture of an empty linked list.
Here is a picture of an empty linked list with dummy header node.
Here is a picture of a circular linked list with dummy header node.
Here is a picture of a doubly-linked circular list with dummy header node.
You will convert existing code (DCHLinkedList.java) to utilize this enhanced structure. It is more work to maintain both forward and backward links, but the removal of all special cases streamlines all of the methods. In addition, we can now support List Iterators efficiently (ability to move forward or backward).
Follow these steps to fill in the blanks in the provided DCHLinkedList class.:
1) Node class: Note that there are now three data members. You need to provide implementations for the three constructors. The default constructor should build a Node that points to itself in both directions (If t=new Node(), then t==t.next==t.previous). This is used to create a dummy header node. No null values are allowed (except in the data field). See the picture above.
2) In the list constructor, instantiate a dummy header node that head will reference.
3)
Examine addFirst and addLast methods. These rely on a utility method to
insert data after a Node. Complete insertAfter so a new Node is added
between the nodes x and x.next (called z). Remember, there are no null references,
so there is always a Node after the Node referenced by x (even if it is
the same as the other). Don't forget to increment the list size. Note that this makes adding to the front and end of a list O(1).
4) 
Write the remove utility method. This is given a reference to some Node of the linked list. It will remove it from the list, connecting its previous Node to its next Node. Again, these nodes always exist. Please throw an exception (NoSuchElementException)
if the argument is the dummy header node. The dummy header node is
never to be removed from the list. How can you tell if the argument is
the dummy header node? Easy... compare the references in head and the parameter! Don't forget to decrement the list size and return the data value removed from the list. This method is O(1), but relies on locating the node to be deleted (which is normally O(n)).
5) Complete the first public remove method. This will search for an exact match of the data (using .equals). Use a basic traversal loop. Remember to start on the node after the dummy header. No trailing pointer is needed because we can always go backwards from the current node. Call the utility remove to finish the task if the item is found. Once the search is done, the actual remove is O(1).
6) Complete the remove by position method. This will be done using a list iterator. Since we only need the iterator's remove method, we will declare a local variable of type Iterator<String>. This is polymorphism in action. A ListIterator<String> positioned at location i is obtained from the List. Get the item from the list (via the iterator) and then call the iterator's remove method. Keep in mind that you must call a next or previous method just before remove or the removal will fail. This implementation will be O(n).
7) The listIterator method must instantiate a LItr object positioned at location i. Positioning will take O(n) steps in the average case.
The inner list iterator class (LItr) itself is completed for you. You may wish to look at its contents.
Time for testing. The main method provides some test statements. Uncomment a few at a time to test each feature.
When you are satisfied with the tests, comment out (or delete) all testing statements in main and solve the following problem using three iterators.
Sort the Declaration signers array, and then copy the signers' names into a DCHLinkedList. The big task is to display the signers in numerical order, numbered 1 through last. The display must be in three columns arranged something like this (the numbers at the top of each column may be different depending on the size of the list, this example represents a subset of the names in the lab).
1. Abraham Clark 3. John Penn 5. William Paca
2. Ben Franklin 4. John Witherspoon
Getting this order is simple using three iterators. The sample test code (that you deleted or commented out) illustrated the basic ideas and may be used as a model. The last column may have one or two empty slots at the end (the extra numbers must not be printed). Be sure to test this with the given names, then take out a name and retest, Then add two names and retest. Then add one more and test again. There are extra names in the code that can be added to the array by simply uncommenting.
Get printed copies of your class files. Turn them in to your instructor. Remember documentation.