Linked Lists:
Inside View of the LinkedNodeCollection Class

In the first LinkedNodeCollection mini-lab, you implemented a number of basic observer methods in the LinkedNodeCollection and DoublyLinkedNodeCollection classes.  In this lab, you will turn your focus to the add and remove methods.

Mini-Lab 2: Basic Modifier Methods

Understanding the add method for a LinkedNodeCollection

The specification for the LinkedNodeCollection.add method is that it always adds the new element to the beginning of the list. The test cases for the add method include:

• Adding an element to an empty list.
• Adding an element to the beginning of a list containing only one element.
• Adding an element to the beginning of a list containing multiple elements.

The following diagrams illustrate the effect of the add method for these cases.

Adding to Empty List:

Before add		After add

Adding to A Single-Element List:

Before add		After add

Adding to A Multiple-Element List:

Before add
After add

Developing the Code: First Draft

Using these test cases to structure the code, we could develop the following, somewhat verbose, version of the add method.

public boolean add(Object o)
{
    if ( isEmpty() )
    {
        ListNode temp = new ListNode(o, null);
        head = temp;
        numElts = 1;
        return true;
    }
    else if ( size() == 1 )
    {
        ListNode temp = new ListNode(o, head);
        head = temp;
        numElts = 2;
        return true;
    }
    else if ( size() > 1  )
    {
        ListNode temp = new ListNode(o, head);
        head = temp;
        numElts++;
        return true;
    }
    else   //  should never get here!
        return false;
}

Implementing the Modifier Methods for a LinkedNodeCollection

• Review the add method in LinkedNodeCollection and compare it to the code developed above.  Does the implementation in the LinkedNodeCollection class address all the "extreme examples" or boundary cases it needs to address?
   
• Identify the test cases for the add method in DoublyLinkedNodeCollection.  Are they the same as for the LinkedNodeCollection class, or do you need to add any?  Develop "Before" and "After" diagrams for these cases.
   
• Implement the add method in the DoublyLinkedNodeCollection class.
   
• The test cases for the remove method include the following:

  empty list	remove 1st element (others are left)
  element is not in list (empty list is special case)	remove element from middle of list
  remove only element	remove last element in list

  
  Develop "Before" and "After" diagrams for these cases.
   
• Implement the remove method in the LinkedNodeCollection class.
   
• Implement the clear method in the LinkedNodeCollection class.
   
• Update your test driver to test these two methods.

Author: Alyce Brady abrady@kzoo.edu