Programming Activity 14-2 Guidance ================================== 

/* Node * Anderson, Franceschi */ public class Node { /** reference to the next node in the list **/ private Node nextNode; /** the data object held by this node **/ private int data; /** * * construct a new node with the given Object as data * **/ public Node( int i ) { data = i; } /** * * construct a new node with the given Object as data * and references to the next and previous nodes. * **/ public Node( int i, Node next ) { data = i; nextNode = next; } /** * * set the reference to the next node * **/ public void setNext( Node n ) { nextNode = n; } /** * * return the reference to the next node * @return reference to the next node, or null if there is no next node * **/ public Node getNext( ) { return nextNode; } /** * * set the data object held by this node * **/ public void setData( int i ) { data = i; } /** * * get the data object held by this node * **/ public int getData( ) { return data; } } // end node class ============================================================= /* AbstractList * Anderson, Franceschi */ public abstract class AbstractList { /* INSTANCE VARIABLES */ /** * a Visualizer instance is maintained here so that the student * can call it from the child class without worrying about the * implementation of the Visualizer. This is intended to mimic * the use of a Graphic object in the Swing or AWT package. **/ protected Visualizer v; protected int numberNodes; protected String traversal; // holds current traversal of the list /* CONSTRUCTORS */ /** * instantiate with the given GUI width and height for the Visualizer. * **/ public AbstractList( int width, int height ) { v = new Visualizer( width, height ); numberNodes = 0; } /* METHODS STUDENTS MUST OVERRIDE */ /** * * insert an object in to the list. * **/ public abstract void insert( int i ); /** * * delete a node from the list based on reference. * * @ return true if the node was deleted, false otherwise **/ /** * * delete a node from the list based on data. * * @return true if the node was deleted, false otherwise * **/ public abstract boolean delete( int i ); /** * * returns the number of Nodes in the list. * **/ public abstract int count( ); /** * * walks the list and displays the data it contains. * **/ public abstract void traverse( ); /** * * removes all nodes from the list. * **/ public abstract void clear( ); /* METHODS FOR CONTROLLING VISUALIZER */ /** * * sets the width and height in pixels for the visualizer. * **/ public void setSize( int width, int height ) { v.setSize( width, height ); v.validate( ); } /** * * returns a reference to the Visualizer being used by this object. * Any object calling this method is on its honor to not modify * the Visualizer. * **/ public Visualizer getVisualizer( ) { return v; } /** * * simple delay routine that makes the thread sleep for the given * number of milliseconds. useful for when a node is being * highlighted by the visualizer. * **/ public void delay( int milliseconds ) { try { Thread.sleep( milliseconds ); } catch ( Exception e ) { System.out.println(" e: "+e ); } } /* * * the following are wrapper methods to make calling the visualizer * a little more convienient. see the wrapped Visualizer methods * for more information. * */ /* public void drawList( Node headNode ) { v.drawList( headNode ); } public void drawList( Node headNode, int highlight ) { v.drawList( headNode, highlight ); } public void drawList( Node headNode, Node highlight ) { v.drawList( headNode, highlight ); } public void drawList( Node headNode, int target, int action ) { v.drawList( headNode, target, action ); } public void drawList( Node headNode, Node target, int action ) { v.drawList( headNode, target, action ); } */ public String getTraversal( ) { return traversal; } } // end abstract list

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

The bold areas where it says" student code starts here" and Student code ends here" is where you need to put your code.

/* LinkList * Anderson, Franceschi */

/** * this class is a concrete implementation of the AbstractList. public class LinkList extends AbstractList { private Node head = null;

public LinkList() { super(500, 400); v.drawList(head); }

public LinkList(Node head) { super(500, 400); // set size for visualizer // set up the list head = head;

animate(head); }

public void insert(int i) { // ***** Student writes the body of this method *****

// code the insert method of a linked list of ints // the int to insert in the linked list is i

// we call the animate method inside the body of this method // as you traverse the list looking for the place to insert, // call animate as follows:

// animate(head, current); // where head is the instance variable head of the linked list // current is the node that you are visiting

// you can start coding now

// in order to improve the animation (this is optional): // just before inserting, i.e. connecting the nodes, // make the call

// animate(head, previous, Visualizer.ACTION_INSERT_AFTER);

// where head is the instance variable head of the linked list // previous is the node (not null) after which to insert

// if you are inserting at the beginning of the list, // just before inserting, make the call

// animate(head, head, Visualizer.ACTION_INSERT_BEFORE);

// where head is the instance variable head of the linked list // // Part 1 student code starts here:

// Part 1 student code ends here.

numberNodes++; // call animate again to show the status of the list animate(head); }

public boolean delete(int i) { // ***** Student writes the body of this method *****

// code the delete method of a linked list of ints // the int to delete in the linked list is i // if deletion is successful, return true // otherwise, return false

// we call the animate method inside the body of this method // as you traverse the list looking for the node to delete, // call animate as follows:

// animate(head, current);

// where head is the instance variable head of the linked list // current is the node that you are visiting

// you can start coding now

// in order to improve the animation (this is optional): // just before deleting, i.e. connecting the nodes, // make the call

// animate(head, current, Visualizer.ACTION_DELETE);

// where head is the instance variable head of the linked list // current is the node that you are deleting // // Part 2 student code starts here:

// Part 2 student code ends here.

// At this point, the item has been deleted. // Decrement the number of nodes: numberNodes--; // Call animate again to show the status of the list: animate(head); return true; }

public int count() { int n = 0; Node current = head; while (current != null) { animate(head, current); n++; current = current.getNext(); } return n; }

public void traverse() { traversal = ""; Node current = head; while (current != null) { animate(head, current); traversal += (current.getData() + " "); current = current.getNext(); } v.drawList(head); }

public void clear() { head = null; v.drawList(head); }

public void animate(Node h, Node nd) { v.drawList(h, nd); delay(1000); }

public void animate(Node h) { v.drawList(h); }

public void animate(Node h, Node nd, int mode) { v.drawList(h, nd, mode); delay(1000); } }

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

The Output:

Programming Activity 14-2 Guidance 1. The 1ist you work with is made up of items of the Node class. You must look at the framework's Node.Java file to understand how to use Node objects Part 1 starter code Here is code to get you started It includes comments showing where you need to put your own code: // Create node to insert: Node nodenew Node (i): if (head null) List is empty, so node is the new head: headnode: numberNodes+t: animate (head) return Node current head: Node previous nuil: /I Traverse 1ist to find insert point: 1 Insert between previous and current: Case 1: insert at the beginning: 1/else Case 2: insert in the middle or at the end of the 1ist Part 2 starter code Here is code to get you stared on part 2. It includes comnents showing where you need to put your own code: Node current-head: Node previousnull: Look for node to delete: are supposed to insert, which was passed in to the insert function as the int parameter "i". To get the value of the current node you must use current's getData ) function. As long as the current value is less than or equal to i, you must keep looking further through the list to find the insert point. In order to do this, you must change the values of previous and current within your traversal loop. The first thing you must do inside your while loop is to call the framework animate method passing it head and current (in that order) . Next, you wil1 change previous to be the value of current. Then you will change current to refer to the next item in the list. You get the next item by using current's getNext ) function. That is all you do in your loop. If your loop is correct, it will simply look through the list until it finds the insertion point. The insertion point will be between the values of previous and current. Your traversal loop does not do the insert. It just looks through the list and ends with previous and current bounding the insertion point. Next you see the comment: // Insert between previous and current: // Case 1: insert at the beginning: You need an if statement to detect case 1. When will it be case 1? What is the condition that implies that you are inserting at the beginning of the 1ist? Note that besides previous and current, you also have access to a variable called "head" that points to (refers to) the head of the list Keep in mind that the list is an ordered list. It starts at head (with the smallest value) and then the other values follow in order from smaller to larger until you reach the end of the 1list, which is indicated by a null link from the last item. You wi1l be inserting at the beginning of the list when current is equal to head (current-= head) . What do you do inside this "if" block? 1rst, YOu WilI call animate as IolloWS: animate (head, head, Visualizer.ACTION_INSERT BEFORE) Then you will insert the new node (the object called "node") between previous and head. You need to change node's link to point to the current head of the list then you need to change head to point to node. You do not need to do anything to previous because it should already be null in this case. Next you see the comment: / else Case 2: insert in the middle or at the end of the 1list That means case 2 must be an "else" block following your case 1 "if" block Remember that if you have an if statement whose body returns false, there is no need for the code that follows that if 3tatement to be wrapped in an else block. It is better to do like this: if (some condition) some code: some more code; turn false: I/ or true // no need for else here. // Just start the code that can only happen if the "if" was not taken. next statement Now back to discussing the starter code. There is another animate call here (see starter code) Then we need to consider the next comment: // Delete node: // Case 1: Its the head node: How do we know it is the head node we need to delete?This should be very obvious. When current head. In this case, we are deleting the head node from the list. The way this is done is to change the list's head pointer to point to the next node after the current head. Once that is done, no one will see the old head again because you have to start at head and it has been changed. So, this effectively deletes the old heacd from the list. Do not do a return here because the starter comments indicate that the following code needs to be the else block for this code: // else Case 2: Its not the head node: If it is not the head node we are deleting, then it is some other node in the list (pointed to by current) . delete it, you just need to move the highway around it so it is bypassed. That means you will change previous' next node link to be the next node link of current. This will cause current (the deleted node) to no longer be on the highway, so to speak. Anyone going through the list after this will come to previous and then they will go to the node after current. The ending brace of this else block ends your part 2 code Example Programming Activity 14-2 Output Start of program Linked List Visualizer Node Dala: insert delete traverse count clear After inserting 10, 2, and 5: Linked List Visualizer Node Data: 10 insert delete traverse count clear insert called with 10 as dala nsert called with 2 as data nsert called with 5 as dala After traversing the list: Linked List Visualizer Node Data: 10 insert delete traverse count clear insert called with 10 as dala insert called with 2 as data nsert called with 5 as dala raversing the list: 2 5 10 After resizing window and inserting 7: d Linked List Visualizer Node Data: 10 insert delete traverse count clear nsert cal led with 10 as data nsert called with 2 as data nsert called with 5 as data raversing the list 2 5 10 nsert called with 7 as data After deleting 5: Linked Lict Vitualizer Node Data: 10 insert delete traverse count clear nsert called with 5 as data aversing the list 2 5 10 nsert called wih 7 as data called wth 5: node deleted After inserting a second 7: Linked List Vicualizer Node Data: 10 insert delete traverse count clear nsert called with 5 as data aversing the list 2 5 10 nsert called wih 7 as data called wth 5: node deleted nsed called with 7 as data After counting number of nodes: Linked Lict Vitualizer Node Data: 10 insert delete traverse count clear nsert cal led with 7 as data e called with 5. node deleted nsert called win 7 as data o nodes d bunt called: number of After clearing Linked Lict Vitualizer Node Data: insert delete traverse count clear nsert cal led with 7 as data e called wth 5. node d9leled nsert called win 7 as data ount called number ofnodes d le ar list called Programming Activity 14-2 Guidance 1. The 1ist you work with is made up of items of the Node class. You must look at the framework's Node.Java file to understand how to use Node objects Part 1 starter code Here is code to get you started It includes comments showing where you need to put your own code: // Create node to insert: Node nodenew Node (i): if (head null) List is empty, so node is the new head: headnode: numberNodes+t: animate (head) return Node current head: Node previous nuil: /I Traverse 1ist to find insert point: 1 Insert between previous and current: Case 1: insert at the beginning: 1/else Case 2: insert in the middle or at the end of the 1ist Part 2 starter code Here is code to get you stared on part 2. It includes comnents showing where you need to put your own code: Node current-head: Node previousnull: Look for node to delete: are supposed to insert, which was passed in to the insert function as the int parameter "i". To get the value of the current node you must use current's getData ) function. As long as the current value is less than or equal to i, you must keep looking further through the list to find the insert point. In order to do this, you must change the values of previous and current within your traversal loop. The first thing you must do inside your while loop is to call the framework animate method passing it head and current (in that order) . Next, you wil1 change previous to be the value of current. Then you will change current to refer to the next item in the list. You get the next item by using current's getNext ) function. That is all you do in your loop. If your loop is correct, it will simply look through the list until it finds the insertion point. The insertion point will be between the values of previous and current. Your traversal loop does not do the insert. It just looks through the list and ends with previous and current bounding the insertion point. Next you see the comment: // Insert between previous and current: // Case 1: insert at the beginning: You need an if statement to detect case 1. When will it be case 1? What is the condition that implies that you are inserting at the beginning of the 1ist? Note that besides previous and current, you also have access to a variable called "head" that points to (refers to) the head of the list Keep in mind that the list is an ordered list. It starts at head (with the smallest value) and then the other values follow in order from smaller to larger until you reach the end of the 1list, which is indicated by a null link from the last item. You wi1l be inserting at the beginning of the list when current is equal to head (current-= head) . What do you do inside this "if" block? 1rst, YOu WilI call animate as IolloWS: animate (head, head, Visualizer.ACTION_INSERT BEFORE) Then you will insert the new node (the object called "node") between previous and head. You need to change node's link to point to the current head of the list then you need to change head to point to node. You do not need to do anything to previous because it should already be null in this case. Next you see the comment: / else Case 2: insert in the middle or at the end of the 1list That means case 2 must be an "else" block following your case 1 "if" block Remember that if you have an if statement whose body returns false, there is no need for the code that follows that if 3tatement to be wrapped in an else block. It is better to do like this: if (some condition) some code: some more code; turn false: I/ or true // no need for else here. // Just start the code that can only happen if the "if" was not taken. next statement Now back to discussing the starter code. There is another animate call here (see starter code) Then we need to consider the next comment: // Delete node: // Case 1: Its the head node: How do we know it is the head node we need to delete?This should be very obvious. When current head. In this case, we are deleting the head node from the list. The way this is done is to change the list's head pointer to point to the next node after the current head. Once that is done, no one will see the old head again because you have to start at head and it has been changed. So, this effectively deletes the old heacd from the list. Do not do a return here because the starter comments indicate that the following code needs to be the else block for this code: // else Case 2: Its not the head node: If it is not the head node we are deleting, then it is some other node in the list (pointed to by current) . delete it, you just need to move the highway around it so it is bypassed. That means you will change previous' next node link to be the next node link of current. This will cause current (the deleted node) to no longer be on the highway, so to speak. Anyone going through the list after this will come to previous and then they will go to the node after current. The ending brace of this else block ends your part 2 code Example Programming Activity 14-2 Output Start of program Linked List Visualizer Node Dala: insert delete traverse count clear After inserting 10, 2, and 5: Linked List Visualizer Node Data: 10 insert delete traverse count clear insert called with 10 as dala nsert called with 2 as data nsert called with 5 as dala After traversing the list: Linked List Visualizer Node Data: 10 insert delete traverse count clear insert called with 10 as dala insert called with 2 as data nsert called with 5 as dala raversing the list: 2 5 10 After resizing window and inserting 7: d Linked List Visualizer Node Data: 10 insert delete traverse count clear nsert cal led with 10 as data nsert called with 2 as data nsert called with 5 as data raversing the list 2 5 10 nsert called with 7 as data After deleting 5: Linked Lict Vitualizer Node Data: 10 insert delete traverse count clear nsert called with 5 as data aversing the list 2 5 10 nsert called wih 7 as data called wth 5: node deleted After inserting a second 7: Linked List Vicualizer Node Data: 10 insert delete traverse count clear nsert called with 5 as data aversing the list 2 5 10 nsert called wih 7 as data called wth 5: node deleted nsed called with 7 as data After counting number of nodes: Linked Lict Vitualizer Node Data: 10 insert delete traverse count clear nsert cal led with 7 as data e called with 5. node deleted nsert called win 7 as data o nodes d bunt called: number of After clearing Linked Lict Vitualizer Node Data: insert delete traverse count clear nsert cal led with 7 as data e called wth 5. node d9leled nsert called win 7 as data ount called number ofnodes d le ar list called