Question

Consider java for fixing this code please:

what i need is to insert method to be added ( please don't change the test class and any giving value in the first class )

here is the correct out put:

------------------testAddLast()----

{A}

{A->B}

{A->B->null}

{A->B->null->C}

-----------------------------

--------testSubListOfSmallerValues()----------

{}

{B->B->B->A}

{F->B->B->B->A->D}

{F->B->B->G->B->A->M->D}

-----------------------------

------------Test lastIndexOf()-----

-1

3

-1

-1

0

5

2

-----------------------------

---------testRetainAll()---------

{}

{6:Tony->6:Tony}

{null->bad->null}

-----------------------------

---------------Test removeStartingAtBack---

false

true

{apple->null->bad->null}

true

{apple->null->bad}

{2:Morning->3:Abby->4:Tim->5:Tom->6:Tony}

-----------------------------

---------test insertionSort()---------

{}

{D}

{D->E->E->F->G}

-----------------------------

the code is here:

/* NOTE: PLEASE DO NOT CHANGE OR REVISE ANY CODE IN THIS TESTER */
/* !!! IF YOU CHANGE THIS FILE, YOU GET A ZERO FOR THIS PROJECT !!!! */
class CDoublyLinkedList {

    private class Node {
        private Object data; // Assume data implemented Comparable
        private Node next, prev;

        private Node(Object data, Node pref, Node next) {
            this.data = data;
            this.prev = pref;
            this.next = next;
        }
    }

    private Node head;
    private int size;

    public CDoublyLinkedList() {
        this.head = new Node(null, null, null);
        this.head.next = this.head;
        this.head.prev = this.head;
        this.size = 0;
    }

    public boolean isEmpty() {
        return this.head == this.head.next;
    }

    // Add Object data to start of this LinkedList
    // Please DO NOT change this addFirst() method.
    public void addFirst(Object data) {
        Node nn = new Node(data, this.head, this.head.next);
        this.head.next.prev = nn;
        this.head.next = nn;
        this.size++;
    }

    // write a method void addLast(Object data) that will insert
    // the piece of data at the end of the current list.
    // Note: this list is allowed to store null data element in its list node.
    public void addLast(Object data) {
        Node nn = new Node(data, this.head.prev, this.head);
        this.head.prev.next = nn;
        this.head.prev = nn;
        this.size++;
    }

    // Write the subListOfSmallerValues method.
    // It should return a CDoublyLinkedList object
    // containing data that is smaller than the value passed to the method.
    // If a null data element in this list is encountered, you can skip it.
    public CDoublyLinkedList subListOfSmallerValues(Comparable data) {
        CDoublyLinkedList result = new CDoublyLinkedList();

        Node start = head.next;
        while (start != head) {
            if (start.data != null && data.compareTo(start.data) > 0) {
                result.addLast(start.data);
            }
            start = start.next;
        }

        return result; // change this as needed.
    }

    // This method should remove the first occurrence of the data from the list,
// starting at the *BACK* of the list.
// It scans the list from back to the front by following the prev links.
    // The method should return true if successful, false otherwise.
    // Note that list node may contain null data element. Please handle this edge
    // case.
    public boolean removeStartingAtBack(Object dataToRemove) {

        Node start = head.prev;
        while (start != head) {
            if ((start.data == null && dataToRemove == null)
                    || (start.data != null && dataToRemove.equals(start.data))) {
                start.prev.next = start.next;
                start.next.prev = start.prev;
                size--;
                return true;
            }
            start = start.prev;
        }

        return false;// change this as needed.
    }

    // Returns the index of the last occurrence of the specified element in this
    // list,
    // or -1 if this list does not contain the element.
    // More formally, returns the highest index i
    // such that (o==null ? get(i)==null : o.equals(get(i))),
    // or -1 if there is no such index.
    // Note: a list node may store a null data element. Please handle this edge
    // case.
    public int lastIndexOf(Object o) {
        int index = -1;
        int i = 0;
        Node start = head.next;
        while (start != head) {
            if ((start.data == null && o == null) || (start.data != null && start.data.equals(o))) {
                index = i;
            }
            start = start.next;
            i++;
        }
        return index; // change this as needed.
    }

    // Removes from this list all of its elements that
    // are NOT contained in the specified linkedlist other.
    // If any element has been removed from this list,
    // returns true. Otherwise returns false.
    // If other list is null, throws NullPointerException.
    // Helper methods are allowed.
    public boolean retainAll(CDoublyLinkedList other) throws NullPointerException {
        if (other == null) {
            throw new NullPointerException();
        }

        boolean status = false;

        Node start = head.prev;
        while (start != head) {
            if (other.lastIndexOf(start.data) == -1) {

                Object x = start.data;
                start = start.prev;
                removeStartingAtBack(x);

                status = true;
            } else {
                start = start.prev;
            }
        }

        return status; // change this as needed.
    }

    // a comes before, b comes later.
    private void swapNodes(Node a, Node b) {
        Node prev1 = a.prev;
        Node next1 = a.next;
        Node prev2 = b.prev;
        Node next2 = b.next;

        a.next = next2;
        a.prev = prev2;
        b.next = next1;
        b.prev = prev1;     

        prev1.next = b;
        next1.prev = b;
        prev2.next = a;
        next2.prev = a;
    }

    // Write this method to sort this list using insertion sort algorithm,
    // as we have learned in the classroom.
    public void insertionSort() {
    }

    @Override
    public String toString() {
        String result = "{";
        for (Node node = this.head.next; node != this.head; node = node.next) {
            if (node.next != this.head)
                result += node.data + "->";
            else
                result += node.data;
        }
        return result + "}";
    }
}

public class Tester {

    private static CDoublyLinkedList list0;
    private static CDoublyLinkedList list2;
    private static CDoublyLinkedList list3;

    private static void init() {
        list0 = new CDoublyLinkedList();
        list2 = new CDoublyLinkedList();
        list3 = new CDoublyLinkedList();
        list2.addFirst("6:Tony");
        list2.addFirst("5:Tom");
        list2.addFirst("4:Tim");
        list2.addFirst("3:Abby");
        list2.addFirst("2:Morning");
        list2.addFirst("1:Good");
        list0.addFirst(null);
        list0.addFirst("bad");
        list0.addFirst("apple");
        list0.addFirst(null);
    }

    public static void drawLine() {
        System.out.println("-----------------------------");
    }

    public static void testAddFirst() { // passed test
        init();
        drawLine();
        System.out.println(list0);
        System.out.println(list2);
        System.out.println(list3);
        drawLine();
    }

    public static void testAddLast() { //
        System.out.println("------------------testAddLast()----");
        init();
        list3.addLast("A");
        System.out.println(list3);
        list3.addLast("B");
        System.out.println(list3);
        list3.addLast(null);
        System.out.println(list3);
        list3.addLast("C");
        System.out.println(list3);
        drawLine();
    }

    public static void testRemoveStartingAtBack() {
        init();
        System.out.println("---------------Test removeStartingAtBack---");
        list0.addFirst("apple");
        System.out.println(list0.removeStartingAtBack("notexist")); // false
        System.out.println(list0.removeStartingAtBack("apple")); // true
        System.out.println(list0); // apple, null, bad, null
        System.out.println(list0.removeStartingAtBack(null)); // true
        System.out.println(list0); // apple, null, bad
        list2.removeStartingAtBack("1:Good");
        System.out.println(list2);

        drawLine();
    }

    public static void testLastIndexOf() {
        init();
        System.out.println("------------Test lastIndexOf()-----");
        System.out.println(list3.lastIndexOf("notexist")); // -1
        System.out.println(list0.lastIndexOf(null)); // 3
        System.out.println(list2.lastIndexOf(null)); // -1
        System.out.println(list2.lastIndexOf("notexist"));// -1
        System.out.println(list2.lastIndexOf("1:Good"));// 0
        System.out.println(list2.lastIndexOf("6:Tony"));// 5
        list3.addFirst("B3");
        list3.addFirst("B3");
        list3.addFirst("B3");
        System.out.println(list3.lastIndexOf("B3"));// 2
        drawLine();
    }

    public static void testSubList() {
        init();
        list3.addFirst("D");
        list3.addFirst("M");
        list3.addFirst("A");
        list3.addFirst("B");
        list3.addFirst("G");
        list3.addFirst("B");
        list3.addFirst("B");
        list3.addFirst("F");
        System.out.println("--------testSubListOfSmallerValues()----------");
        System.out.println(list3.subListOfSmallerValues("A")); // none
        System.out.println(list3.subListOfSmallerValues("C")); // BBBA
        System.out.println(list3.subListOfSmallerValues("G")); // FBBBAD
        System.out.println(list3.subListOfSmallerValues("Q")); // FBBGBAMD
        drawLine();
    }

    public static void testRetainAll() {
        init();
        System.out.println("---------testRetainAll()---------");
        list3.retainAll(list0);
        System.out.println(list3);
        list3.addFirst("C");
        list3.addFirst("C");
        list3.addFirst("6:Tony");
        list3.addFirst("6:Tony");
        list3.retainAll(list2);
        System.out.println(list3);
        init();
        list3.addFirst(null);
        list3.addFirst("bad");
        list3.addFirst(null);
        list3.addFirst("B");
        list3.addFirst("A");
        list3.retainAll(list0);
        System.out.println(list3);
        drawLine();
    }

    public static void testSort() {
        init();
        System.out.println("---------test insertionSort()---------");
        list3.insertionSort();
        System.out.println(list3); // none
        list3.addFirst("D");
        System.out.println(list3); // D
        list3.addFirst("F");
        list3.addFirst("E");
        list3.addFirst("G");
        list3.addFirst("E");
        list3.insertionSort();
        System.out.println(list3); // DEEFG
        drawLine();
    }

    public static void main(String argv[]) {
        testAddLast();
        testSubList();
        testLastIndexOf();
        testRetainAll();
        testRemoveStartingAtBack();
        testSort();
    }// end of main
}

Answer 1

Tester.java

public class Tester {

   private static CDoublyLinkedList list0;
   private static CDoublyLinkedList list2;
   private static CDoublyLinkedList list3;
  
   private static void init() {
       list0 = new CDoublyLinkedList();
       list2 = new CDoublyLinkedList();
       list3 = new CDoublyLinkedList();
       list2.addFirst("6:Tony");
       list2.addFirst("5:Tom");
       list2.addFirst("4:Tim");
       list2.addFirst("3:Abby");
       list2.addFirst("2:Morning");
       list2.addFirst("1:Good");
       list0.addFirst(null);
       list0.addFirst("bad");
       list0.addFirst("apple");
       list0.addFirst(null);
   }
   public static void drawLine() {
       System.out.println("-----------------------------");
   }
  
   public static void testAddFirst() { //passed test
       init();
       drawLine();
       System.out.println(list0);
       System.out.println(list2);
       System.out.println(list3);
       drawLine();
   }
  
   public static void testAddLast() { //
       System.out.println("------------------testAddLast()----");
       init();
       list3.addLast("A");
       System.out.println(list3);
       list3.addLast("B");
       System.out.println(list3);
       list3.addLast(null);
       System.out.println(list3);
       list3.addLast("C");
       System.out.println(list3);
       drawLine();
   }
  

   public static void testRemoveStartingAtBack() {
       init();
       System.out.println("---------------Test removeStartingAtBack---");
       list0.addFirst("apple");
       System.out.println(list0.removeStartingAtBack("notexist")); //false
       System.out.println(list0.removeStartingAtBack("apple")); //true
       System.out.println(list0); //apple, null, bad, null
       System.out.println(list0.removeStartingAtBack(null)); //true
       System.out.println(list0); //apple, null, bad
       list2.removeStartingAtBack("1:Good");
       System.out.println(list2);

       drawLine();
   }
  

   public static void testLastIndexOf() {
       init();
       System.out.println("------------Test lastIndexOf()-----");
       System.out.println(list3.lastIndexOf("notexist")); //-1
       System.out.println(list0.lastIndexOf(null)); //3
       System.out.println(list2.lastIndexOf(null)); //-1
       System.out.println(list2.lastIndexOf("notexist"));//-1
       System.out.println(list2.lastIndexOf("1:Good"));//0
       System.out.println(list2.lastIndexOf("6:Tony"));//5
       list3.addFirst("B3");
       list3.addFirst("B3");
       list3.addFirst("B3");
       System.out.println(list3.lastIndexOf("B3"));//2
       drawLine();
   }
  
   public static void testSubList() {
       init();
       list3.addFirst("D");
       list3.addFirst("M");
       list3.addFirst("A");
       list3.addFirst("B");
       list3.addFirst("G");
       list3.addFirst("B");
       list3.addFirst("B");
       list3.addFirst("F");
       System.out.println("--------testSubListOfSmallerValues()----------");
       System.out.println(list3.subListOfSmallerValues("A")); //none
       System.out.println(list3.subListOfSmallerValues("C")); //BBBA
       System.out.println(list3.subListOfSmallerValues("G")); //FBBBAD
       System.out.println(list3.subListOfSmallerValues("Q")); //FBBGBAMD
       drawLine();
   }
  
   public static void testRetainAll() {
       init();
       System.out.println("---------testRetainAll()---------");
       list3.retainAll(list0);
       System.out.println(list3);
       list3.addFirst("C");
       list3.addFirst("C");
       list3.addFirst("6:Tony");
       list3.addFirst("6:Tony");
       list3.retainAll(list2);
       System.out.println(list3);
       init();
       list3.addFirst(null);
       list3.addFirst("bad");
       list3.addFirst(null);
       list3.addFirst("B");
       list3.addFirst("A");
       list3.retainAll(list0);
       System.out.println(list3);
       drawLine();
   }
  
   public static void testSort() {
       init();
       System.out.println("---------test insertionSort()---------");
       list3.insertionSort();
       System.out.println(list3); //none
       list3.addFirst("D");
       System.out.println(list3); //D
       list3.addFirst("F");
       list3.addFirst("E");
       list3.addFirst("G");
       list3.addFirst("E");
       list3.insertionSort();
       System.out.println(list3); //DEEFG
       drawLine();
   }
  
   public static void main(String argv[]) {

       testAddLast();
       testSubList();
       testLastIndexOf();
       testRetainAll();
       testRemoveStartingAtBack();
       testSort();
      
   }//end of main
}

CDoublyLinkedList.java

public class CDoublyLinkedList {

   private class Node {
       private Object data;   //Assume data implemented Comparable
       private Node next, prev;
       private Node(Object data, Node pref, Node next)
       {
           this.data = data;
           this.prev = pref;
           this.next = next;
       }
   }

   private Node head;
   private int size;

   public CDoublyLinkedList() {
       this.head = new Node(null, null, null );
       this.head.next = this.head;
       this.head.prev=this.head;
       this.size = 0;
   }

   public boolean isEmpty() {
       return this.head == this.head.next;
   }
  
   // Add Object data to start of this LinkedList
   // Please DO NOT change this addFirst() method.
   // You must keep and include this provided addFirst() method
   //      in your source code.
   public void addFirst(Object data) {
       Node nn = new Node(data, this.head, this.head.next);
       this.head.next.prev = nn;
       this.head.next = nn;
       this.size ++;
   }

   // write a method void addLast(Object data) that will insert
   // the piece of data at the end of the current list.
   // Note: this list is allowed to store null data element in its list node.
   public void addLast(Object data) {
       Node nn = new Node(data, this.head.prev, this.head);
       this.head.prev.next = nn;
       this.head.prev = nn;
       this.size++;
   }

   // Write the subListOfSmallerValues method.
   // It should return a CDoublyLinkedList object
   //     containing data that is smaller than the value passed to the method.
        // If a null data element in this list is encountered, you can skip it.
   public CDoublyLinkedList subListOfSmallerValues(Comparable data) {
       CDoublyLinkedList small = new CDoublyLinkedList();
       if (data == null) {
           return small;
       } else {
           Node cur = this.head.next;
           while (cur != this.head) {
               if (cur != null && ((Comparable)cur.data).compareTo(data) < 0) {
                   small.addLast(cur.data);
               }
               cur = cur.next;
           }
       }
       return small;
   }
  
   // This method should remove the first occurrence of the data from the list,
        //      starting at the *BACK* of the list.
        // It scans the list from back to the front by following the prev links.
   // The method should return true if successful, false otherwise.
   // Note that list node may contain null data element. Please handle this edge case.
   public boolean removeStartingAtBack(Object dataToRemove) {
       Node cur = this.head.prev;
       boolean toRem = false;
       while (cur != this.head) {
           if (cur.data == null || dataToRemove == null) {
               if (cur.data == null && dataToRemove == null) {
                   toRem = true;
               }
           } else if (cur.data.equals(dataToRemove)) {
               toRem = true;
           }
           if (toRem) {
               cur.prev.next = cur.next;
               cur.next.prev = cur.prev;
               this.size--;
               return true;
           }
           cur = cur.prev;
       }
  
       return false;//change this as needed.
   }
  
   // Returns the index of the last occurrence of the specified element in this list,
   //     or -1 if this list does not contain the element.
   // More formally, returns the highest index i
   //     such that (o==null ? get(i)==null : o.equals(get(i))),
   //     or -1 if there is no such index.
   // Note: a list node may store a null data element. Please handle this edge case.
   public int lastIndexOf(Object o) {
       Node cur = this.head.prev;
       int index = this.size - 1;
       while (cur != this.head) {
           if (cur.data == null && o == null) {
               return index;
           } else if (cur.data != null && o != null && cur.data.equals(o)) {
               return index;
           }
           cur = cur.prev;
           index--;
       }
       return -1; //change this as needed.
   }
   // Removes from this list all of its elements that
   //    are NOT contained in the specified linkedlist other.
   // If any element has been removed from this list,
   //    returns true. Otherwise returns false.
   // If other list is null, throws NullPointerException.
        // Helper methods are allowed.
   public boolean retainAll(CDoublyLinkedList other) throws NullPointerException {
       if (other == null) {
           throw new NullPointerException("Input list is null");
       }
       boolean del = false;
       Node cur = this.head.next;
       while(cur != this.head) {
           if (!other.contains(cur.data)) {
               cur.prev.next = cur.next;
               cur.next.prev = cur.prev;
               if (del == false) {
                   del = true;
               }
           }
           cur = cur.next;
       }
       return del;
   }

   //Helper method for retainAll
   private boolean contains(Object data) {
       Node cur = this.head.next;
       while(cur != this.head) {
           if(cur.data == null && data == null) {
               return true;
           } else if (cur.data != null && data != null && cur.data.equals(data)) {
               return true;
           }
           cur = cur.next;
       }  
       return false;
   }
  

        // Write this method to sort this list using insertion sort algorithm,
        //      as we have learned in the classroom.
   public void insertionSort() {
       Node curBack = this.head.next, fUnsort = curBack.next, nn;
       while (fUnsort != this.head) {
           while (curBack != this.head && ((Comparable)curBack.data).compareTo(fUnsort.data) > 0) {
               curBack = curBack.prev;
           }
           if (curBack != fUnsort.prev) {
               nn = new Node(fUnsort.data, curBack, curBack.next);
               curBack.next.prev = nn;
               curBack.next = nn;
               fUnsort.prev.next = fUnsort.next;
               fUnsort.next.prev = fUnsort.prev;
           }
           fUnsort = fUnsort.next; curBack = fUnsort.prev;
       }
   }
  
   @Override
   public String toString() {
       String result = "{";
       for (Node node = this.head.next; node != this.head; node = node.next) {
           if(node.next != this.head)
               result += node.data + "->";
           else
               result += node.data;
       }
       return result + "}";
   }
}