Assignment #4: Linked Lists and Binary Search Trees

Covers

Linked data structures, linked lists, binary search trees, Java programming

Basic Requirements

In this assignment you will provide two implementations of the DoubleEndedPriorityQueue interface specified as follows:

package cop3530; 

public interface DoubleEndedPriorityQueue<AnyType>
{ 
    void makeEmpty( ); 
    void add( AnyType x ); 
    AnyType deleteMin( ); 
    AnyType deleteMax( ); 
    AnyType findMin( ); 
    AnyType 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. If the find or delete operations are invoked on an empty DoubleEndedPriorityQueue, then you should throw an unchecked runtime exception of type cop3530.UnderflowException. (Note the name of the class: the test program will fail if you return null or throw an UnderflowException that is not part of package cop3530). 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. The test program will be 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<? super AnyType> cmp; 
    private Node<AnyType> first = null;
    private Node<AnyType> 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 singly-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<? super AnyType> cmp; 
    private Node<AnyType> root = null; 

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

    private static class Node<AnyType>
    {
        private Node<AnyType> left;
        private Node<AnyType> right;
        private ListNode<AnyType> items;

        private static class ListNode<AnyType>
        {
            private AnyType data;
            private ListNode<AnyType> next;

            public ListNode( AnyType d, ListNode<AnyType> n )
              { data = d; next = n; }
        }

        public Node( AnyType data )
        {
            left = right = null;
            items = new ListNode<AnyType>( 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 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.