The following code compiles, but in the main method I cannot iterate backwards t
ID: 3607171 • Letter: T
Question
The following code compiles, but in the main method I cannot iterate backwards through the list. I've highlighted the segment of code that isn't performing the desired result. As mentioned in the comments, I need myDogList to print out in reverse order.
------------------------------------------------------------------------------------------
public class ListRunner {
public static void main(String[] args) {
Dog fifi = new Dog("Fifi", 12, 8);
Dog butch = new Dog("Butch", 10, 10);
Dog leonard = new Dog("Leonard", 22, 13);
Dog spot = new Dog("Spot", 17, 9);
LinkedList myDogList = new LinkedList();
System.out.println();
myDogList.add(fifi);
System.out.println(myDogList);
System.out.println();
myDogList.add(butch);
myDogList.add(leonard);
myDogList.add(spot);
System.out.println(myDogList);
System.out.println();
Dog jack = new Dog("Jack", 18, 18);
myDogList.add(jack,1);
System.out.println(myDogList);
System.out.println();
// the following lines build Iterators, and provide an example
// of how you would use an Iterator to step through this data
// structure
Iterator iter1 = myDogList.getIterator();
Iterator iter2 = myDogList.getIterator();
System.out.println("Iterating using Iterators!!!");
while (iter1.hasNext()) {
Dog foo = iter1.next();
System.out.println(foo);
}
System.out.println();
// In a doubly-linked list, an iterator can move either forward or backward,
// so this should print the list out in reverse order if you've correctly
// implemented everything
System.out.println("Iterating backwards using Iterators!!!");
iter2.setToEnd();
while (iter2.hasPrior()) {
Dog foo = iter2.prior();
System.out.println(foo);
}
}// end main
} // end class ListRunner
------------------------------------------------------------------------------------------
public class LinkedList {
Node itsFirstNode;
Node itsLastNode;
private int size;
public LinkedList() {
itsFirstNode = null;
itsLastNode = null;
size = 0;
}
public Iterator getIterator() {
return new Iterator(this);
}
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element) {
Node node = new Node(element);
if (itsFirstNode == null) {
itsFirstNode = node;
itsLastNode = node;
}
else {
itsLastNode.setNextNode(node);
node.setPriorNode(itsLastNode);//prior node set from new node to last node
itsLastNode = node;
}
size++;
}
// THIS WILL NEED TO BE MODIFIED FOR DOUBLY-LINKED LIST
public void add(T element, int index) {
int counter = 0;
Node newNode = new Node(element);
Node current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index - 1 )
break;
current = current.getNextNode();
counter++;
}
newNode.setNextNode(current.getNextNode());
Node temp=current.getNextNode();//temp node is next node of current node
temp.setPriorNode(newNode);
current.setNextNode(newNode);
newNode.setPriorNode(current);
size++;
}
public T get(int index) {
int counter = 0;
Node current = itsFirstNode;
while (current.getNextNode() != null ) {
if (counter == index)
break;
current = current.getNextNode();
counter++;
}
return current.getData();
}
// returns true if element is in the list, false if not
public boolean contains(T element) {
Node head = itsFirstNode;
boolean res = false;
if (itsFirstNode == null)
return res;
else {
while (head != null) {
if(head.getData() == element){
res = true;
break;
}
head.setNextNode(head.getNextNode());
}
}
return res;
}
// returns the index of the element if it is in the list, -1 if not found
public int indexOf(T element) {
Node head = itsFirstNode;
int index = 0;
if(itsFirstNode == null)
return -1;
else {
while (head != null) {
if (head.getData() == element) {
break;
}
head.setNextNode(head.getNextNode());
index++;
}
}
return index;
}
// returns an Iterator at the location of the element if it is in the list
// returns the null reference if the element is not found
/* we cannot get java iterator to an user defined object unless implementing iterable interface*/
/* therefore i changed return type to Node and return reference to current node*/
public Node iteratorAt(T element) {
Node head = itsFirstNode;
if (itsFirstNode == null)
return null;
else {
while (head != null) {
if (head.getData() == element) {
break;
}
head.setNextNode(head.getNextNode());
}
}
return head;
}
public String toString() {
String returnVal = "";
Node current = itsFirstNode;
if (size != 0 ) {
while (current.getNextNode() != null ) {
returnVal += current.toString();
returnVal += " ";
current = current.getNextNode();
}
returnVal += current.toString();
}
return returnVal;
} // end toString
class Node {
private T data;
private Node itsNext;
private Node itsPrior;
public Node(T data) {
itsNext = null;
itsPrior = null;
this.data = data;
}
public T getData() {
return this.data;
}
public Node getNextNode() {
return itsNext;
}
public Node getPriorNode() {
return itsPrior;
}
public void setNextNode(Node next) {
itsNext = next;
}
public void setPriorNode(Node prior) {
itsPrior=prior;
}
public String toString() {
return data.toString();
}
} // end of Node
} // end LinkedList class
------------------------------------------------------------------------------------------
public class Iterator {
private LinkedList myList;
private LinkedList.Node myCurrentNode;
public Iterator(LinkedList list) {
myList = list;
myCurrentNode = myList.itsFirstNode;
}
// return true if there is a "next" element, otherwise returns false
public boolean hasNext() {
if (myCurrentNode != null)
return true;
return false;
}
// return true if there is a "prior" element, otherwise returns false
public boolean hasPrior() {
if (myCurrentNode.getNextNode() != null)
return true;
return false;
}
// returns the "next" node (really the current one) and
// moves the Iterator forward by one node
public T next() {
T data = myCurrentNode.getData();
myCurrentNode = myCurrentNode.getNextNode();
return data;
}
// returns the "prior" node (really the current one) and
// moves the Iterator backward by one node
public T prior() {
T data = myCurrentNode.getData();
myCurrentNode = myCurrentNode.getPriorNode();
return data;
}
// Sets this iterator to point to the last Node in the list
public void setToEnd() {
while (myCurrentNode.getNextNode() != null)
myCurrentNode = myCurrentNode.getNextNode();
}
} //end Iterator class
------------------------------------------------------------------------------------------
public class Dog {
private int weight;
private int heightAtShoulder;
private String name;
public Dog (String name, int w, int h) {
System.out.println("Just Entered Dog constructor");
this.name = name;
this.weight = w;
this.heightAtShoulder = h;
System.out.println("Leaving Dog constructor");
}
public String getName() {return this.name;}
public int getHeight() {return this.heightAtShoulder;}
public int getWeight() {return this.weight;}
public void bark() {System.out.println("woof");}
public String toString() {
return "Dog: " + name + " , height: " + heightAtShoulder +
" weight: " + weight;
}
@Override
public boolean equals(Object o) {
if (o instanceof Dog) {
//now we can do checks
Dog tempDogRef = (Dog)(o);
if (tempDogRef.getName().equals(this.name) &&
tempDogRef.getHeight() == this.heightAtShoulder &&
tempDogRef.getWeight() == this.weight)
return true;
}
return false;
}
} // end class Dog
Explanation / Answer
iter2.setToEnd();
while (iter2.hasPrior()) {
Dog foo = iter2.prior();
System.out.println(foo);
}
This is the code use by you print your list in reverse order.
The above code is correct and it will print your doglist in reverse order but the I mistake i observed is as follows.
initially you are setting the your iteraor to the end of the list with the statement iter2.setToEnd(); it is fine.
After this you have written a while loop to print the element one by one in your list starting from last node to first node.
but if you the loop invariant it is based on the condition iter2.hasPrior(). But if you look at the implementation of hasPrior() method in your Iterator class it is as follows.
public boolean hasPrior() {
if (myCurrentNode.getNextNode() != null)
return true;
return false;
}
if you observe condition in if it is checking for the next node but conceptually it has to check for previous node as we are checking whether previous node is present or not. It can be solved by replacing the if condition in above method as follows
if (myCurrentNode.getPriorNode() != null)
by replacing now it always return true if previous node is present and prints the list in reverse order.
Reason for failure: You have already set your iterator to end of list and in while loop you are checking condiion hasprior(), but this method will return false as this method will always check for next is present or not asper the code wriitten by you and why it will return false is as we have already traversed to the end of the list there wont any nodes present in the list.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.