Linked Lists:
Inside View of the LinkedNodeCollection Class

In the Bad News Bearers Lab, you saw how to build up a linked list and traverse it, using the standard Java LinkedList class (a class in java.util that implements a doubly-linked list).  In this lab, you'll be focusing on implementation, using the simpler LinkedNodeCollection and DoublyLinkedNodeCollection classes.

Mini-Lab 1: Basic Observer Methods

Getting Started

• Download the ListNode class and the skeleton source file for the LinkedNodeCollection class.  Read the class, focusing on its instance variables and constructor, and on the ListNode class. 
   
• Implement the following methods in the LinkedNodeCollection class:  size, isEmpty, contains, and iterator.  Also implement the hasNext and next methods in the LinkedNodeCollectionIterator class.  Test your changes by writing a test driver (similar to the Bad News Bearers program) that creates a linked collection, tests whether it is empty, adds elements to it, tests again whether it is empty, asks it for its size, and so on.
   
• Consider implementing a DoublyLinkedNodeCollection class, in which each node has a reference to the previous node in the list as well as to the next one, and in which the collection maintains a reference to the last node in the list (the tail) as well as to the first node (the head).   Identify and draw diagrams for the "extreme examples" (or boundary cases) of a doubly linked collection, similar to the diagrams below for a singly linked collection.  How many "extreme examples" are there for a doubly linked collection?

• Develop a skeleton source file for the DoublyLinkedNodeCollection class.  Specify the class's instance variables, constructor, and the ListNode class.  Implement the size, isEmpty, contains, and iterator methods in DoublyLinkedNodeCollection and the hasNext and next methods in the nested DoublyLinkedNodeCollectionIterator class, just as you did for LinkedNodeCollection.  (For the rest of the methods, you may copy the skeleton methods that throw UnsupportedMethodException from the LinkedNodeCollection class.)

Analysis Question

1. Can you come up with a second implementation for the isEmpty method in LinkedNodeCollection?

Author: Alyce Brady abrady@kzoo.edu