Assignment 16
due Friday, November 30 at 9:20am on Canvas

Before You Begin:

  • To get us started thinking about how to write our own linked list class, let's watch the following video:
  • Video: Linked Lists in 10 Minutes

Assignment 16.1: Checking Off the List (10 pts)

  • Create a new Java file called List.java and one called ListTest.java
  • Copy and paste the below contents into List.java:
/**
 * List.java
 * @author
 * @author
 * CIS 36B
 */

public class List<E> {
    private class Node {
        private E data;
        private Node next;
       
        public Node(E data) {
            this.data = data;
            this.next = null;
        }
    }
   
    private Node head;
    private Node tail;
    private int length;
   
    /****CONSTRUCTOR****/
   
    /**
     * Instantiates a new List
     * with default values
     */
    public List() {
       
    }
   
    /****ACCESSORS****/
   
    /**
     * Returns the data stored at the head node
     * @return the first element
     * @throws IllegalStateException when List is empty
     */
    public E getHead() throws IllegalStateException{
       
    }
   
    /**
     * Returns the value stored at the tail
     * @return the last element
     * @throws IllegalStateException when List is empty
     */
    public E getTail() throws IllegalStateException{
       
    }
   
    /**
     * 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;
    }
    
    /**
     * 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 "";
    }
   
    /****MUTATORS****/
   
    /**
     * Inserts a new element at the head
     * @param data the data to insert at the
     * head of the list
     */
    public void insertHead(E data) {
   
    }
   
    /**
     * Inserts a new element at the tail
     * @param data the data to insert at the
     * tail of the list
     */
    public void insertTail(E data) {
        
    }
   
    /**
    * Removes the element at the head of the List
    * @throws IllegalStateException
    * when the List is empty
    */
    public void removeHead() throws IllegalStateException{
        
    }
   
    /**
     * Removes the element at the tail of the List
     * @throws IllegalStateException
     * when the List is empty
     */
    public void removeTail() throws IllegalStateException{
        
    }
   
}
  • Copy and paste in the code for the constructor, insertHead and getHead.
  • Then, using those methods as a model, write insertTail and getTail.
  • For insertTail, my hint is to draw a picture. Which reference variables will need to be updated?
  • Next, copy and paste the below code into ListTest.java
/**
 * ListTest.java
 * @author
 * CIS 36B, Assignment 16.1
 */
public class ListTest {
    public static void main(String[] args) {
        List<String> l = new List<String>();
        l.insertHead("A");
        System.out.println("A at head: " + l.getHead());
        System.out.println("A at tail: " + l.getTail() + "\n");
        l.insertHead("B");
        System.out.println("B at head: " + l.getHead());
        System.out.println("A at tail: " + l.getTail() + "\n");
        l.insertHead("C");
        System.out.println("C at head: " + l.getHead());
        System.out.println("A at tail: " + l.getTail() + "\n");
        l.insertTail("D");
        System.out.println("C at head: " + l.getHead());
        System.out.println("D at tail: " + l.getTail() + "\n");
        l.insertTail("E");
        System.out.println("C at head: " + l.getHead());
        System.out.println("E at tail: " + l.getTail() + "\n");
       
    }
}
  • Compile and run your code to ensure you get the correct output.
  • Note that you only need to write 5 methods for this assignment:
    • Default constructor
    • insertHead
    • insertTail
    • getHead
    • getTail
  • We will look at the other methods next class.
  • When you are finished, please submit List.java to Canvas.