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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.