Question

Java/LinkedList Need help with a few of the TODO parts, more info below in comments in bold.

Thanks,

package lab4;

import java.util.IdentityHashMap;

public class IntNode implements Cloneable {
   private int data;
   private IntNode next;
  
   public IntNode(int d, IntNode n) {
       data = d;
       next = n;
   }
  
   public IntNode getNext() {
       return next;
   }
  
  
   /// Override methods from Object
  
   @Override
   public boolean equals(Object obj) {
       throw new UnsupportedOperationException("Don't use .equals to compare nodes!");
   }
  
   @Override
   public IntNode clone() {
       try {
           return (IntNode)super.clone();
       } catch (CloneNotSupportedException e) {
           throw new AssertionError("IntNodes should be cloneable!");
       }
   }
  
   protected String originalToString() {
       return super.toString();
   }
  
   @Override
   public String toString() {
       String nextString = "null";
       if (next != null) nextString = next.originalToString();
       return super.toString() + "(" + data + "." + nextString + ")";
   }
  
  
   /// Print method that is used for testing
   /**
   * Convert a list to a string for debugging purposes.
   * The string is of the form [n1, n2, n3, ...].
   * if the list ends in a cycle then we have "..." followed by
   * the one-based index of the node we go back to.
   * @param head list t print, may be null
   * @return string representation of the whole list.
   */
   public static String listToString(IntNode head) {
       if (head == null) return "[]";
       IdentityHashMap<IntNode,Integer> m = new IdentityHashMap<>();
       StringBuilder sb = new StringBuilder("[");
       sb.append(head.data);
       m.put(head, 0);
       int n = 1;
       for (IntNode p = head.next; p != null; p = p.next) {
           Integer boxed = m.get(p);
           if (boxed != null) {
               sb.append(", ..." + (n-boxed));
               break;
           }
           m.put(p, n++);
           sb.append(", " + p.data);
       }
       sb.append("]");
       return sb.toString();
   }  
   public static IntNode exercise0() {
       return null; // []
   }
  
   public static IntNode exercise1() {
       return null; // TODO [42], retrun list with single value in it. Number 42
   }
  
   public static IntNode exercise2() {
       return null; // TODO [1, 2, 3], return a list with the values 1,2, and 3. This will have 3 nodes
   }
  
   public static IntNode exercise3() {
       return null; // TODO [9, ...1], create a cyclic list of nines with a single node pointing to itself.
   }
  
   public static IntNode exercise4() {
       return null; // TODO [4, 3, 2, 1, ...3], create a list that starts 4, 3, 2, 1 but then cycles back to the "2"node again making a loop.
   }
  
   public static IntNode exercise5(IntNode param) {
       return null; // TODO: change second element to 4, change data in the second element of a list with at least two elements to "4"
   }
  
   public static IntNode exercise6(IntNode param) {
       return null; // TODO: remove second element, code should now remove(bypass) the second element of a list with at least two // elements
   }
  
   public static int exercise7(IntNode param) {
       return 0; // TODO: count number of nodes in list (use NORMAL loop), count up all nodes in the list passed in and rettrun the // count.
   }
  
   public static IntNode exercise8(IntNode param) {
       final IntNode dummy = new IntNode(999,null);
       IntNode last = dummy; // "last" node currently is the fake node.
      // TODO copy list by tacking on each element to the last node
       // of the result list. Use the NORMAL idiom
       return dummy.next;
   }
  
   public static IntNode exercise9(IntNode param, int v) {
       return null; // TODO: add v to the end of a non-empty list (in general!)
       // NB: We recommend using the FOLLOWER idiom
   }
}

Answer 1

import java.util.IdentityHashMap;

public class IntNode implements Cloneable {
   private int data;
   private IntNode next;

   public IntNode(int d, IntNode n) {
       data = d;
       next = n;
   }

   public IntNode getNext() {
       return next;
   }


   /// Override methods from Object

   @Override
   public boolean equals(Object obj) {
       throw new UnsupportedOperationException("Don't use .equals to compare nodes!");
   }

   @Override
   public IntNode clone() {
       try {
           return (IntNode)super.clone();
       } catch (CloneNotSupportedException e) {
           throw new AssertionError("IntNodes should be cloneable!");
       }
   }

   protected String originalToString() {
       return super.toString();
   }

   @Override
   public String toString() {
       String nextString = "null";
       if (next != null) nextString = next.originalToString();
       return super.toString() + "(" + data + "." + nextString + ")";
   }


   /// Print method that is used for testing
   /**
   * Convert a list to a string for debugging purposes.
   * The string is of the form [n1, n2, n3, ...].
   * if the list ends in a cycle then we have "..." followed by
   * the one-based index of the node we go back to.
   * @param head list t print, may be null
   * @return string representation of the whole list.
   */
   public static String listToString(IntNode head) {
       if (head == null) return "[]";
       IdentityHashMap<IntNode,Integer> m = new IdentityHashMap<>();
       StringBuilder sb = new StringBuilder("[");
       sb.append(head.data);
       m.put(head, 0);
       int n = 1;
       for (IntNode p = head.next; p != null; p = p.next) {
           Integer boxed = m.get(p);
           if (boxed != null) {
               sb.append(", ..." + (n-boxed));
               break;
           }
           m.put(p, n++);
           sb.append(", " + p.data);
       }
       sb.append("]");
       return sb.toString();
   }  
   public static IntNode exercise0() {
       return null; // []
   }

   public static IntNode exercise1() {
       IntNode x = new IntNode(42, null);
       return x; // TODO [42], retrun list with single value in it. Number 42
   }

   public static IntNode exercise2() {
       IntNode x = new IntNode(1, new IntNode(2, new IntNode(3, null)));
       return x; // TODO [1, 2, 3], return a list with the values 1,2, and 3. This will have 3 nodes
   }

   public static IntNode exercise3() {
       IntNode x = null;
       for(int i=1; i<=9; i++) {
           x = new IntNode(i, x);
       }
       return x; // TODO [9, ...1], create a cyclic list of nines with a single node pointing to itself.
   }

   public static IntNode exercise4() {
       IntNode one = new IntNode(1, null);
       IntNode two = new IntNode(2, one);
       one.next = two;

       IntNode x = new IntNode(4, new IntNode(3, two));
       return x; // TODO [4, 3, 2, 1, ...3], create a list that starts 4, 3, 2, 1 but then cycles back to the "2"node again making a loop.
   }

   public static IntNode exercise5(IntNode param) {
       IntNode first = param.getNext();
       IntNode s = first.getNext();
       s.data = 4;
       return param; // TODO: change second element to 4, change data in the second element of a list with at least two elements to "4"
   }

   public static IntNode exercise6(IntNode param) {
       IntNode first = param.getNext();
       IntNode s = first.getNext();
       first.next = s.next;
       return param; // TODO: remove second element, code should now remove(bypass) the second element of a list with at least two // elements
   }

   public static int exercise7(IntNode param) {
       int count = 0;
       while(param != null) {
           count++;
           param = param.getNext();
       }
       return count; // TODO: count number of nodes in list (use NORMAL loop), count up all nodes in the list passed in and rettrun the // count.
   }

   public static IntNode exercise8(IntNode param) {
       final IntNode dummy = new IntNode(999,null);
       IntNode last = dummy; // "last" node currently is the fake node.
       // TODO copy list by tacking on each element to the last node
       // of the result list. Use the NORMAL idiom
       while(param != null) {
           last = new IntNode(param.data, last);
           param = param.next;
       }
       return dummy.next;
   }

   public static IntNode exercise9(IntNode param, int v) {
       if(param == null) {
           return new IntNode(v, null);
       }
       IntNode last = param;
       while(last.getNext() != null) {
           last = last.getNext();
       }
       last.next = new IntNode(v, null);

       return param; // TODO: add v to the end of a non-empty list (in general!)
       // NB: We recommend using the FOLLOWER idiom
   }
}