Recursively turning a stack into a linked list

Question

so I have been working on a programming assignment that involves taking a stack implementation of size ~13,000 and turning it into a linked list. The guide is basically that the stack was filled by sequentially scanning a linked list (IE tail would be the top of the stack), and you want to re create the linked list using the stack. The trick is you have to do it using a recursive method. The only methods in this stack class are pop (returns and removes the top element), and isEmpty(tells if the stack is empty). I have code that gets the job done, however it requires increasing the java stack size (otherwise I get StackOverflowError), which I feel like that isn't allowed.

That being said does anyone know a way I could possibly get this to work without increasing the java stack size.

The stack is a static field I have labeled S. Head is what should be the first node in the linked list, and steper is simply a node to be used to create every other step.

Here is the code I currently have:

public static void stackToList()
{
    int x = 0;
        if(S.isEmpty())
        {
            return;
        }
        x = S.pop();
        stackToList();
        if (head == null)
        {
            head = new ListNode(x, null);
            steper = head;
        }
        else
        {
            steper.next = new ListNode(x, null);
            steper = steper.next;
        }

}

Thank you ahead of time for any help.

Just to clarify , When you say "stack size" are you referring to Java call stack during recursion calls? because you stack 'S' doesn't increase if you are reading from it! — Ravi Yenugu, Sep 30 '16 at 13:25
When I say I increase the stack size, I mean a added a argument in run configurations like -Xss2m — xtruexwolfx, Sep 30 '16 at 13:28

score 1 · Answer 1 · edited May 23 '17 at 10:27

It is happening because you are keeping an entire list of function calls in memory stack. You start creating your linked list only after you reach to the bottom of the stack thus keeping all the previous calls to stackList waiting to be over.

You need to start creating your linked list with the first pop of stack.

A simple & non tested (not worked in Java in a very long time now) function may look like:

public static ListNode stackToList(ListNode head) {
    if(S.isEmpty())
        return head;

    int stackValue = S.pop();
    ListNode node = ListNode(stackValue, null);
    node.next(head);
    return stackToList(node);
}

And you call it like:

ListNode head = stackToList(null)

HTH

EDIT: Now that I posted it, I realized that my code has potentially the same issue as yours, because I remembered Java doesn't support tail-call optimization.

Sorry for the slow response I was at school. Your code works fine as far as creating the same list, but it does also encounter the stack overflow. At this point I have just wrapped it in a try catch that for the catch calls the method again. Obviously this is far from ideal, but the professor has explicitly stated now that we cant increase the java stack size, so I'm at a loss as to how expects us to fix it otherwise. — xtruexwolfx, Sep 30 '16 at 18:59

D.B. · Answer 2 · 2016-09-30T14:12:57.753

It's not entirely clear from your question if you're using java.util.LinkedList and java.util.Stack but since you didn't provide the code for these objects I will be using those in my example solution below:

public static void main(String[] args) {
    //Create a stack
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.push(6);
    stack.push(7);
    stack.push(8);
    stack.push(9);

    //Create a list to hold your stack elements
    LinkedList<Integer> linkedList = new LinkedList<Integer>();

    //Call the conversion method, which modifies both the stack and the list
    convertStackToLinkedList(stack, linkedList);

    //print the results
    System.out.println("linkedList: "+linkedList);
}

public static void convertStackToLinkedList(Stack<Integer> stack, LinkedList<Integer> linkedList){
    int topStackElement = stack.pop();
    linkedList.add(0,topStackElement);
    if(!stack.isEmpty())
        convertStackToLinkedList(stack, linkedList);
}

I suspect you may not be using java.util.LinkedList since your code is attempting to modify the internals of the list. So, you would simply need to implement a method similar to that of the add(int index, E element) method in the java.util.LinkedList class and then use it in your recursion. I assume you can do this if you have access to the internals of the list.

EDIT:

I forgot to mention that I agree with the answer by Harsh Gupta in that the reason you're seeing StackOverflowError is that you're waiting until you reach the end of your recursion to modify your list. In some recursion you have to wait until the end but if you don't have to wait don't do it.

Recursively turning a stack into a linked list

2 Answers2