Linked lists with tail element

The aim of this part is to modify the LinkedList class so that it includes a reference to the last node in the list, as well as to the first. Your new class will need a private instance variable

  private ListNode tail;

which should always hold a reference to the last node in the list, if there is one, whatever other operations are performed on the list.

To help you do this, copy the two files ListNode.java and LinkedList.java to somewhere in your own area. There is no need to change ListNode.java, but you will need to edit your copy of LinkedList.java. (You may like to take a copy of the original first.)

You will need to modify the constructor for the LinkedList class as well as the following methods:

  public void addFirst (Object item);
  public void removeFirst (Object item);
  public void reverse ();
  public Iterator iterator ();

In addition you should write three new methods

  public Object lastItem ();
  public void addLast (Object item);
  public void removeLast ();

lastItem should return the item in the last node of the list, raising an exception if the list is empty. addLast should insert the item as the last element of the new list. removeLast should remove the last node from the list, raising an exception if the list is empty.

Now copy the test file ListDemo.java to your working directory and run the test on your revised version of the LinkedList class. (You may like to run just parts of it, to test what you have done so far, as you go along.)
Show the output as part of your submission.
If you have only been partly successful, write a similar test program to illustrate where it works, and where it doesn't.