Week 3

Post date: Jan 19, 2019 5:52:39 AM

Chapter 3 Linked Lists:

Lists in java.util

Lab 3 – More on Linked Lists

Objectives:

Learn How to Implement Iterable and Iterator interfaces for Doubly Linked List

Learn How to Traverse Doubly Linked List outside its class (using the Iterator)

Iterable and Iterator interfaces:

Two related interfaces in the java.util package are Iterator and Iterable:

All java collections (ArrayList, LinkedList, etc.) implements the Iterable interface. This means they have a method : public Iterator<T> iterator()that returns an object implementing the Iterator interface, which can be used to iterate (or traverse) through the elements of the collection, either directly or using foreach loop. Example:

In our generic implementation of linked list, we need to implement these two interfaces for the following important reasons:

  1. The head and tail variables, which are used to traverse the list are private, thus can only be used to traverse the list in its class but not outside.

  2. Since the linked list is generic, operations that are type-specific can only be done in the application class after the type is specified. Example, finding the sum in a list of integers or finding the item with highest price in a list of Items, etc.

  3. The for-each loop [ for ( : ) ] can only be used on a data structure that implements the Iterable interface.

Examples:

1- Class DLL has been updated to implement the Iterable interface. Study it carefully to understand the implementation.

2- Class TestIntegerDLL example has been updated to include a method that returns the sum of the element in the list.

3- Class TestItemDLL has been updated to print all items whose price is greater than a specified amount.

Tasks:

1- Update TestIntegerDLL to include a method that uses Iterator (or for-each loop) to print all the odd numbers in the list. Test your method by adding an option in the main method.

2- Update the TestItemDLL to include a method:

public static double totalCost(String itemName, int quantity, DLL<Item> list)

That uses Iterator (or foreach loop) to locate a given item, then computes and returns the total cost, given the quantity purchased. Test your method by adding an option in the main method.

3- Update your TestStudentDLL of Lab#2 to include a method:

public static void printGoodStudents(DLL<Student> list)

that uses Iterator (or foreach loop) to print all students in the list whose GPA is greater than 2.0. Test your method by adding an option in the main method.

4- Write an inner class, DLLReverseIterator<T>, inside the DLL class, similar to DLLIterator<T> but which iterates the elements of the list in reverse order. Update the iterator() method to return an object of this class instead. Test your new Iterator class using any of the Test classes. Example, test your task 1 above with the new iterator.