ENGR 131 HW 9

From Johnwiki

ENGR 131 Homework #9: Lists

Due at beginning of next recitation. Turn in the following:

• Typed sheet with answers to the questions and survey below.
• A hard copy of your final program.
• An email to me with your program files (.java) attached.

Contents 1 Introduction 2 Instructions 2.1 Sample Execution 3 Code 3.1 ListNode 3.2 List 3.3 Sample Usage 4 Hints 5 Questions 6 Survey

Introduction

Lists are like arrays, except they can grow to hold any number of objects, whereas an array can hold up to a fixed number of objects. Lists work by creating "list nodes" for each object in the list. A node stores two things: the object at that position in the list and the "next" node in the list.

Consider the list (3, 7, 2). To store this list, we need to create three nodes: A, B, and C. The following psuedocode describes how the nodes create a list:

 A.value = 3
 B.value = 7
 C.value = 2
 
 A.next = B
 B.next = C
 C.next = null

Notice how A points to B (by A.next) and B points to C (by B.next). This allows you to read the entire list to the end if you are given the starting node.

If you wanted to add a new entry to the list, now, all you have to do is create a new node and add it to the end of the list. Say we want to add 8 with the node D:

 D.value = 8
 
 C.next = D
 D.next = null

All we did to add 8 to the list was to change C to point to D. The list is now (3, 7, 2, 8). If you repeat this process, your list can keep growing until you run out of memory!

Instructions

Your program will let the user add, remove, test, and print the values in a list. For simplicity, your list only needs to store strings. When the program starts, the list should be empty. The user will give commands of the form "A x", "R x", "C x", or "P", where x is some string. "A" means x should be added, "R" means x should be removed, "C" means the list should be tested for x, and "P" means the values of the list should be printed. After each command, the size of the list should be reported.

You don't need to worry about the order of the values in the list or the presence of duplicate values.

Sample Execution

 P
 ()
 List size: 0
 
 A Milk
 List size: 1
 
 A Eggs
 List size: 2
 
 C Swiss Cheese
 Sorry, the list does not contain Swiss Cheese.
 List size: 2
 
 R Eggs
 List size: 1
 
 A Swiss Cheese
 List size: 2
 
 P
 (Milk, Swiss Cheese)
 List size: 2
 
 R Eggs
 You can't remove something that isn't in the list!
 List size: 2
 
 C Milk
 Yes, the list does contain Milk.
 List size: 2

Code

To use this code, you will have to write the missing methods for the List class.

ListNode

The list node defines the structure of the list, but it itself is not capable of doing operations on the list such as adding and deleting.

class ListNode {
	
	public String value ;
	public ListNode next ;
}

List

The list uses list nodes to carry out the user's operations, but it only needs to store the first node of the list.

class List {

  private ListNode first ;
  
  public List() {
    first = null ; // The list is initially empty.
  }
  
  public void add(String value) {
  	// Add this string to the list.
  }
  
  public void remove(String value) {
  	// Remove this string from the list.
  }
  
  public boolean contains(String value) {
  	// Return true if and only if this string is in the list.
  }
  
  public void print() {
  	// Print the strings in the list in the form (s1, s2, s3, ...).
  }
  
  public int size() {
  	// Return the number of strings in the list.
  }
}

Sample Usage

This code shows how to use the List class.

 List list = new List() ;
 list.add("3") ;
 list.add("7") ;
 list.add("2") ;
 list.print() ; // Prints 3, 7, 2.
 list.add("8") ;
 list.remove("7") ;
 list.print() ; // Prints 3, 2, 8.
 if(list.contains("3"))
   System.out.println("The list contains 3.") ;

Hints

• Don't forget to use the equals() method to compare strings!

• If you can't figure out how to write the list methods, here is one way to do the "add" method. The other methods are very similar to this one.

1. If the list is empty, create a new ListNode and store it as "first". Set the value of this node to the input value and return.
2. Otherwise, loop through the nodes with a while loop (use a temporary variable) until you find the first node that doesn't have a "next" node. This is the end of the list.
3. Create a new ListNode and point the node end of the list (from the last step) to the new node. Set the value of the new node to the input value and return.

Questions

No questions this time. Just print out an example of your program's input/output that demonstrates everything it can do. This should include. but is not limited to:

1. Adding values.
2. Removing values that are and aren't in the list. The latter should cause an error report.
3. Testing if the list contains values that it does and doesn't contain.
4. Printing empty and non-empty lists.
5. Getting the size of empty and non-empty lists.

If you program does anything else cool, demonstrate it here!

Survey

Rate the difficulty for you on a scale of 1 to 10 (1 = Very easy for me, 10 = Very difficult for me).

Rate your understanding of the requirements on a scale of 1 to 10 (1 = Did not understand anything, 10 = Understood everything)