Lab 1: Singly-Linked List (120 pts)
Due Monday, September 30 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
    • See the De Anza CIS Tutorial on Eclipse for Mac and Windows


Pair Programming Required!

  • 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.
  • 50 point deduction for working alone.
  • Find a partner using Piazza! Contact me ASAP if you are having trouble finding a partner.

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


/**
 * Defines 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 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 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 on its own line
     * 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 method stub 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.

Part 2: 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 - method calls - 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 each on its own line.
  • 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
  • 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 on its own line
   * 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
        }
        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 to 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 updating first.
  • 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 variable of the new Node to point to the beginning of the list
    3. Set first to point to the new Node
  3. Increment the length of the list (this will happen in either case)


   /**
   * 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 links 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 to 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 Node
  3. If the List has more than one Node
    1. Advance the first reference variable to link to the second Node.
  • 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.java.
  • Your ListTest.java 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 empty List: " + 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 to point to the second-to-last Node
  • I have written part of removeLast below 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 empty list: " + 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 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 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?

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


Part 3: 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.
  • Note that these statements must test the method in question. Don't write tests for another method other than the one you are testing.
  • 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());
       
    }

}



Part 4: Using Your List (20 pts)


  • In this last part, you will write a small application that uses your List class (no credit if you do not use your List class to complete this portion of the assignment )
  • In the same project where you have your List.java file, create a new source code file named Uni.java.
  • Additionally, create a text file named words.txt (right-click on the project folder and select New->File and make sure your file ends up in the overall project folder, not under src).
  • Next, copy and paste the following contents into your text file:

philatelist
numismatist
vexillophile
sucrologist

  • Note that these are all words for types of collectors. For more fun collector words, check out this article from MentalFloss.
  • The purpose of this application will be to do the following:
  1. Read each word from the file
  2. Convert each char in the word to its Unicode value
  3. Store each individual Unicode value in a node of a linked list
  • In essence, you should create 4 lists, one for each word, with each list storing the Unicode values for that particular word.
  • Your program will then specify the following information (see sample output below for more information):
    • The list number (1-4)
    • The word itself
    • The length of the list (should correspond to the number of letters in the word)
    • Whether the list is empty
    • The first Unicode value stored in the list (at the first node)
    • The last Unicode value stored in the list (at the last node)
    • The complete contents of the list (Unicode values of all chars in the word)
  • Your program should also ensure that the user has entered a correct file name and should allow the user to try again when mistyping the file name. (Hint: Use try-catch!)
  • Your program should give identical output to the sample output below (given the same inputs) to receive full credit for this component of the assignment.
Sample Output:

Welcome!

Please enter a file name: abc.txt
Invalid file name!

Please enter a file name: word.txt
Invalid file name!

Please enter a file name: words.txt

List #1: philatelist
The length of the list: 11
The list is empty: false
The first value in the list: 112
The last value in the list: 116
The contents of the list: 112 104 105 108 97 116 101 108 105 115 116


List #2: numismatist
The length of the list: 11
The list is empty: false
The first value in the list: 110
The last value in the list: 116
The contents of the list: 110 117 109 105 115 109 97 116 105 115 116


List #3: vexillophile
The length of the list: 12
The list is empty: false
The first value in the list: 118
The last value in the list: 101
The contents of the list: 118 101 120 105 108 108 111 112 104 105 108 101


List #4: sucrologist
The length of the list: 11
The list is empty: false
The first value in the list: 115
The last value in the list: 116
The contents of the list: 115 117 99 114 111 108 111 103 105 115 116

Goodbye!


Specifications for Submission

  • Please submit the following files to Canvas by Monday at 11:59pm:
    • List.java (All methods implemented and all preconditions and postconditions noted in comments)
    • ListTest.java (Test class with at least 2 method calls for each method inside of the main to receive credit)
    • 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)
    • Uni.java (working identically to the sample output, and using the List.java class and its methods to complete the demonstrated tasks)
    • Important: You must name your files exactly as described above for full credit
  • -10 points for incorrect naming
  • No credit for altering the Node inner class in the List class or for adding any additional methods to the List class other than those provided in the starter code.
  • Please submit each file separately (no zip files or other compressed file type -5 pts).
  • Please remove all package statements before submitting (-5 pts).
  • 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 installed 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.
  • You will receive 20 points for a Uni.java that works identically to the output shown and meets specifications in the lab description above.
  • 50 point deduction for not pair programming and submitting 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!