Stephen O'C Stephen O'C - 24 days ago 7
Java Question

Java sorted linked list printing twice

I am writing a program that will take in a set of data, process it and sort it in a linked list. My issue is that when I look at the output, when my (myList.retrieve(0, 20)); method is called the first time, it prints double what it should. The second time after deleting 2 elements, the output is correct.

public class Lab9Tester {
public static void main(String args[]){
int testData[] = {5, 2, 7, 8, 3, 6, 10, 2, 6};
int numberOfElementsDeleted = 0;
SortedListOfInt myList = new SortedListOfInt();
for (int i = 0; i < testData.length; i++){
myList.addElement(testData[i]);
}
System.out.println("The values in the sorted list are given below");
System.out.println(myList.retrieve(0, 20));
System.out.println("The values in the sorted list between 4 and 7 are given below");
System.out.println(myList.retrieve(4, 7));
numberOfElementsDeleted = myList.deleteElement(6);
System.out.println("Number of deleted elements is " + numberOfElementsDeleted);
System.out.println("The values in the sorted list after deleting all elements with value 6 are given below");
System.out.println(myList.retrieve(0, 20));

}
}


My test program, which when run I expect the ouput:

The values in the sorted list are given below
2 2 3 5 6 6 7 8 10
The values in the sorted list between 4 and 7 are given below
5 6 6 7
Number of deleted elements is 2
The values in the sorted list after deleting all elements with value 6 are given below
2 2 3 5 7 8 10


However the first line of values is printed twice as

2 2 3 5 6 6 7 8 10 2 2 3 5 6 6 7 8 10


My other classes are as follows:

public class SortedListOfInt {

ListGeneral myList = new ListGeneral();

private boolean needToRestart = true;
private boolean restartFlag = false;

public void addElement(int x){

if(myList.listIsEmpty())
{
myList.addAfterCurrent(x);
return;
}


if (myList.endOfList())
{
myList.addBeforeCurrent(x);
myList.restart();
return;
}


if (myList.currentValue() != null){
int currentValue = (int) (myList.currentValue());
if(currentValue >= x)
{
myList.addBeforeCurrent(x);
myList.restart();
}
else if(currentValue < x)
{
myList.getNextNode();
addElement(x);
}
}
}


public String retrieve(int lowerLimit, int upperLimit)
{

if(myList.listIsEmpty())
{
return "";
}

if(myList.endOfList() && needToRestart)
{
myList.restart();
needToRestart = false;
return "" + retrieve(lowerLimit, upperLimit);
}
if(myList.endOfList())
{
needToRestart = true;
return "";
}

int currentValue = (int) (myList.currentValue());

if(currentValue >= lowerLimit && currentValue <= upperLimit)
{

String result =currentValue + " " ;
myList.getNextNode();
return result + retrieve(lowerLimit,upperLimit);
}
else
{
myList.getNextNode();
return retrieve(lowerLimit,upperLimit);
}
}

public int deleteElement(int x)
{
repointToStart();

int currentValue;
if(myList.endOfList())
{
restartFlag = false;
return 0;
}
else
{
currentValue = (int) myList.currentValue();
if(currentValue == x)
{
myList.removeCurrent();
return deleteElement(x) + 1;
}
else
{
myList.getNextNode();
return deleteElement(x);
}
}

}

private void repointToStart()
{
if(restartFlag == false)
{
myList.restart();
restartFlag = true;
}
}
}


Given by the professor:

public class ListGeneral {

protected Node firstNode; // firstNode can be used by this
// class and any of its subclass.
private Node currentNode, previousNode; // These are usable only
// within this class.

public ListGeneral(){ // Constructor creates an
// empty list.
currentNode = null;
firstNode = null;
previousNode = null;
}

/*
* The method addAfterCurrent adds a new node with value x
* after the current node.
*/
public void addAfterCurrent(Object x){
if (firstNode == null){
firstNode = new Node(x, null);
currentNode = firstNode;
}
else{
Node newNode = new Node(x, currentNode.getNext());
currentNode.setNext(newNode);
previousNode = currentNode;
currentNode = newNode;
}
}

/*
* The method addBeforeCurrent adds a new node with value x
* before the current node.
*/
public void addBeforeCurrent(Object x){
if (firstNode == null){
firstNode = new Node(x, null);
currentNode = firstNode;
}
else {
Node newNode = new Node(x, currentNode);
if (previousNode != null) {
previousNode.setNext(newNode);
}
else{
firstNode = newNode;
}
currentNode = newNode;
}
}

/*
* removeCurrent() deletes the current node. This is defined
* only if the list is not empty.
*/
public void removeCurrent(){
Node temp;
if (listIsEmpty() || endOfList()) return;
temp = currentNode.getNext();
/*
* if previousNode is null, firstNode is currentNode.
*/

if (previousNode == null) {
firstNode = temp;
}
else {
previousNode.setNext(temp);
}
currentNode = currentNode.getNext();
}

/*
* listIsEmpty() is true if list is empty.
* current() returns the current node.
* restart() makes the the first node the current node.
*/


public boolean listIsEmpty(){
return firstNode == null;
}

public Object currentValue(){
return currentNode.getValue();
}

public void restart(){
currentNode = firstNode;
previousNode = null;
}

/* endOfList() is true if current is not pointing to
* any node.
*/

public boolean endOfList(){
return currentNode == null;
}

/* getNextNode makes the next node the current node.
* The method returns true if the operation was successful
* otherwise it returns false.
*/
public boolean getNextNode(){
if (currentNode == null) {
return false;
}
else {
previousNode = currentNode;
currentNode = currentNode.getNext();
return true;
}
}
/*
* method toString() returns the result of invoking toString()
* on all successive elements of the list.
*/

public String toString(){
String s = "";
for(restart(); !endOfList(); getNextNode()){
s += currentValue() + "\n";
}
return s;
}
}


As well as given:

public class Node {
private Object value; // self-referential link.
private Node next;

public Node(Object value, Node nextNode) // The constructor inserts the
{ // arguments in the new object.
this.value = value;
this.next = nextNode;
}
public Object getValue(){
return value;
}

public Node getNext(){
return next;
}

public void setValue(Object value){
this.value = value;
}

public void setNext(Node next){
this.next = next;
}
}

Answer

The problem is you are setting needToRestart = true in the SortedListofInt class.So when you do the initial retrieve it calls it twice but sets the needToRestart = false. Next time around when you call the retrieve it prints only once. Setting the needToRestart = false initially is working for me and printing out the correct output.

This is working for me

public class SortedListOfInt {

ListGeneral myList = new ListGeneral();

private boolean needToRestart = false;
private boolean restartFlag = false; //the only change

...

}