Skip to main content
Lesson 31 - Linked-List Algorithms
ZIPPDF (letter)
Lesson MenuPrevious
  
L.A.31.1 - OrderedList page 7 of 7

Background:

This lab will use a text file, "file20.txt", which is similar to the one used in the binary search lab in Lesson 28. The file has been saved in random order by id number. Your program must build an ordered linked list based on the id field. The ordered list should be implemented as a SinglyLinkedList of type ListNode.


Assignment:

  1. Here are some of the specifications for the methods to be added to the SinglyLinkedList class:

    1. You are to write a method insert that builds the linked list in order based on the id value. You are to write a method insert that builds the linked list in order based on the id value.

    2. A find method will check the list for a specific id value, returning a reference to such a node if the value exists in the list. If the value is not found, the method should return a null value.

    3. A remove method will remove unwanted data from the linked list

    4. Write a clear method that clears the entire list.

    5. Write a size method that returns the number of nodes in the list. Avoid copying this code from the last lesson and write it from scratch.

    6. Reading the data file is an identical process to that used in Store.java in Lesson 27.

    7. Printing the list involves the same code as used in the previous lesson on linked lists.

    8. Code a recursive printBackward method that prints out the linked list contents in reverse order.

  2. If your instructor chooses, you will be provided with a program shell consisting of a main menu, testing methods, and stubbed methods. Here are some of the specifications of this program shell.

    1. A method addLast is provided which builds the list just as in lab L.A.31.1, List1. The list will be built in the same order as it exists in the data file. The routine that reads the data from the text file has been separated from the method to insert the information into the linked list. See the code in the program shell.

    2. The find method returns a null value.

    3. The remove method returns a null value.

    4. The clear method is stubbed out as a print statement.

    5. The printBackwards method is stubbed out as a print statement.

    6. The size method returns 0.

    7. Methods to read the data file and print the list are provided.


Instructions:

  1. Modify and write code as necessary to satisfy the above specifications.

  2. Print out the entire source code.

  3. Include a printed run output of the following:

    1. The entire list printed in ascending order. Include a call of the size method and print the number of nodes.

    2. Print the list backward using the recursive printBackward method. Do not worry about printing a line number in this algorithm.

    3. The id's you searched for and their corresponding inventory amounts. Your instructor will specify which id values to search for.

    4. Delete id values as specified by your instructor. Print the abbreviated list after values have been deleted and include a call to size.

    5. Clear the entire list of all nodes. Call the size method one last time.


Lesson MenuPrevious
Contact
 ©ICT 2003, All Rights Reserved.