Lab 21 – Fun with linked lists

 

Background

The linked list is a useful tool for working with many kinds of data structures.  In this exercise you will create a linked list of sorted integers and will manipulate this list in various ways.

 

Submission

You will submit this assignment by printing the code that you produce and a copy of the results of one of your tests.  This lab is due on Tuesday before lecture.

 

TASK 1 – Create a linked list class

NOTE:  After doing #1 and #2, write a VERY SHORT program which shows how to put three items into a list and then delete the second one....  Understanding this will help you a lot with the rest of this lab.

You will be creating a linked list that will consist of nodes with the data portion being an integer and the link portion a link to the next node.

 

  1. Using the magazine rack example in the book, create a basic linked list program that will also have a private inner class representing the node.  As you work, test each method with a test driver.
  2. Your linked list class should have a constructor which sets the list pointer to null.
  3. This linked list should always stay in numeric order.  Therefore, you need to create an add method that when given an integer will insert its node into the correction location in the list. 
  4. You should add a delete method that when given a node value, will check to see if that node exists, then delete that node.  Delete should return a true or false depending on the result of the action. 
  5. To go along with the delete method, create a isHere method which returns true if a passed integer is in the list and a false otherwise.
  6. Collections should always contain an isEmpty method that returns true if there are no elements in the collection or false if there are.  Add an isEmpty method to your class.
  7. You should create a toString method that will print the contents of the list from beginning to end.

TASK 2:  Testing your Linked List

 

  1. Create a test driver (you may do this in your own test driver or make a new one).
  2. Create a linked list.
  3. Using the isHere method, test to see if 0 is in the list.
  4. Now add values to the list.  Add to it 10 random integers in the range of -50 to +50.  After each addition, print the elements in the linked list.
  5. Create a loop that will generate random numbers and test to see if they are in the list.  Print the number and the result of the test.
  6. End the loop when you find a number in the list.  Delete the node corresponding to this value. After each deletion, print the elements in the linked list.
  7.  
  8. Print the list again to see that the node was properly deleted.

 

Deliverable:  Disk with code and a printout of your program.  Due Wednesday BY the start of lab...