CODEWITHSUNDEEP
recursion
xtruexwolfx
xtruexwolfx

Reputation: 41

Recursively turning a stack into a linked list

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.

Upvotes: 4

Views: 167

Answers (2)

D.B.
D.B.

Reputation: 4713

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.

Upvotes: 0

Harsh Gupta
Harsh Gupta

Reputation: 4538

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.

Upvotes: 1

Related Questions