Welcome to Lesson 20!


Learning Objectives
By the end of today's class, you should know...
  • How do you write the accessor methods getLength and is Empty for the List class? 
  • How do you write the remove methods to remove at the head and tail of a List?


The List Class Continued

Writing isEmpty()

  • The purpose of isEmpty() is to return whether the list is empty using a boolean value.
  • It is possible to write this method in a single line of code or using an if-else block.
  • Here is the pseudocode:
  1. Return the whether the length is 0
  • And, here is the starter code for this method:
    /**
     * Returns whether the list is currently empty
     * @return whether the list is empty
     */
    public boolean isEmpty() {
        return false; //update the method body
    }

Writing getLength()

  • The getLength() method can also be written in just one line of code.
  • Its purpose is to return the current length of the List.
  • Note that when the List is empty getLength should simply return 0.
  • Here is the starter code for this method:
    /**
     * Returns the current length of the list
     * @return the length of the list from 0 to n
     */
    public int getLength() {
        return -1; //update method body
    }


Writing removeHead() and removeTail()

  • The easiest place to remove a node from the list is from the start
  • To remove a node from the start, we want to move the head node so that it points to the second node on the list
  • We can do this with an assignment statement:
head = head.next;
  • After a call to removeHead, the second node in the list will have become the head.
  • We need to consider three cases for this method:
  1. The List is empty <-- throw an exception (nothing to remove)
  2. The List has only one Node <--- both head and tail go to null (edge case)
  3. The List has more than one Node <-- advance head to be the second node (general case)
  • The pseudocode is as follows:
  1. If the List is empty,
    1. throws an IllegalStateException
  2. If the List has one node
    1. Return the list to its empty state, where head and tail 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
  • The below image depicts the third case of removeHead, where there are multiple Nodes in the list.
removeHead method

Activity 20.1: A Completed List

  • Open up your List.java and ListTest.java from the last lesson
  • Write the getLength and isEmpty methods for the List class, using the starter code provided above.
  • Now, copy and paste the below code into ListTest.java and run your program to verify the new methods are working properly.
/**
 * ListTest.java
 * @author
 * @author
 * CIS 36B
 */
public class ListTest {
    public static void main(String[] args) {
        List<String> L = new List<String>();
        System.out.print("Should print a blank line: " + L);
        System.out.println("List is empty (true): " + L.isEmpty());
        System.out.println("Length of the List (0): " + L.getLength());
       
        try {
            L.getHead();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
        try {
            L.getTail();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
       
        L.insertHead("A");
        System.out.println("\nA 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");
       
        System.out.print("Should print C B A D E : " + L);
        System.out.println("List is empty (false): " + L.isEmpty());
        System.out.println("Length of the List (5): " + L.getLength());
       
    }
}
  • When you have finished testing isEmpty and getLength (and you are certain they are working properly), it is time to write removeHead and removeTail
  • Using the starter code provided below, write removeHead and removeTail.
  • Below is the code for removeHead. Fill in the missing parts of the method below:
     /**
    * Removes the element at the head of the List
    * @throws IllegalStateException
    * when the List is empty
    */
    public void removeHead() throws IllegalStateException{
        if (length == 0) {
            throw new IllegalStateException("removeHead(): Cannot remove "
                    + "from an empty List!");
        } else if (length == 1) {
            head = tail = //fill in here
        } else {
            //fill in here
        }
        length--;
    }

removeTail

  • Add the below removeTail method to your List class.
  • removeTail is similar to removeHead, 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 tail Node and reset the last reference to point to the second-to-last Node
  • I have written part of removeTail below. Please finish the method by filling in the missing lines of code where indicated.
   /**
     * Removes the element at the tail of the List
     * @throws IllegalStateException
     * when the List is empty
     */
    public void removeTail() throws IllegalStateException {
        //fill in if statement here!
        } else if (length == 1) {
            //fill in here!
        } else {
            Node temp = head;
            while (temp.next != tail) {
                temp = temp.next;
            }
            tail = temp;
            tail.next = null;
        }
        length--;
    }

ListTest.java
  • Copy and paste the below code into ListTest.java.
  • Run the tests and verify that you get the correct output (see sample output below)

/**
 * ListTest.java
 * @author
 * @author
 * CIS 36B
 */
public class ListTest {
    public static void main(String[] args) {
        List<String> L = new List<String>();
        System.out.print("Should print a blank line: " + L);
        System.out.println("List is empty (true): " + L.isEmpty());
        System.out.println("Length of the List (0): " + L.getLength());
        try {
            L.removeHead();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
        try {
            L.removeTail();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
       
        try {
            L.getHead();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
        try {
            L.getTail();
        } catch(IllegalStateException e) {
            System.out.println(e);
        }
       
        L.insertHead("A");
        System.out.println("\nA 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");
       
        System.out.print("Should print C B A D E : " + L);
        System.out.println("List is empty (false): " + L.isEmpty());
        System.out.println("Length of the List (5): " + L.getLength());
       
        L.removeHead();
        System.out.println("\nB at head: " + L.getHead());
        System.out.println("E at tail: " + L.getTail());
        System.out.println("Length of the List (4): " + L.getLength());
       
        L.removeHead();
        System.out.println("\nA at head: " + L.getHead());
        System.out.println("E at tail: " + L.getTail());
        System.out.println("Length of the List (3): " + L.getLength());
       
        L.removeTail();
        System.out.println("\nA at head: " + L.getHead());
        System.out.println("D at tail: " + L.getTail());
        System.out.println("Length of the List (2): " + L.getLength());
       
        L.removeTail();
        System.out.println("\nA at head: " + L.getHead());
        System.out.println("A at tail: " + L.getTail());
        System.out.println("Length of the List (1): " + L.getLength());
       
        L.removeHead();
        System.out.println("\nLength of the List (0): " + L.getLength());
        System.out.println("List is empty (true): " + L.isEmpty());
    }
}

  • When your List class is complete and you get the correct results for each test, submit your List.java to Canvas.

Sample Output (Your output must be *identical* to the output below):

Should print a blank line:
List is empty (true): true
Length of the List (0): 0
java.lang.IllegalStateException: removeHead(): Cannot remove from an empty List!
java.lang.IllegalStateException: removeTail(): Cannot remove from an empty List!
java.lang.IllegalStateException: getHead(): List is empty.
java.lang.IllegalStateException: getTail(): List is empty.

A at head: A
A at tail: A

B at head: B
A at tail: A

C at head: C
A at tail: A

C at head: C
D at tail: D

C at head: C
E at tail: E

Should print C B A D E : C B A D E
List is empty (false): false
Length of the List (5): 5

B at head: B
E at tail: E
Length of the List (4): 4

A at head: A
E at tail: E
Length of the List (3): 3

A at head: A
D at tail: D
Length of the List (2): 2

A at head: A
A at tail: A
Length of the List (1): 1

Length of the List (0): 0
List is empty (true): true


Upcoming Assignments
  • Lesson 20 Practice Exam Questions due Thursday at 11:59pm
  • Activity 20.1 due Thursday at 11:59pm
  • Peer Reviews of Lesson 18 -19 and 20 Practice Exam Questions due Saturday at 11:59pm
  • Quiz 7 due Friday at 11:59pm
  • Course project and presentation due by Friday at 11:59pm
  • Final Exam on Monday, June 22 at 9:15am

Good Luck Studying!