Due: Friday, March 17, 2017, 11:59 pm

Doubly-Linked Lists

The goal of this lab is to give you an opportunity to implement a doubly-linked lists with Iterators that allow you to traverse the list backwards and forwards.

Tasks

  1. Make a new folder for this week's project.
  2. Copy your LinkedList class from last week.
  3. Re-implement your LinkedList class as a doubly-linked list with a head and a tail pointer and prev/next pointers at each node. It should have the same functionality as the original LinkedList. Add the following methods to your LikedList class:

    • public T removeFirst () removes and returns the first element from the list.
    • public T removeLast () removes and returns the last element from the list.
    • public T get (int index) returns the element at the specified position in the list.
  4. Test your doubly-linked list. It will be graded as part of your project, so be sure to test it well. This means you should test (at a very minimum) adding to an and removing from an empty list, a list with one item, a list with multiple items, clearing a list, and then adding to it again. For a list with multiple items, you should test its ability to add to the list and remove from the beginning of the list, the middle of the list, and the end of the list.

  5. Add support for a backwards iterator.
    • Create another private class called LLBackwardIterator modeled on LLIterator:
      	private class LLBackwardIterator implements Iterator<T>
      

      It should begin at the tail and iterate through the backwards links.

    • Add a method to the LinkedList class to access the iterator:
        // Return a new LLBackwardIterator pointing to the head of the list
        public Iterator<T> backward_iterator() {
            return new LLBackwardIterator(this.tail);
        }
      
    • Then add the following to the end of your main test function.
        System.out.printf( "\nIterating backward %d\n", llist.size());
        Iterator bi = llist.backward_iterator();
        while (bi.hasNext()) {
          System.out.printf("thing %d\n", bi.next());
        }
      

Once you are comfortable with the above tasks, go on to Project 5.

© 2017 Ying Li. Page last modified: .