Assignment #4: Linked Lists and Binary Search Trees

In this assignment you will provide two additional implementations of the DoubleEndedPriorityQueue interface specified in Assignment #1. Recall that the interface looks like:

package cop3530; 

public interface DoubleEndedPriorityQueue 
{ 
    void makeEmpty( ); 
    void insert( Object x ); 
    Object deleteMin( ); 
    Object deleteMax( ); 
    Object findMin( ); 
    Object findMax( ); 
    boolean isEmpty( ); 
}

Note that duplicates may be inserted. If more than one item is tied as minimum/maximum, then the deletion operation removes exactly one occurrence, leaving others in place. Recall also that any implementation class would be expected to provide a toString method. Your toString method must list all the elements in the collection, in sorted order, in LINEAR TIME. I will provide a test program two days prior to the due date. The test program will provided as a .class file, without any Java source, so it is important that you write sufficient test cases on your own to convince yourself that your logic works.

Linked List Implementation

In the linked list implementation, you should use a doubly-linked list, maintaining a reference to both the first and last nodes. Thus, the private representation looks like:

    private Comparator cmp; 
    private Node first = null;
    private Node last  = null;

In this implementation, when the collection is empty, both first and last are null. No header or tail nodes should be used. Your implementation class must be cop3530.ListDoubleEndedPriorityQueue.

Binary Search Tree Implementation

In the binary search tree implementation, which is completely unrelated to the linked list implementation above, you will use an unbalanced binary search tree. Since duplicates are allowed, each node will have to store a linked list of all the entries that are considered identical. Two values are identical if the comparator returns 0, even if the objects are unequal according to the equals method. A sketch of the private representation looks something like this:

    private Comparator cmp; 
    private Node root = null; 

    private void toString( Node t, StringBuffer sb )
      { ... the recursive routine to be called by toString ... }

    private static class Node
    {
        private Node left;
        private Node right;
        private ListNode items;

        private static class ListNode
        {
            private Object data;
            private ListNode next;

            public ListNode( Object d, ListNode n )
              { data = d; next = n; }
        }

        public Node( Object data )
        {
            left = right = null;
            items = new ListNode( data, null );
        }

    }

In accessing objects of type ListNode from the TreeDoubleEndedPriorityQueue class, it may be necessary to use Node.ListNode as the qualified class name, depending on the context. Of course, ListNode cannot be viewed from outside TreeDoubleEndedPriorityQueue.

Observe that when you insert or remove into the double-ended priority queue, (tree) nodes are created only when you add an element that does not compare to 0 with any other element in the tree. Tree nodes are removed only when the item to be removed was the only item in its node.

You will definitely need to use recursion to implement toString, and you must use string buffers with appends only to avoid quadratic behavior. The other routines do not necessarily require recursion but the use of recursion is at your discretion and may simplify some logic.

Your implementation class must be cop3530.TreeDoubleEndedPriorityQueue.

What to Submit

Submit your source code and the result of running the class file that I provide.