Lab 2 - Generic, Doubly-Linked List (100 pts)

Due Monday, October 8 at 11:59pm on Canvas


Pair Programming Extra Credit Opportunity (5 pts)

  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit this file.
  • Only one partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.
  • Both partners follow the rules for pair programming.

Part 1: Making Your Lab 1 List Class Generic

  • For this Lab, you will need to convert your List class to become a generic class.
  • The purpose of using generics in this assignment is to allow the List to store any (Object) type.
  • Note that the previous Lab only stored data of the primitive type int
  • To store other data types, we do not want to have to write a whole new list class for each type, e.g. one for Strings, one for numerical data, and one for each type of Objects of other classes (such as classes that you write).
  • Fortunately, generic types exist in Java, which allow you to specify that any type of (non-primitive) Object be stored inside the same List class.
  • Note: primitive types - int, double, boolean, char - do not work with generics. Use their Object counterparts instead - Integer, Double, Boolean, and Character.
  • Other advantages of generics, include:
    • Strong type checking at compile time - The Java compile verifies at compile time that the type you specified the class to store, and any operations you make on data of that type, are legal.
    • Algorithms implemented as generic methods or classes are type-safe, generalized (not specific to one type only), and easy to read.
  • You will need to specify that you List holds a generic type of objects (not ints anymore).
  • To do so, follow these steps:

Step 1:

  • Open up your List.h file and add the following to the class definition:
public class List<T> {

Step 2:

  • Alter the Node definition to also work with generic data (we don't want it just to store ints anymore!):
private class Node {
private T data;
private Node next;

public Node(T data) {
this.data = data;
this.next = null;
}
}

Step 3:

  • for EACH method in the List class, you will need to examine it to determine whether it needs to be altered to work with our new generic class.
  • The Eclipse error messages can help you determine which methods need to change.
  • Below are two examples, where int has been updated to T:
Access Method Example:

    /**
     * Returns the value stored in the first node
     * @precondition length != 0
     * @return the integer value stored at node first
     * @throws IllegalArgumentException when the
     * precondition is violated
     */
    public T getFirst() throws NoSuchElementException{
        if (length == 0) {
            throw new NoSuchElementException("getFirst(): "
                    + "List is empty. No first element.");
        }
        return first.data;
    }

Mutator Method Example:

    /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition a new first element
     */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first = N;
        }
        length++;
    }

  • Reflection: Will methods such as getLength() and isEmpty() need to change?
Step 4:
  • Inside of ListTest.java, alter any calls to your List constructor to specify the type of data being stored by placing the type in angled brackets next to the word List.
  • The easiest approach would be to indicate the List stores type Integer so that your tests remain compatible with your new List class.
List<Integer> L1 = new List<Integer>();
  • Now, declare some new Lists of various types, such as String and Double.
    • Verify that your List works with these types as well. 

For More Information:

  • Read the Oracle Generics Tutorial here
  • Read chapter 5 of the course textbook

Part 2: Creating a Doubly-Linked List Class

  • The next part of your assignment is to alter the List class that you wrote in Lab 1 to be a doubly-linked list.
  • The principle difference between the singly-linked list that you wrote in Lab 1 and a doubly-linked List is that each node contains a reference to both to the next node and to the previous node in the List.
  • You can visualize a doubly-linked list like so:

Image source.

  • Therefore, your inner Node class will be updated to look like the following:

private class Node {
private T data;
private Node next;
private Node prev;

public Node(T data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
  • Additionally, bear in mind that the first Node of the list now has a prev Node reference to null while the last Node has a next Node reference to null.
  • The advantage of the prev reference is the ease with which we can traverse the list in both directions, and also perform some more challenging operations such as removeLast().
  • To account for the presence of this additional reference variable in the Node class, you will need to make updates to your code for many of the List methods.
  • Most of these updates are as simple as adding one line of code to the method.
  • For example, let's look at the insertFirst() method:
      /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition a new first element
     */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first.prev = N;
            first = N;
        }
        length++;
    }
  • Important! Each time you update one of your methods, run your tests again to make sure your List is still working properly.
  • If you want more information on doubly-linked lists, you can watch this short video (8 min).


Part 3: Adding New Functionality to your List Class

  • Your doubly-linked list needs to be able to perform all of the same operations as your singly-linked list.
    • However, as you may have noted when writing Lab 1, the Lab 1 List class was very limited.
    • You could only add and remove data at the two ends of the List
    • What about the middle of the List?
  • How can we access data or insert and remove data from the middle of the List?
  • To increase the functionality of our class, we will be adding some new methods and a new field to the List.
  • First, add a new private field to the class to store the iterator - a node reference that we will use to move around the List container.
  • Unlike the first and last Nodes, which must always remain in the same location, the iterator will need to change positions in the List.
private int length;
private Node first;
private Node last;
private Node iterator;

  • All of the required methods for this lab are described below:


Constructors:

constructor: constructs a new linked list object.
copy constructor
: makes a copy of this list object

Mutators:

removeFirst: removes the element at the beginning of the list   
removeLast:
removes the element at the end of the list
<--Important: Rewrite for this Lab! Remove while loop
addFirst:
inserts an element at the beginning of the linked list

addLast:
inserts an element at the end of the list
pointIterator: moves the iterator to the start of the list
removeIterator: removes the element currently pointed to by the iterator. Postcondition: Iterator then points to NULL.
addIterator: inserts an element after the node currently pointed to by the iterator
advanceIterator: moves the iterator up by one node
reverseIterator: moves the iterator down by one node

Accessors:

getFirst: returns the first element
getLast:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length of the list
getIterator: returns the element currently pointed at by the iterator
offEnd: returns whether the iterator is off the end of the list, i.e. is NULL
equals: overrides the equals method for object to compares this list to another list to see if they contain the same data in the same order.

Additional Operations:

toString: overrides the toString method for object to print the contents of the linked list to the screen separated by a blank space
printNumberedList: prints the contents of the linked list to the screen in the format #. <element> followed by a newline
  • Note that, as you write each method, you must also write its Javadoc comment, including using the @precondition tag, @postcondition tag and @throws tag where necessary.
  • Hint: You can use the above descriptions as a starting point for your Javadoc comments.
  • You should also test your methods inside of ListTest.java and create unit tests (or update the unit tests where necessary) for the following methods:
    • addFirst
    • addLast
    • getFirst
    • getLast
    • removeFirst
    • removeLast
    • isEmpty
    • getLength
    • addIterator
    • removeIterator
    • getIterator

Extra Credit: Scheduler App (10 pts)
  • Create a class called Scheduler.java inside of your List project folder
  • This program should store a user schedule inside of a linked list - with one event stored per node
  • It should call the List iterator methods to move events around in the schedule
  • There are 3 menu options offered to the user:
    • A: Add an event
    • R: Remove and event
    • X: Exit
  • The Add an event option:
    • Should prompt for a new event and then store the event at the front of the List
    • Next, it should prompt the user whether or not to move the event up in the schedule (later in the schedule) and how far up, as shown in the example output below
    • The above functionality will require you to call pointIterator(), advanceIterator() and addIterator()
    • It should also do some error checking if the user wants to move the event past the end of the List, and allow the user to keep entering values until giving a valid input. (See sample output below)
  • The remove an event option:
    • Prompts the user for the number of the event and removes it (call pointIterator(), advanceIterator() the specified number of times followed by removeIterator())
  • The exit option should print "Goodbye" and end the application
  • The program should also check whether the user has entered an invalid menu option (A value other than A, R or X or their lower case equivalents) and print an error message as shown below.
  • Scheduler.java should give identical output (including formatting and line spacing) to the output below (given the same user input):

Example Output:

Welcome to the Scheduler App!

You have no upcoming events!

Select from the following options:
A: Add an event
R: Remove an event
X: Exit

Enter your choice: A

Please enter an event: Walk dog

Your Current Schedule:

1. Walk dog

Select from the following options:
A: Add an event
R: Remove an event
X: Exit

Enter your choice: A

Please enter an event: Make dinner

You just added the following event to your schedule: Make dinner

Your Current Schedule:

1. Make dinner
2. Walk dog

Would you like to move this event up in your schedule (Y/N): Y
Enter the number of places: 1

Your Current Schedule:

1. Walk dog
2. Make dinner

Select from the following options:
A: Add an event
R: Remove an event
X: Exit

Enter your choice: A

Please enter an event: Grade labs

You just added the following event to your schedule: Grade labs

Your Current Schedule:

1. Grade labs
2. Walk dog
3. Make dinner

Would you like to move this event up in your schedule (Y/N): Y
Enter the number of places: 10
Sorry that input is invalid!

Enter the number of places: 18
Sorry that input is invalid!

Enter the number of places: 2

Your Current Schedule:

1. Walk dog
2. Make dinner
3. Grade labs

Select from the following options:
A: Add an event
R: Remove an event
X: Exit

Enter your choice: R
Enter the number of the event to remove: 2

Removing: Make dinner

Your Current Schedule:

1. Walk dog
2. Grade labs

Select from the following options:
A: Add an event
R: Remove an event
X: Exit

Enter your choice: X

Goodbye!


Specifications for Submission
  • Please submit the following files to Canvas
  1. List.java (a complete and fully commented generic, doubly-linked List class, including specified methods)
  2. ListTest.java (test file with at least 2 method calls to each method written)
  3. Schedule.java (source file with all of the logic to create the Scheduler App shown above)
  4. Unit Test classes for the required methods as specified above
  • Important: You must name your files exactly as described above
  • Also, your code must compile using Eclipse for Java.
  • Optionally: Your extra credit pair programming contract
  • Please do not submit as a Zip file


How You Will Be Graded:

  • No credit if your List.java file contains any additional methods other than those specified in the directions or if the inner Node class has been altered in any way from what was given in this Lab.
  • Make sure that you test your list thoroughly inside of ListTest.cpp!
  • No credit if your List doesn't compile or run using the Eclipse IDE as specified above
  • No credit if your program doesn't compile. Make sure to comment out the parts that aren't working (if any) before you submit.
  • Please include a block comment with your name on the top of EACH file like so:

/**

* FirstName LastName

* CIS 22C, Lab 2

*/

  • 72 points of the credit will be for submitting a complete and functional generic, doubly-linked list (4 points per correct method)
  • 28 points for adequate testing (2 points per unit test class and 8 points for a complete ListTest.java class)
  • 10 points extra credit for a complete and functional Schedule.java that works as shown in the sample output.
  • 5 points extra credit for pair programming