In this lab you are going to implement a doubly linked list.
The file LinkedList.java contains a template for a linked list class. This class is slightly different from the class that we created in class. First, it has two pointers, next and previous, instead of just one pointer. This allows the list to be traversed either forward or backward. Second, it has an addAt method that has a parameter that specifies where to add an element into the linked list. The version we created in class always added to the end. Since we do not have index access to elements in the list, this method specifies where to add by specifiying a node (a LinkedList object) in the list. Because we do not want to expose the recursive nature of this class to the user, this method is private. It is called by the addFirst and addLast methods, as well as by the iterate sub-class.
Complete the addAt method. The method should insert the specified object before the specified node in the linked list. If the node is null then the object should be added to the end of the list. Note that if the object is being added to either the beginning or end of the list, then the static pointers to the begining or end of the list must be updated. The image below illustrates how a node is added to a linked list. You could test your program by using the debugger, but for larger lists this can be difficult. Instead complete the toString method and use it to test your add method.
Complete the removeAt method. The method should remove the specified node from the linked list. If the list is empty or the specified node is null, the method should throw an exception. Note that, like the addAt method the first and last pointers may need to be updated after removing a node. The image below illustrates how a node is removed from a linked list. Test your remove method before proceeding.
The LinkedList class has a sub-class that implements iterable in order to provides access to interior nodes of the linked list through iteration. The constructor to the class should take a LinkedList object and initialize an instance variable to represent that the current element in the iteration is the first element in the LinkedList. The hasNext method should return true if there is a node after the current node in the list and false otherwise. The next method should return the element in the list after the current node and update the current element to be the element returned. The add method should call the addAt method to add an element to the list. The remove method should call the removeAt method to remove an element to the list. Be sure to test your code.
To submit your code: Tar your lab8 directory and submit your code on the course Inquire site.