Lab 1: Singly-Linked List (100 pts)
Due Monday, October 1 at 11:59pm on Canvas

Before you begin!

  • Install Eclipse on your home computer (if needed)
    • You are required to use Eclipse in this class (Yes, really!).
    • You can use the Eclipse installed on lab computers in the ATC for assignments in this class or install it at home.
    • See my tutorial for help installing and creating a new project, and for a trouble shooting guide


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.

Project Set Up & Pre and Post Conditions
  • Create a new Java project in Eclipse named List (Notice the capitalization.
  • Right click on your project and add a new class named List.java (again notice the capitalization).
  • Please refer to the tutorial if you encounter any problems.
  • Copy and paste the following code into List.java file:


/**
 * Defines the a singly-linked list class
 * @author
 * @author
 */

import java.util.NoSuchElementException;

public class List {
    private class Node {
        private int data;
        private Node next;
       
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
   
    private int length;
    private Node first;
    private Node last;
   
    /****CONSTRUCTOR****/
   
    /**
     * Instantiates a new List with default values
     * @postcondition
     */
    public List() {
 
    }
   
    /****ACCESSORS****/
   
    /**
     * Returns the value stored in the first node
     * @precondition
     * @return the integer value stored at node first
     * @throws NoSuchElementException when precondition is violated
     */
    public int getFirst()
throws NoSuchElementException{
        return 0;
    }
   
    /**
     * Returns the value stored in the last node
     * @precondition
     * @return the integer value stored in the node last
     * @throws NoSuchElementException when precondition is violated
     */
    public int getLast() throws
NoSuchElementException{
        return 0;
    }
   
    /**
     * Returns the current length of the list
     * @return the length of the list from 0 to n
     */
    public int getLength() {
        return -1;
    }
   
    /**
     * Returns whether the list is currently empty
     * @return whether the list is empty
     */
    public boolean isEmpty() {
        return false;
    }
   
    /****MUTATORS****/
   
    /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition
     */
    public void addFirst(int data) {
        return;
    }
   
    /**
     * Creates a new last element
     * @param data the data to insert at the
     * end of the list
     * @postcondition
     */
    public void addLast(int data) {
        return;
    }
   
    /**
    * removes the element at the front of the list
    * @precondition
    * @postcondition
    * @throws
NoSuchElementException when precondition is violated
    */
    public void removeFirst() throws
NoSuchElementException{
        return;
    }
   
    /**
     * removes the element at the end of the list
     * @precondition
     * @postcondition
     * @throws NoSuchElementException when precondition is violated
     */
    public void removeLast()
throws NoSuchElementException{
        return;
    }
   
    /****ADDITIONAL OPERATIONS****/
   
    /**
     * List with each value separated by a blank space
     * At the end of the List a new line
     * @return the List as a String for display
     */
    @Override public String toString() {
       return "";
    }
   

}


  • Notice that each method is only a stub.
  • Also notice that the pre and postconditions in the comments are left blank.
  • Update the comments for each prototype by filling in the pre and postconditions.
    • It is your job to fill in the pre and postconditions for each method where indicated only.
    • Remember that preconditions indicate what conditions must be met BEFORE the user calls the method. The method will not work properly unless the preconditions are met.
    • Postconditions indicate what will be the result of the method call. In other words, what conditions will exist after the method is called.
    • See class notes from this week and also watch the lesson videos.

Method Implementation
  • For this lab, you should only write the methods defined in the starter code above. Please do not add any additional methods or you will lose points on this lab.
  • You will also lose points if you do not implement ALL the methods from the starter code.
  • Finally, each method must be tested thoroughly (3 tests in total for each method), using your own ListTest.java file and also JUnit (as described below).
  • When you scroll down this lab, you will see that I have helpful suggestions about how to write each method, as well as an example JUnit test for some of the methods.
Testing Your List Using ListTest.java
  • Create a second class inside the List project called ListTest.java (note the capitalization).
  • Add a main method to this class.
  • You will be using this class like scratch paper to test your List as you go along.
  • After you write each method, immediately call the method in ListTest.java, and then compile and run your code.
  • Did you get the expected output?
  • Take a moment now to create ListTest.java so it is ready when you write your methods

Constructor
  • For the default constructor, the goal is simply to initialize the fields inside the List class with a starting value - in this case default values, as the constructor takes no parameters.
  • We have 3 fields inside our List class:
    • Node first
    • Node last
    • int length
  • What are the appropriate default values for each of these fields?

    /**
     * Instantiates a new List with default values
     * @postcondition <--fill in here
     */
    public List() {
        first = null;
        last = //you fill in here
        length = //you fill in here
    }
  • Once you have written this method, please immediately test it inside of ListTest.java
  • Compile and run your code to make sure there are no errors
  • After you are finished, your ListTest.java should look like this:
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List L = new List();
       
    }

}


Additional List Operations - toString()

  • Any class we write will inherit from the Object class, which has basic methods such as toString() that you can override.
    • For a refresher on this information, see the tutorial here.
  • The toString() method is VERY IMPORTANT and should be one of the very first that you write.
  • Why?
    • You should be testing your code as you go along, and if you cannot print out the contents of the list, you will be unable to determine whether your methods are working properly.
  • Additionally, toString() determines how you are going to display the List information to the user.
    • For example, are you going to display it with [ ] and a , separating each piece of data, like so: [1,2,3,4]?
    • Are you going to display each piece of data on its own line or simply separated by a blank space?
  • For the purposes of this Lab, we will simply have the data items displayed on a single line, each separated by a blank space.
  • The idea behind the toString() method is straightforward:
  1. Create an empty String which will ultimately store the List as a String
  2. Create a temporary iterator to point to the first node
  3. Using a loop, concatenate the data for the current node
  4. Advance the temporary iterator
  5. Stop the loop when the iterator has gone off the end of the List
  6. Return the resulting String, with a new line appended to the end
  • For this lab, fill in the 2 missing lines of code below to complete the toString method.
  • Note: Please do not print any special messages when the List is empty
     /**
   * List with each value separated by a blank space
   * At the end of the List a new line
   * @return the List as a String for display
   */
    @Override public String toString() {
        String result = "";
        Node temp = first;
        while(temp != null) {
            result += fill in here
            //fill in here
        }
        result += "\n";
        return result;
    }
  • Now, write a test for toString() by displaying the empty List we just created. Note that toString should print nothing in this case.
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List L = new List();
        System.out.println("Should print nothing (an empty list): " + L);      
    }

}

Mutator: addFirst

  • Now let's write the addFirst method so we can start adding data to our list.
  • Remember that addFirst inserts a new Node IN FRONT OF the first node in the list each time it is called, effectively creating a new front of the list.
  • Therefore, if I were to call addFirst(6); and then call addFirst(4); 4 will be the data at the start of the list after those two calls.
  • We need to consider two cases here:
  1. The list is empty (edge case)
  2. The list has one or more Nodes (general case)
  • Why do I need to treat the empty List differently?
  • Remember: when writing your List procedures, it is very important to take into account the "edge" cases, such as an empty list.
  • In the case the List is empty, we will have to write some additional code to handle this situation.
    • We need to make a new Node and then ensure that both the first and last Nodes point to this new Node.
    • After all, if there is just a single Node in the list, this Node is both first and last Node of the List.
  • However, if there is already one or more Nodes in the List, all we need to worry about is adjusting the first pointer.
  • The pseudocode is as follows:
  1. If the list is empty, <--edge case
    1. Create a new Node 
    2. Set first and last to point to this Node.
  2. Otherwise: <--general case
    1. Create a new Node
    2. Set the next pointer of the new Node to point to the beginning of the list
    3. Set the first pointer to point to the new Node
  3. Increment the length of the list (this will happen in either case)

Depiction of addFirst. Notice how addFirst requires updating the pointer to the first node to point to the new node and the new node to point to the former first node of the list. The red arrows and lightening bolts indicate the updated pointers after calling the method.


   /**
   * Creates a new first element
   * @param data the data to insert at the
   * front of the list
   * @postcondition
   */
    public void addFirst(int data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first = N;
        }
        length++;
    }
  • Now, test your method.
  • Make sure to test the edge case : insertion when the List is empty
  • Also test the general case: insertion when the List has one or more elements in it
  • When you are finished, your ListTest.java should look like this:
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List L = new List();
        System.out.println("Should print nothing (an empty list): " + L);
       
        System.out.println("**Testing addFirst**");
        L.addFirst(2); //Testing Edge case: length == 0
        System.out.println("Should print 2: " + L);
        L.addFirst(1); //Testing General case: length >= 1
        System.out.println("Should print 1 2: " + L);

       
    }

}


Mutator: addLast

  • Write the addLast method.
  • Hint: it should be similar to addFirst, but not identical.
  • Hint 2: Don't simply update some of the names, but think about what is happening, using the diagram below to help yourself.
  • Which pointers will need to be updated?
  • You might try re-drawing the diagram on a sheet of paper and then manually updating the necessary arrows.
  • When you are finished, test your method inside of ListTest.java using the model provided in the section above.
  • Make sure you test both cases - edge case and general case


Mutator: removeFirst

  • Now let's write the removeFirst method so we can also remove data from the list.
  • Remember that removeFirst removes the data at the front of the list.
  • After a call to removeFirst, the second node in the list will have become the first.
  • We will temporarily handle the precondition using a print statement, until we cover assertions next lecture
  • We need to consider three cases here:
  1. The List is empty <-- nothing to remove (precondition)
  2. The List has only one Node (edge case)
  3. The List has more than one Node (general case)
  • Reflection: Why do I need to write different code for the case where the List has only one Node?
  • The pseudocode is as follows:
  1. If the List is empty,
    1. throws a NoSuchElementException
  2. If the List has one node
    1. Return the list to its empty state, where first and last are null and the length is 0
    2. Automatic garbage collection will remove the deleted Node
  3. If the List has more than one Node
    1. Create a temp Node to temporarily store a pointer the start node
    2. Advance the first pointer to point to the second node in the list (i.e. first.next)
    3. Call delete on the temp node to deallocate its memory
    4. decrement the length of the list
  • The below image depicts the third case of removeFirst, where there are multiple Nodes in the list.

  • Below is the code for removeFirst:
     /**
     * removes the element at the front of the list
     * @precondition <--fill in here
     * @postcondition <-- fill in here
     * @throws
NoSuchElementException when precondition is violated
     */
    public void removeFirst() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("removeFirst(): Cannot remove from an empty List!");
        } else if (length == 1) {
            first = last = null;
        } else {
            first = first.next;
        }
        length--;

       }

  • Now, make sure you test all three cases (if, else if, and else) in ListTest.cpp.
  • Your ListTest.cpp should now look something like this:
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List L = new List();
        System.out.println("Should print nothing (an empty list): " + L);
        
        System.out.println("**Testing addFirst**");
        L.addFirst(2);
        System.out.println("Should print 2: " + L);
        L.addFirst(1);
        System.out.println("Should print 1 2: " + L);
        
        //Code to test addLast goes here!
        
        System.out.println("**Testing removeFirst**");
        L.removeFirst(); //Testing General case: length >1
        System.out.println("Should print 2: " + L);
        L.removeFirst(); //Testing Edge case: length == 1
        System.out.println("Should print an new Line: " + L);
        System.out.println("Should an error message for an empty List: ");
        try { //place in a try-catch so program does not end when exception thrown
            L.removeFirst(); //Testing Precondition: length == 0
        } catch(NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
 

    }

}

Mutator: removeLast

  • Add the below removeLast method to your List class.
  • RemoveLast is similar to removeFirst, but also trickier.
  • There is no easy way to access the second to last node in the list. Do you see why?
    • You need a loop to advance a temp Node up to the second to last Node.
    • Then, you can remove the last Node and reset the last pointer to point to the second-to-last Node
  • I have written part of removeLastbelow to help you get started.
   /**
   * removes the element at the end of the list
   * @precondition <--fill in here
   * @postcondition <--fill in here
   * @throws NoSuchElementException when precondition is violated
   */
    public void removeLast throws
NoSuchElementException {
        //add your if statement here
        else if (length == 1) {
            //add a line of code here
        } else {
            Node temp = first;
            while (temp.next != last) {
                temp = temp.next;
            }
            last = temp;
            last.next = null;
        }
        length--;
    }

Writing the List Access Methods

  • Access methods provide information about the current state of the data structure.
  • Access methods typically have preconditions that we must account for as part of the method. We will discuss this concept in more detail during the next class.
  • For this lab, I recommend placing any method call that violates a precondition (and thus throws an exception) inside of a try catch block to avoid the program terminating upon encountering an error. Please see the example above.


Accessor: isEmpty

  • Writing access methods is generally pretty straightforward, involving just a few lines of code at most.
  • For example, let's look at the isEmpty() method, whose purpose is to return whether the list is empty using a boolean.
  • This method doesn't require a precondition. It is thus possible to write this method in a single line of code.
  • Here is the pseudocode:
  1. Return the whether the length is 0

/**
* Returns whether the list is currently empty
* @return whether the list is empty
*/
 public boolean isEmpty() {
     return length == 0;
 }

  • Now test this method.
  • You should test it twice as there are two possible cases.
    • What are they?

/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List L = new List();
        System.out.println("Should print nothing (an empty list): " + L);
       
        System.out.println("**Testing addFirst**");
        L.addFirst(2);
        System.out.println("Should print 2: " + L);
        L.addFirst(1);
        System.out.println("Should print 1 2: " + L);
       
        //Code to test addLast goes here!
       
        System.out.println("**Testing removeFirst**");
        L.removeFirst();
        System.out.println("Should print 2: " + L);
        L.removeFirst();
        System.out.println("Should print an new Line: " + L);
        System.out.println("Should an error message for an empty List: ");
        try {
            L.removeFirst();
        } catch(NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
        //Tests for removeLast go here!
       
        System.out.println("**Testing isEmpty**");
        List L2 = new List();
        System.out.println("Should print true: " + L2.isEmpty());
        //add another test for isEmpty() here!

       
    }

}

Accessor: getLength()

  • Given the code for empty above, now try to write the getLength method.
  • This method can also be written in just one line of code.
  • Its purpose is to return the current length of the List.
  • Now test this method. Try writing a test for when the List is empty and when it is not.
  • Note that when the List is empty getLength should simply return 0.


Accessor: getFirst()

  • The purpose of the getFirst access method is to return the data that is currently stored at the start of the List.
  • Copy and paste the below code into your List class:
      /**
     * Returns the value stored in the first node
     * @precondition
     * @return the integer value stored at node first
     * @throws
NoSuchElementException when the precondition is violated
     */
    public int getFirst() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("getFirst: List is Empty. No data to access!");
        }
        return first.data;
    }

  • Now test this method. What possible cases might there be?
  • What will happen if the precondition is violated?
  • Make sure to comment out your test for the precondition after you have verified the exception gets thrown.

Accessor: getLast()
  • Given the example above, it is your job to write the getLast method and test it properly.


Testing Your List Using JUnit
  • Watch the tutorial video on using JUnit
  • Note that you will be required to write a JUnit class for each of the following methods:
    • addFirst
    • addLast
    • getFirst
    • getLast
    • removeFirst
    • removeLast
    • isEmpty
    • getLength
  • You should write these JUnit tests AFTER you finish writing your List class. (Use ListTest.java to test your code as you go along.)
  • Name your JUnit class NameOfMethodTest.java.
    • For example: GetLengthTest.java or GetFirstTest.java or RemoveLastTest.java
  • How to Set Up a JUnit Class:
    • Right-click on the project folder for List
    • Select New
    • Select JUnit Test Case
    • Name your class according to the rules defined above.
  • Inside of each class write 3 assertEquals() statements in the test() method.
  • Then, run your tests. Make sure each test passes before moving to the next JUnit class.
  • Only once the JUnit tests pass for each method should you submit your assignment.
  • Below are some examples of good JUnit Classes for your List Methods:
JUnit Tests for addLast():
import static org.junit.Assert.*;

import org.junit.Test;

public class AddLastTest {

    @Test
    public void test() {
        List L = new List();
        L.addLast(1);
        assertEquals(1, L.getLength());
        L.addLast(2);
        assertEquals(2, L.getLast());
        L.addLast(3);
        assertEquals(3, L.getLast());
    }

}

JUnit Tests for getLength():
import static org.junit.Assert.*;

import org.junit.Test;

public class GetLengthTest {

    @Test
    public void test() {
        List L = new List();
        assertEquals(0, L.getLength());
        L.addLast(3);
        assertEquals(1, L.getLength());
        L.addFirst(2);
        assertEquals(2, L.getLength());
       
    }

}


Specifications for Submission
  • Please submit the following files to Canvas by Monday at midnight:
  1. List.java (All methods implemented and all preconditions and postconditions noted in comments)
  2. ListTest.java (Test class with at least 2 method calls for each method inside of the main to receive credit)
  3. 8 JUnit Test Classes -- one for each of the methods described above. (Note that these must be named properly and also contain 3 assertEquals() calls for each JUnit class to receive credit)
  • Important: You must name your files exactly as described above for full credit
    • -10 points for incorrect naming
  • Please do not submit any zip or compressed files!
  • Also, your code must compile using the Eclipse IDE. Make sure to compile and run your files using Eclipse before submitting to make sure they compile and run properly. Note that Eclipse is located on the Lab computers in ATC 203.
  • Note that you can find tutorials for installing Eclipse on Windows and Mac and for creating new Java projects on my tutorials page here


How You Will Be Graded:
  • You will receive 10 points for providing a ListTest.java test file that fully tests each method with 2 calls per method minimum.
    • Also: You must copy and paste the results of running your tests into the comments at the bottom of this file
  • You will receive 24 points for the JUnit test files -- one point per assertEquals per class
  • You will receive 15 points for methods that are fully commented with both pre and post conditions filled in where indicated
  • You will receive 5 points for each correctly written method as specified for this lab. These methods must be a working part of a List class that is written in the List.java file.
  • 5 points extra credit for pair programming and submitting the pair programming worksheet. No extra credit if you do not submit the pair programming worksheet.
  • Stop! Did you read the comments for each method to make sure your method does exactly what the comments describe? Make sure before you submit!