APS 105 -- Computer Fundamentals

Lab #8

Fall, 2000

You must submit this lab by 11:59 pm on Friday, November 17

1. Objective

In this lab, you are required to construct and manipulate a list ADT, which uses a linked list to hold integer numbers.

2. Creating a List ADT

In a file called List.java, write the description for two classes: an Node class and a List class. The Node class will contain an integer number and the next Node in a list. Neither of these classes should use Stdin or print anything.

The List class contains the list ADT operations. You must use use linked lists to implement the list ADT. Lists should be maintained so that the integers are placed in non-decreasing order (note: duplicate values are permitted). The List must contain (at least) the following methods:

• public List ()
  This is a constructor used when creating a new, empty list.

• public String toString ()
  This returns the numbers in this list, in order, as a string. There should be a single space between each number. If the list is empty, the method should return an empty string "".

• public void insert (int item)
  This inserts a new node containing item into a list. The item should be inserted so that the list is maintained in non-decreasing order.

• public void deleteAll (int item)
  This method deletes all occurrences of item from a list.

• public List copy ()
  This method creates a copy of a list and returns a reference to the copy. It leaves the original list unchanged. This should be a completely independent copy, so any changes to the original would not affect the copy (and vice versa).

• public void mergeFrom (List other)
  This method removes all of the items from the other list and inserts them into this list in the proper order. You should be careful to make this method as efficient as you can. At the end of this method, the other list will be empty. See FAQ question below.

• public void reverse ()
  This method should reverse the order of the items in the current List object. This will cause the list to be in non-increasing order. You can assume that reversing will be the last possible operation on a list, so you do not have to complicate your other methods (insert, delete, and mergeFrom).

In addition to these methods, the class may also contain any fields, methods, or inner classes that you feel are appropriate.

3. Using the List ADT

Write a main method (in a class called Lab8) that uses the List class to perform the following operations. You may write any additional methods you need to help you.

• Repeatedly prompt the user for integers $\geq 0$, continuing to request values until the user provides a value that is negative. Each non-negative value provided by the user should be inserted into a list in non-decreasing order.

• Once the user has provided the values for the list, print a blank line, then print the list on its own line (using the toString() method).

• The program should then make a new list whose contents are identical to the original list.

• The program should then prompt the user for a single value and it should delete all occurrences of this value from the copy of the original list. The program should then print a blank line, print the modified list, then print the original list (each list should appear on its own line).

• Repeatedly prompt the user for integers $\geq 0$, continuing to request values until the user provides a value that is negative. Each non-negative value provided by the user should be inserted into the modified list in non-decreasing order.

• Merge the two lists together. Print a blank line, then print the merged list on its own line.

• Finally, the program should reverse the order of the merged list. Print a blank line, then print the reversed list on its own line.

4. FAQ

1.

Typo correction.
mergeFrom() should have return type void.

2.

Deadline extension.
New deadline: Friday at 11:59pm.

3.

How do I do mergeFrom()? Must it be efficient in runtime, or can I call my insert() method?
Do not use your insert() method. You must use references and do pointer manipulation to manually move each Item from the other list to the original one. Do not create any new Items -- anything that does new Item() makes a new item.

5. What to Submit

Submit your Lab8.java and List.java files along with Stdin.java.

Use the command: submitaps105f 8 List.java Lab8.java Stdin.java