CS210 ALGORITHMS & DATA STRUCTURES I

LABORATORY 4

21/10/05

Mr. T. Lysaght

LINKED LISTS AND INTERFACES

The purpose of this Laboratory session is the implementation of the LINKED LIST data structure and INTERRFACES.

  1. Study the code for the Mesurable Interface in the CS210 folder on the public (J:/CS210/interfaces) drive.  Compile and run the code for the DataSetTester class.  Create a new class Country which has instance variables Name and Population.  The Country class should implement the Mesurable Interface, similarly to Coin and BankAccount, by implementing its own getMeasure() method to return the population.  Alter the DataSetTester program to include a DataSet of countries and to return the maximum population of a number of countries.

 

  1. Study the code for Linked Lists in the CS210 folder on the public (J:/CS210/LinkedLists  (not including the code from the uselist folder) drive.  Compile all files and run the ListTester.java file.  Study the output of the program.

 

  1. Add a method public int size() to the implementation of the LinkedList.java class that computes the number of elements in the list, by following links and counting the elements until the end of the list is reached.

 

  1. Add a currentSize field to the LinkedList.java class.  Modify the add and remove methods of both the LinkedList and ListIterator classes to update the currentSize field so that it always contains the correct size.  Modify the size() method, which returns the value of currentSize.

 

  1. The linked list class in the Java Library supports operations addLast and removeLast.  To carry out these operations efficiently, the LinkedList class has an added reference last (similar to first) to the last node in the list.  Draw a ‘before/after’ diagram of the changes of the links in a linked list under the addLast and removeLast methods.  Alter the LinkedList class to include addLast and removeLast methods.

 

  1.   The linked list class in the Java Library supports bi-directional iterators.  To go backwards efficiently, each Node has an added reference, precede, (similar to next) to the predecessor node in the linked list.  Draw a ‘before/after’ diagram of the changes of the links in a linked list under the addFirst and removeFirst methods that shows how the previous links need to be updated.