CMPU 102 - Assignment 3
List ADT, Circular-Doubly-Linked-list
Assigned: Monday, Feb. 18
Due: Monday, Feb. 25

In this assignment you will:

  1. define two classes that use Generic types, and
  2. implement a SortedListInterface using a circular doubly-linked list with a dummy head node.

Summary: You will be given a starter project that contains source files:

The data structure "behind the wall" will be a circular, reference-based implementation of a sorted linked list.  The ADT you will implement is listed below. The classes you will implement are GNode and CircDoublyLL. 

Download the starter project

  1. Click here to download the starter project: assign3.zip. 
  2. Save it in your cs102 directory.
  3. Unzip the file.
  4. You should be able to Open this as an existing project in NetBeans (described next)

Launch NetBeans and Open Project

  1. From NetBeans, go to the File menu and select "Open Project" -- or click on the third button from the left on the button bar.
  2. Navigate to your cs102 folder and select the folder named "assign3" 
  3. The "Open Project Folder" button should be enabled. Click it to open the starter project.
  4. The only files you need to modify are GNode.java and CircDoublyLL.java.

The Interface

Here is SortedListInterface, the ADT you will be implementing:
public interface SortedListInterface<E> {
   
    /** Determines whether this sorted list is empty. */
    public boolean sortedIsEmpty();
   
    /** Returns the number of items that are in a sorted list. */
    public int sortedSize();
   
    /**
     * Inserts item into its proper sorted position in a
     * sorted list. 
     */
    public void sortedAdd(E item);
   
    /**
     * Deletes item from a sorted list.
     * Throws an exception if the item is not found.
     */
    public void sortedRemove(E item);
   
    /**
     * Returns the item at position index of a sorted list,
     * if 1 <= index <= sortedSize().
     * The list is left unchanged by this operation.
     * Throws an exception if the index is out of range.
     */
    public E sortedGet(int index);
   
    /**
     * Returns the position where item belongs or exists
     * in this sorted list; item and the list are unchanged.
     */
    public int locateIndex(E item);
}

Implementation Details

Class GNode:

You should begin by implementing this class, in file GNode.java.  Objects of this class have three instance variables:  prev and next, which are references to other GNode<E> objects, and item, which will contain a reference to a generic item of type E.

Type E is a placeholder for the actual type that will be supplied by the client in the application class Main. Since GNode<E> extends Comparable<E>, the actual type that replaces this placeholder must implement Java's Comparable interface.  The SortedLinkedList interface is generic, which means that the class CircDoublyLL that implements it and the class GNode that CircDoublyLL uses to hold the sequence of items must also both be generic.  

Implementation class GNode is very similar to the implementation of class Node for singly-linked lists given in Carrano & Prichard on pages 231-232 except that now there are two references to other GNode objects and the placeholder E is used to indicate the type of item that is contained.

Class CircDoublyLL:

Next implement this class, in file CircDoublyLL.java.  In this class we've provided the fields you must use, and the stubs (headers and empty bodies) for all the methods in the SortedListInterface that must be implemented. You must implement the ADT methods using only the fields provided, although you may implement private helper methods, if you wish. 

The instance variables:

You are given two instance variables: head and size.  The variable head is a reference to a dummy head node. 

The constructor:

When you implement the constructor for this class you will create a GNode<E> object whose two references both reference itself. The size of the list will initially be 0 (the dummy head node doesn't count).  

The sortedInsert and sortedRemove methods:

When you implement the sortedInsert and sortedRemove methods in this class, be sure to adjust the list size accordingly.  With a dummy head node, there are no special cases for performing inserts or removes.  Just be sure you cannot delete the head node. When the first node is added to the list, it will have the same predecessor and successor (the dummy node head refers to).  After the first insert occurs dummy.prev and dummy.next will refer to the newNode; newNode.prev and newNode.next will both refer to the dummy.  This is not a special case.  The sortedInsert method is implemented the same way for all inserts.  You will need to declare a local GNode reference to traverse the sorted list to find the location where the new item is to be placed.  You must also be able to recognize when you reach the end of the list (if that is where the new item should go).  You may refer to page 262 in Carrano & Prichard for additional information on implementing this method.

The same situation exists when you are performing a remove or a get.  You must move a node reference to the node containing the item to be retrieved or deleted and be sure that you do not continue to circulate around the linked list.  If the item to be deleted is not present in the list, do nothing.  Pay close attention to the comments in the stubs and in the interface listed above to help you implement each of the methods of the class.

Class Main:

There is nothing for you to implement in Main, but you should read through it and understand how the code tests your CircDoublyLL class. We have created two CircDoublyLL objects holding items of types Integer and String, respectively. Items for both of these lists are produced from a list of primitives of type int that are converted into Integer and String objects.  Initially, 15 values will be added to each list. Notice the use of the for-each loop to iterate through the array of values and add them to the lists. Pretty cool, huh? 

Since each list contains items of a different respective type, the resulting sorted lists will contain the same items in different sequences. Next, each list will be printed out in forward and reverse order. (In case you were wondering when we were going to exploit the doubly-linked lists.)  Once the lists are printed, we check for the position of a particular value in both lists.

Then, some elements will be removed from each of the lists, and the two lists will be printed in forward and reverse order again. Finally, we'll check the position of the same item we checked before (the new positions should reflect the removals). You should refer to the code in Main to observe how these lists are declared and constructed, and you should note and be able to explain the difference in the ordering between the Integer and String items in the two lists.

Sample Output

When your project is fully implemented, running the code in Main will produce the following output:

init:
deps-jar:
compile:
run:
Creating a linked list of Integers and a linked list of Strings...
===> Both lists successfully created and initially empty.

Original list of Integers:
  Ascending order: 1 2 5 7 8 11 22 55 77 88 111 222 555 777 888
  Descending order: 888 777 555 222 111 88 77 55 22 11 8 7 5 2 1

Original list of Strings:
  Ascending order: 1 11 111 2 22 222 5 55 555 7 77 777 8 88 888
  Descending order: 888 88 8 777 77 7 555 55 5 222 22 2 111 11 1

Locate position of 5 in both lists:
  listOfIntegers index = 3
  listOfStrings index = 7

===> Removing 1, 55, and 888 from both lists...

Revised list of Integers:
  Ascending order: 2 5 7 8 11 22 77 88 111 222 555 777
  Descending order: 777 555 222 111 88 77 22 11 8 7 5 2

Revised list of Strings:
  Ascending order: 11 111 2 22 222 5 555 7 77 777 8 88
  Descending order: 88 8 777 77 7 555 5 222 22 2 111 11

Locate position of 5 in both lists:
  listOfIntegers index = 2
  listOfStrings index = 6
BUILD SUCCESSFUL (total time: 0 seconds)

Submitting your solution

From a terminal window, type the following commands: 

cd
cd cs102 
submit102 assign3