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 ContinuedWriting 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:
- 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:
- The List is empty <-- throw an exception (nothing to remove)
- The List has only one Node <--- both head and tail go to null (edge case)
- The List has more than one Node <-- advance head to be the second node (general case)
- The pseudocode is as follows:
- If the List is empty,
- throws an IllegalStateException
- If the List has one node
- Return the list to its empty state, where head and tail are null and the length is 0
- Automatic garbage collection will remove the deleted Node
- 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.
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!
|
|