AP Java Assignment 14:
Building an Ordered Linked List

Background

In this assignment we will write an application that reads some data from a text file, stores it in a linked list and then does various operations on the linked list. Much of the java code has already been written for you and can be downloaded from the website.

Instructions for downloading the files for this assignment:

  1. Right click on the following links ApJava14.java, file20.txt, EasyReader.java. For each one choose "Save Target As" and save each file to your My Documents folder
  2. Create a new project in RealJ using the files you've just downloaded:
    1. Choose Project | New Project
    2. Select "Empty Project" and name the main class "ApJava14"
    3. Choose Add Java Source file and add ApJava14.java and EasyReader.java
    4. Choose Window | ApJava14.jpr
    5. On the Main Java File pull down menu select ApJava14.java
    6. Choose Build and then Run Application. It should display the following:
      
Line 0 Key: 196 Inventory: 60
Line 1 Key: 18618 Inventory: 64
Line 2 Key: 2370 Inventory: 65
Line 3 Key: 18410 Inventory: 56
Line 4 Key: 18465 Inventory: 27
Line 5 Key: 19967 Inventory: 45
Line 6 Key: 17911 Inventory: 96
Line 7 Key: 184 Inventory: 14
Line 8 Key: 18871 Inventory: 69
Line 9 Key: 14088 Inventory: 92
Line 10 Key: 18061 Inventory: 3
Line 11 Key: 206 Inventory: 31
Line 12 Key: 13066 Inventory: 8
Line 13 Key: 12705 Inventory: 14
Line 14 Key: 15917 Inventory: 51
Line 15 Key: 15814 Inventory: 60
Line 16 Key: 15320 Inventory: 82
Line 17 Key: 8303 Inventory: 90
Line 18 Key: 7282 Inventory: 73
Line 19 Key: 12328 Inventory: 63
Exit code: 0
No Errors

Steps to completing this assignment

You will notice that in ApJava14.java there are two class definitions: List and ListNode. Your job is to complete the List definition. You will need to use the ListNode class. 

class List
{
        private ListNode head;
        /* Step 1
        Complete this contructor */
        public List()
        {
           
        }
       
        void startDisplay()
        {
           display(head);
        }
        /* Step 2
        complete the following method: */
        void display (ListNode node)
        {

        }
        /* Step 3
        Complete the following method 
        void insertInOrder(int nKey, int nInv)
        {
        } */
        void startPrintBackwards()
        {
           printBackwards(head);
        }
        /* Step 4
        complete the following method: */
        void printBackwards (ListNode node)
        {
           
        }
        
        /* Step 5
        complete the following method: 
        int countNodes ()
        {
           
        }*/

        /* Step 6: complete the following method 
        ListNode search(int nKeyToFind)
        {

        }*/
        
        /* Step 7: complete the following method 
        void clearList()
        {

        }*/
        
        /* Step 8: complete the following method 
        void removeNode(int nKeyToFind)
        {
           
        }*/

}

class ListNode
{
        private int myKey, myInv; 
        private ListNode myNext; 
        public ListNode (int nTempKey, int nTempInv, ListNode tempNext) 
        {
           myKey = nTempKey;
           myInv = nTempInv;
           myNext = tempNext;
        }
        public int getKey(){return myKey;}
        public int getInv(){return myInv;} 
        public ListNode getNext(){return myNext;}
        public void setNext(ListNode newNext){myNext = newNext;}

}
  1. Write a constructor for the List class that initializes the head of list to an empty list.
  2. Write a display method to display the Key and Inventory values in a list of ListNodes
  3. Write a method void insertInOrder(int nKey, int nInv) which builds the linked list in order based on the Key value. (Hint: Call display to show the list each time after you call insertInOrder to check to see that the method is running correctly.)
  4. Code a recursive printBackward method which prints out the linked list contents in reverse order.
  5. Write a method countNodes which returns the number of nodes in the list.
  6. Write a Search method that will check the list for a specific Key value, returning a handle to such a node if the value exists in the list. If the value is not found, the function should return null.
  7. Write function ClearList which clears the entire list.
  8. Write a removeNode method that will remove a single node from the linked list if it has the given Key. Delete Key values 196, 13066, 18871. Print the abbreviated list after values have been deleted
  • Submit your code with sample output to mrsimon@lycos.com.