Linked List Labs

The Linked List Labs give students a chance to write a program that uses the standard Java LinkedList class and then to implement on their own two simpler classes, LinkedNodeCollection and DoublyLinkedNodeCollection. (Note: the LinkedNodeCollection class uses the ListNodeclass and is derived from the LinkedCollection class in W. Collins's Data Structures and the Java Collections Framework, McGraw-Hill, 2002.)

Downloading the Linked List Labs:

Download the zip file containing the starting code files for the Linked List Labs by right-clicking or shift-clicking on the following link: LLists.zip.

When you unzip this file, it will create a folder called LLists  that contains the instructions for the labs (in the two sub-folders), some diagrams used in the instructions, and several source files.  The lab instructions will introduce the source files as you need them.

The Linked List Labs consist of several mini-labs, which are meant to be short enough to complete in a single class period, and a programming project, which may need a longer time-block or several class periods to complete, or which could be completed outside of class.

Mini-Lab: Bad News Bearers

Tasks include:

• Add elements to a linked list (specifically, an instance of the LinkedList class) and traverse the linked list.
• Use an Iterator class developed for this lab, CircularLLIterator, to implement a variant on the classic mathematics problem known as the Josephus Problem.

Mini-Lab: LinkedNodeCollection and DoublyLinkedNodeCollection: Basic Observer Methods

Tasks include:

• Implement some of the basic observer methods in the LinkedNodeCollection class.
• Diagram the boundary test cases for the DoublyLinkedNodeCollection class.
• Implement some of the basic observer methods in the DoublyLinkedNodeCollection class.

Mini-Lab: LinkedNodeCollection and DoublyLinkedNodeCollection: The Modifier Methods

Tasks include:

• Analyze the LinkedNodeCollection add method.
• Implement the DoublyLinkedNodeCollection add method.
• Diagram what happens when an object is removed from a LinkedNodeCollection object.
• Implement the remove and clear methods in LinkedNodeCollection.

Programming Project: Completing the LinkedNodeCollection and DoublyLinkedNodeCollection Implementations

Tasks include:

• Implement the remaining observer methods in LinkedNodeCollection and DoublyLinkedNodeCollection.
• Implement the remove and clear methods in DoublyLinkedNodeCollection.
• Implement the add and remove methods in LinkedNodeCollectionIterator and DoublyLinkedNodeCollectionIterator.
• Modify the Bad News Bearers program from the first mini-lab to use DoublyLinkedNodeCollection and CircularLCIterator.