Java remove an element from linked list recursion

Question

For this assignment given to me, I am supposed to move through a linked list of size 1,000,000 iteratively and recursively. I have the iterative part down but I am confused on the recursive part. I have the concept down but I have told my teacher that I cannot recursively do it because I will inevitably get a stack overflow error. He says I should not be getting that problem but I am totally stuck. Any tips would be great as I have no idea what I am doing wrong.

public static void main(String[] args) {

    System.out.println("Please enter how many random numbers you want to generate: ");
    Scanner prompt = new Scanner(System.in);
    int amount = prompt.nextInt();

    Random rnd = new Random();
    System.out.println("Creating list...");
    for (int i = 0; i < amount; i++) {
        randomList.add(rnd.nextInt(100));
    }
    System.out.println("Going through list...");
    iterateNumbers();

    long startTimeRec = System.nanoTime();
    recursiveNumbers(randomList);
    long elapsedTimeRec = System.nanoTime() - startTimeRec;
    double seconds = (double)elapsedTimeRec / 1000000000.0;
    System.out.println("Recursively, the function took " + seconds + " seconds.");

    prompt.close();

}
//create the linked list
public static LinkedList<Integer> randomList = new LinkedList<Integer>();

private static void iterateNumbers() {

    long startTime = System.nanoTime();
    for (int i = 0; i < randomList.size(); i++) {
        randomList.remove();
    }
    long elapsedTime = System.nanoTime() - startTime;
    double seconds = (double)elapsedTime / 1000000000.0;
    System.out.println("Iteratively, the function took " + seconds + " seconds.");
}

private static void recursiveNumbers(LinkedList<Integer> current) {     

    if (current.isEmpty() == true) {
        return;
    } else {
        current.removeFirst();
        recursiveNumbers(current);
    }
}

}

What did you get with this code? What is your exact question? — innoSPG
– innoSPG, Commented Mar 25, 2014 at 1:50

D0n9X1n · Accepted Answer · 2014-03-25 01:52:32Z

1

It's not very hard to understand. When you run your program, the stack area is not enough,so you have a error.

You can try to add the space of the stack.

run the program with the following arguments:

-Xss1280m

It means create the stack with 1280MB, and you will see the result like this:

enter image description here

answered Mar 25, 2014 at 1:52

D0n9X1n

2,1341 gold badge15 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Arkant0r Over a year ago

how would i go about running my program with those arguments? is it possible to make that statement within my code so it would automatically allocate a greater stack area for anyone who runs the program?

D0n9X1n Over a year ago

You can compile the java file first with the code javac Main.java, and run with the code:java -Xss1280m Main.And I write the shell script to run the program instead of run it directly.Here is my script:java -Xss1280m Main,and I just run with sh run.sh,and it works.If you are in windows, you can also write the .bat file.

Arkant0r Over a year ago

okay I gotcha, but is there any way to write in my .java file to create a stack with 1280MB?

D0n9X1n Over a year ago

I am not sure whether there is any way we can do that.But what I see is a script with a config file until now.

Siyuan Ren Over a year ago

@Arkant0r: I think it is not possible to specify the stack size from the java source code because it would be a security risk.

|

GermaineJason · Accepted Answer · 2014-03-25 01:42:07Z

1

In the iterative version , you should pass in the index at the remove.

randomList.remove(i);

And should you not also repopulate the linked list before you call the recursive method?

    for (int i = 0; i < amount; i++) {
    randomList.add(rnd.nextInt(100));
}

Not too sure about the Java implementation of the Linked List. Tried looking it up there. Is there a isEmpty() method? Or should you try:

if(current.size() < 1) 
    return;

answered Mar 25, 2014 at 1:42

GermaineJason

5896 silver badges15 bronze badges

2 Comments

Arkant0r Over a year ago

you're right I forgot to repopulate the list! Let me get back to you once i try that.

Arkant0r Over a year ago

Well I repopulated the list and passed the index at the remove statement but I'm still getting a stackoverflowerror when I create a linked list with 1,000,000 integers and then use the recursive function.

Collectives™ on Stack Overflow

Java remove an element from linked list recursion

2 Answers 2

8 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related