JAVA HELP:

Modify LinkedListWithNode class, so the class describes a doubly-linked list, as described below:

1.) Change the inner Node class so that it includes 2 Node references, one that points left and the other right (there is already one that points right) you will need to declare a new instance variable and modify the 2 constructors:

Add methods to the inner Node class to get and set the left-pointing link:

Make changes to the add() and remove() methods of the outer class so that left-pointing links are made and broken properly:

2.) . Implement the Cloneable interface on your revised class (and define the clone() method):

3.) Add listSearch and listPart methods to your (doubly) LinkedListWithNode class so that your class has approximately the same functionality as the IntNode static methods of the same name. Method headings with documentation are shown below:

int listSearch (Object target)

- returns the index where the first occurrence of target is found, or -1 if not found

LinkedListWithNode listPart(int start, int end)

- returns a copy of the calling object that includes only the Nodes between and including those at the specified start and end positions.

- throws IllegalArgumentException if either start or end is out of range

4. Add the following methods to either implementation of the linked list class (IntNode or LinkedListWithNode). The method headings will vary depending which route you choose, so only descriptions are listed below:

- reverseCopy: returns a copy of a linked list, only backwards

- loseDupes: Takes a linked list that may contain duplicate values and returns a copy of the same list, but without duplicates. For example, if the original list looked like this:

// [3 ]->[5 ]->[3 ]->[4 ]->[3 ]->[3 ]->[7 ]->[5 ]->[6 ]->[4 ]

- the revised list would look like this:

// [3 ]->[5 ]->[4 ]->[7 ]->[6 ]

5. Add test code to the main method(s) of the class(es) you modify to demonstrate that your methods work.

---Class IntNode----- public class IntNode { private int data; private IntNode link; public IntNode(int initialData, IntNode initialLink) { data = initialData; link = initialLink; } public IntNode() { data = 0; link = null; } public int getData( ) { return data; } public IntNode getLink( ) { return link; } public void setData(int newData) { data = newData; } public void setLink(IntNode newLink) { link = newLink; } public static int listLength(IntNode head) { IntNode cursor; int answer; answer = 0; for (cursor = head; cursor != null; cursor = cursor.getLink()) answer++; return answer; } public static IntNode listSearch(IntNode head, int target) { IntNode cursor; for (cursor = head; cursor != null; cursor = cursor.getLink()) if (target == cursor.data) return cursor; return null; } public static IntNode listPosition(IntNode head, int position) { IntNode cursor; int i; if (position <= 0) throw new IllegalArgumentException("position is not positive"); cursor = head; for (i = 1; (i < position) && (cursor != null); i++) cursor = cursor.getLink(); return cursor; } public static IntNode listCopy(IntNode source) { IntNode copyHead; IntNode copyTail; if (source == null) return null; copyHead = new IntNode(source.data, null); copyTail = copyHead; while (source.getLink() != null) { source = source.getLink(); copyTail.addNodeAfter(source.data); copyTail = copyTail.getLink(); } return copyHead; } public void addNodeAfter(int item) { link = new IntNode(item, link); } public void removeNodeAfter( ) { link = link.link; } public static IntNode[ ] listCopyWithTail(IntNode source) { IntNode copyHead; IntNode copyTail; IntNode[ ] answer = new IntNode[2]; // Handle the special case of the empty list. if (source == null) return answer; // The answer has two null references . // Make the first node for the newly created list. copyHead = new IntNode(source.getData(), null); copyTail = copyHead; // Make the rest of the nodes for the newly created list. while (source.getLink() != null) { source = source.getLink(); copyTail.addNodeAfter(source.data); copyTail = copyTail.getLink(); } // Return the head and tail references. answer[0] = copyHead; answer[1] = copyTail; return answer; } public static IntNode[ ] listPart(IntNode start, IntNode end) { IntNode copyHead; IntNode copyTail; IntNode cursor; IntNode[ ] answer = new IntNode[2]; // Make the first node for the newly created list. Notice that this will // cause a NullPointerException if start is null. copyHead = new IntNode(start.data, null); copyTail = copyHead; cursor = start; // Make the rest of the nodes for the newly created list. while (cursor != end) { cursor = cursor.link; if (cursor == null) throw new IllegalArgumentException ("end node was not found on the list"); copyTail.addNodeAfter(cursor.data); copyTail = copyTail.link; } // Return the head and tail references answer[0] = copyHead; answer[1] = copyTail; return answer; } public static void printList(IntNode listStart, int position) { System.out.printf("%s %s %s %s ","[]listStart", " |", " |", " v"); for (IntNode cursor = listStart; cursor != null; cursor = cursor.getLink()) System.out.printf("[%2d|]-->", cursor.getData()); System.out.println("null"); if (position > 0) { int offset = (position-1) * 8 + 3; String format = "%" + offset + "s "; format = format+format+format+format; System.out.printf(format, "^", "|", "|", "cursor[]"); } } public static void main (String [] args) { java.util.Random rg = new java.util.Random(); IntNode head = new IntNode(rg.nextInt(100), null); boolean done = false; java.util.Scanner kb = new java.util.Scanner(System.in); String reply; while (!done) { // build & print initial list for testing for (int x=0; x<8; x++) { int tmp = rg.nextInt(100); head.addNodeAfter(tmp); } System.out.println("initial list:"); printList(head, 0); // No provision for adding node before head in instance methods, // so doing so with client code: System.out.print("Adding 2 nodes at front of list; "); head=new IntNode(rg.nextInt(100), head); head=new IntNode(rg.nextInt(100), head); System.out.println("cursor indicates where head used to be:"); printList(head, 3); // Removing head node can't be done using instance method with // this implementation, so trying it in client code: System.out.println("Removing first node:"); head = head.getLink(); printList(head, 0); // Testing static methods: listLength System.out.println("length of list is: " + IntNode.listLength(head)); // listSearch int target = rg.nextInt(100); System.out.println("Testing search method; searching for " + target); IntNode cursor = IntNode.listSearch(head, target); if (cursor == null) System.out.println("target value not in list"); else { System.out.println("target found; printing list from target to end"); printList(cursor, 0); } // listPosition int position = rg.nextInt(IntNode.listLength(head)) + 1; cursor = IntNode.listPosition(head, position); System.out.println(cursor.getData() + " occurs at position " + position); printList(head, position); // adding new node in midlist; first, ensure that we're not // at the head node: if (position == 1) { position++; cursor = IntNode.listPosition(head, position); } System.out.println("Adding 0 after " + cursor.getData()); cursor.addNodeAfter(0); printList(head, position+1); // listCopy (from head & also from cursor) System.out.println("Copying big list"); IntNode copy = IntNode.listCopy(head); printList(copy, 0); System.out.println("Copying list that starts at " + cursor.getData()); copy = IntNode.listCopy(cursor); printList(copy, 0); // listCopyWithTail System.out.println("Testing listCopyWithTail"); IntNode[]nodes = IntNode.listCopyWithTail(head); System.out.println("Data at head of new list: " + nodes[0].getData()); System.out.println("Data at tail of new list: " + nodes[1].getData()); System.out.println("Copied list; cursor shows position of tail node"); printList(nodes[0], IntNode.listLength(nodes[0])); // listPart System.out.println("Testing listPart"); boolean badParams = true; while (badParams) { // generate semi-random node for start position = rg.nextInt(IntNode.listLength(head)) + 1; if (position == 1) position++; IntNode ch = IntNode.listPosition(head, position); System.out.println("List showing cursor at 1st node to be copied:"); printList(head, position); // generate semi-random node for end position = rg.nextInt(IntNode.listLength(head)) + 1; if (position == IntNode.listLength(head)) position--; IntNode ct = IntNode.listPosition(head, position); System.out.println("List showing cursor at last node to be copied:"); printList(head, position); // here's where the badParams might have happened - we didn't // check to see if ch was before ct in the list; so watch for // exception try { nodes = IntNode.listPart(ch, ct); badParams = false; } catch (IllegalArgumentException e) { System.out.println("head must come before tail!"); } } printList(nodes[0], IntNode.listLength(nodes[0])); System.out.print("Run tests again? (y/n): "); reply = kb.nextLine(); if(reply.equalsIgnoreCase("n")) { done = true; } else { // We're starting over, so wipe out list & start fresh: head = null; head = new IntNode(rg.nextInt(100), null); } } } } 

---Class LinkedListWithNode----- 

public class LinkedListWithNode { // reference to the head node. private Node head; private int listCount; // LinkedList constructor public LinkedListWithNode() { // this is an empty list, so the reference to the head node // is set to a new node with no data head = new Node(null); listCount = 0; } public void add(Object data) { // post: appends the specified element to the end of this list. Node temp = new Node(data); Node current = head; // starting at the head node, crawl to the end of the list while(current.getNext() != null) { current = current.getNext(); } // the last node's "next" reference set to our new node current.setNext(temp); listCount++;// increment the number of elements variable } public void add(Object data, int index) { // post: inserts the specified element at the specified position in this list. Node temp = new Node(data); Node current = head; // crawl to the requested index or the last element in the list, // whichever comes first for(int i = 1; i < index && current.getNext() != null; i++) { current = current.getNext(); } // set the new node's next-node reference to this node's next-node reference temp.setNext(current.getNext()); // now set this node's next-node reference to the new node current.setNext(temp); listCount++;// increment the number of elements variable } public Object get(int index) { // post: returns the element at the specified position in this list. // index must be 1 or higher if(index <= 0) return null; Node current = head.getNext(); for(int i = 1; i < index; i++) { if(current.getNext() == null) return null; current = current.getNext(); } return current.getData(); } public boolean remove(int index) { // post: removes the element at the specified position in this list. // if the index is out of range, exit if(index < 1 || index > size()) return false; Node current = head; for(int i = 1; i < index; i++) { if(current.getNext() == null) return false; current = current.getNext(); } current.setNext(current.getNext().getNext()); listCount--; // decrement the number of elements variable return true; } public int size() { // post: returns the number of elements in this list. return listCount; } public String toString() { Node current = head.getNext(); String output = ""; while(current != null) { output += "[" + current.getData().toString() + "]"; current = current.getNext(); } return output; } private class Node { // reference to the next node in the chain, // or null if there isn't one. Node next; // data carried by this node. // could be of any type you need. Object data; // Node constructor public Node(Object _data) { next = null; data = _data; } // another Node constructor if we want to // specify the node to point to. public Node(Object _data, Node _next) { next = _next; data = _data; } public Object getData() { return data; } public void setData(Object _data) { data = _data; } public Node getNext() { return next; } public void setNext(Node _next) { next = _next; } } public static void main(String[] args) { LinkedListWithNode list = new LinkedListWithNode(); String data; for (int x=0; x<8; x++){ data = ""+x; list.add(data); } System.out.println("Original list:"); System.out.println(list); int index = ((int)(Math.random()*10))%list.size() + 1; System.out.println("Getting item at index " + index); System.out.println(list.get(index)+ " retrieved"); System.out.println("Removing item at index 4"); list.remove(4); System.out.println("Revised list:"); System.out.println(list); System.out.println("Removing first item:"); list.remove(1); System.out.println("Revised list:"); System.out.println(list); System.out.println("Removing last item"); list.remove(list.size()); System.out.println("Revised list:"); System.out.println(list); index = ((int)(Math.random()*1000))%list.size() + 1; System.out.println("Adding new item at position " + index); list.add(""+Math.random(), index); System.out.println("Revised list:"); System.out.println(list); } }