Question

I need help with the Implementation of an Ordered List

(Template Files)

public interface OrderedStructure {

    public abstract int size();

    public abstract boolean add( Comparable obj ) throws IllegalArgumentException;
    public abstract Object get( int pos ) throws IndexOutOfBoundsException;
    public abstract void remove( int pos ) throws IndexOutOfBoundsException;
    public abstract void merge( OrderedList other );
}

import java.util.NoSuchElementException;

public class OrderedList implements OrderedStructure {

    // Implementation of the doubly linked nodes (nested-class)

    private static class Node {

        private Comparable value;
        private Node previous;
        private Node next;

        private Node ( Comparable value, Node previous, Node next ) {
            this.value = value;
            this.previous = previous;
            this.next = next;
        }
    }

    // Instance variables

    private Node head;

    // Representation of the empty list.

    public OrderedList() {
        // Your code here.
    }

    // Calculates the size of the list

    public int size() {
        // Remove line below and add your implementation.
        throw new UnsupportedOperationException( "not implemented yet!" );
    }


    public Object get( int pos ) {
        // Remove line below and add your implementation.
        throw new UnsupportedOperationException( "not implemented yet!" );
    }

    // Adding an element while preserving the order

    public boolean add( Comparable o ) {
        // Remove line below and add your implementation.
        throw new UnsupportedOperationException( "not implemented yet!" );
    }

    //Removes one item from the position pos.

    public void remove( int pos ) {
      // Remove line below and add your implementation.
      throw new UnsupportedOperationException( "not implemented yet!" );
    }

    // Knowing that both lists store their elements in increasing
    // order, both lists can be traversed simultaneously.

    public void merge( OrderedList other ) {
      // Remove line below and add your implementation.
      throw new UnsupportedOperationException( "not implemented yet!" );
    }
}

1. Create an implementation for the interface OrderedStructure. This implementation, called OrderedList, will use doubly-linked (with a dummy node) nodes and should have a head pointer. Furthermore, the implementation should throw exceptions when necessary. Here are the files that you will need:
   • OrderedStructure.java
   • OrderedList.java
   • Documentation

   Here is a step-by-step approach for implementing the class OrderedList. This will be a top-down approach, focusing on the general organization of the class first (adding the variables, the nested class, as well as empty methods). Once, the overall implementation is complete, we will implement the methods one by one.

   1. First, let’s create a template for the class. At this point, we are ignoring details such as the implementation of the body of the methods, and instead we are focusing on the necessary variables and the need for a static class called Node. This template needs to contain a static nested class called Node, the necessary instance variables, and empty definitions for all the methods of the interface OrderedStructure. You should not use a variable int size in this implementation. Also, the class Node should save a value of type Comparable

      The compiler will not allow us to have empty declarations for the methods that return a result. To circumvent this problem, we could add a “dummy” return statement, such as returning the value -99 for the method size.

      However, we may later forget to change the implementation, and this will cause all sorts of problems. Because of this, it is better to create an initial method that consists a throw statement.

      int size(){
              throw new UnsupportedOperationException("not implemented yet!");
      }

      Do the same for every method.

      You can now compile the class and start working on the implementation of the methods one by one. Any attempt at using a method that has not been implemented yet will be signaled with the proper exception to remind us that we still have to implement that method. You can ask your TA for further information if needed.

      You can now compile the class and start working on the implementation of the methods one by one. Any attempt at using a method that has not been implemented yet will be signaled with the proper exception to remind us that we still have to implement that method. You can ask your TA for further information if needed.

      Create a test class called OrderedListTest; at this point it will contain only a main method that declares an OrderedList and creates an OrderedList object.

      Make sure that your implementation is correct, i.e. has all the elements presented above and compiles. When you are done compiling all the files, proceed with the next step, implementing the method size().

   2. Implement the method size(), i.e. replace the throw statement by an iterative implementation that traverses the list and counts the number of elements. Add a test to the test class, simply to check that the method size works for empty lists. We will check the other cases when the method add has been completed.
   3. Implement the method boolean add( Comparable obj ); adds an element in increasing order according to the class’ natural comparison method (i.e. uses the method compareTo ). Returns true if the element can be successfully added to this OrderedList, and false otherwise.
   4. Add test cases for the method add. It will be difficult to thoroughly test the implementation, but at least the size of the list should change as new elements are added.
   5. Implement Object get( int pos ). It returns the element at the specified position in this OrderedList; the first element has the index 0. This operation must not change the state of the OrderedList.
   6. Add test to validate the methods get and add. We are now in a better position to evaluate the method add, get and size. In particular we can add elements, and use a loop to access all the elements one after the other using get. Make sure that all the methods work properly before proceeding. Do not forget that get returns an element of type Object, you will therefore need to use a type cast.
   7. Implement void remove( int pos ); Removes the element at the specified position in this OrderedList; the first element has the index 0.
   8. Add test cases for the method remove to the test class. Make sure that the method remove (as well as all the other methods) is fully debugged before continuing.

   We now have a complete implementation of the interface OrderedStructure.

2. Write an instance method, void merge( OrderedList other ), that adds all the elements of the other list to this list, such that this list preserves its property of being an ordered list. For example, let a and b be two OrderedLists, such that a contains “D”, “E” and “G”, and b contains “A”, “C”, “D” and “F”. The call a.merge( b )transforms a such that it now contains the following elements: “A”, “C”, “D”, “D”, “E”, “F” and “G”; b should not be modified by the method call. The class String implements the interface Comparable and could be used for testing.

   The objectives are to learn how to traverse and transform a doubly linked list. Therefore, you are not allowed to use any auxiliary or existing methods, in particular add, for your implementation!

Answer 1

Solution:

.............................................................................................................................................................

==========================================================================

interface OrderedStructure<E extends Comparable<E>> {

    public abstract int size();

    public abstract boolean add(E obj) throws IllegalArgumentException;
    public abstract Object get( int pos ) throws IndexOutOfBoundsException;
    public abstract void remove( int pos ) throws IndexOutOfBoundsException;
    public abstract void merge( OrderedList<E> other );
}

public class OrderedList<E extends Comparable<E>> implements OrderedStructure<E> {

    // Implementation of the doubly linked nodes (nested-class)
    private static class Node<E> {
        private E value;
        private Node<E> previous;
        private Node<E> next;

        private Node (E value, Node<E> previous, Node<E> next ) {
            this.value = value;
            this.previous = previous;
            this.next = next;
        }
    }

    // Instance variables
    private Node<E> head;

    // Representation of the empty list.
    public OrderedList() {
        head = new Node<E>(null, null, null); // dummy node.
    }

    // Calculates the size of the list
    public int size() {
        // head is always present.
        int count = 0;
        Node<E> ptr = head.next;
        while(ptr != null) {
                count++; ptr = ptr.next;
        }
        return count;
    }


    public Object get( int pos ) {
        Node<E> ptr = head.next;
        while(ptr != null && pos != 0) {
                pos--; ptr = ptr.next;
        }
        
        if(pos == 0 && ptr != null) {
                return ptr.value;
        }
        return null;
    }

    // Adding an element while preserving the order
    public boolean add(E o ) {
        Node<E> prev = head;
        
        while(prev.next != null && prev.next.value.compareTo(o) < 0) {
                prev = prev.next;
        }
        
        prev.next = new Node<>(o, prev, prev.next);
        if(prev.next.next != null) {
                prev.next.next.previous = prev.next.next;
        }
        
        return true;
    }

    //Removes one item from the position pos.
    public void remove( int pos ) {
        Node<E> prev = head;
        Node<E> ptr = head.next;
        while(ptr != null && pos != 0) {
                pos--; prev = ptr; ptr = ptr.next;
        }
        
        if(pos == 0 && ptr != null) {
                prev.next = ptr.next;
                if(ptr.next != null) {
                        ptr.previous = prev;
                }
        }
    }
    
    private void addAfter(Node<E> oldNode, E value) {
        Node<E> newNode = new Node<>(value, oldNode, oldNode.next);
        if(oldNode.next != null) {
                oldNode.next.previous = newNode;
        }
        oldNode.next = newNode;
    }

    // Knowing that both lists store their elements in increasing
    // order, both lists can be traversed simultaneously.
        @Override
        public void merge(OrderedList<E> other) {
                Node<E> prev1 = head;
                Node<E> start1 = head.next;
                Node<E> start2 = other.head.next;
                
                while(start2 != null) {
                        // we need to insert start2 value.
                        while(start1 != null && start1.value.compareTo(start2.value) < 0) {
                                prev1 = start1;
                                start1 = start1.next;
                        }
                        addAfter(prev1, start2.value);
                        start1 = prev1.next;
                        start2 = start2.next;
                }
        }
        
        public void printList() {
        // head is always present.
        Node<E> ptr = head.next;
        while(ptr != null) {
                System.out.print(ptr.value + " ");
                ptr = ptr.next;
        }
        System.out.println();
        }
        
        public static void main(String args[]) {
                OrderedList<Integer> list1 = new OrderedList<>();
                list1.add(8);
                list1.add(18);
                list1.add(16);
                list1.add(23);
                list1.add(3);
                list1.add(7);
                
                list1.printList();
                
                // remember remove taks position, not value
                list1.remove(0);
                list1.printList();
                list1.remove(2);
                list1.printList();
                System.out.print("List1: ");
                list1.printList();

                OrderedList<Integer> list2 = new OrderedList<>();
                list2.add(8);
                list2.add(18);
                list2.add(13);
                list2.add(71);
                list2.add(9);
                list2.add(15);
                System.out.print("List2: ");
                list2.printList();
                
                list1.merge(list2);

                System.out.print("Merged List: ");
                list1.printList();
        }
}

Please upvote. i did the extra credit ones too.

96 OrderedList (1) [ava Application CAProgra 3 7 8 16 18 23 7 8 16 18 23 7 8 18 23 List1: 7 8 18 23 List2: 8 9 13 15 18 71 Merged List: 78 89 13 15 18 18 23 71 97 98 // Knowing that both lists store their elements in increasing // order, both 1ists can be traversed simultaneously 100 gOverride 101 public void merge (OrderedList prev1 -head; Node start1- head.next Node start2 other.head.next; while(start2nu11) ( // we need to insert start2 value while(start1!null && start1.value.compareTo (start2.value) < 0) prev starti; start1start1.next; 112 113 114 115 116 addAfter(previ, start2.value); start1 prev1.next; Start2 start2 . next; 118 public void printlist) 119 120 121 122 123 124 125 126 127 128 public static void main(String args[]) 129 130 131 132 133 134 135 136 137 // head is always present. Node ptrhead.next; while(ptr nul1) { System.out.print(ptr.value "); ptrptr.next; System.out.println); OrderedList« Integer> listi list1.add(8); list1.add (18) list1.add (16); list1.add (23); list1.add (3) list1.add(7); new OrderedLíst()(); list1.printlist);