CODEWITHSUNDEEP
javadata-structureslinked-listtostringswap
mamba-mentality24
mamba-mentality24

Reputation: 13

Stack overflow from recursive toString function after swapping Linked List nodes

I am getting a stack overflow when I am using my recursive toString function on my Linked List after I am swapping the head node and another node in the middle of my Linked List. I am not sure as why this is happening and was hoping I can get some guidance of what is actually going on. It seems that before my swap function executes, the toString is working completely fine, but as soon as I swap the nodes I happen to get a stack overflow error in my recursive toString function.

My Linked List class: 

public class LinkedList {
    //
    //Instance variable
    //
    private Node top;

    //
    //Instance and static methods below
    //

    //Accessor for the top Node
    public Node getTop() {
        return top;
    }

    public Node getPreviousNode(Node toFind) {
        //call getPreviousNodeRec() method
        if (top.equals(toFind))
            return null;
        else
            return getPreviousNodeRec(top, toFind);
    }

    private Node getPreviousNodeRec(Node start, Node toFind) {
        if (start.getLink().equals(toFind)) {
            return start;
        } else
            return getPreviousNodeRec(start.getLink(),toFind);
    }

    public void swap(Node n1, Node n2) {
        if (top.equals(n1)) {
            System.out.println("top equals n1");
            Node n2prev = getPreviousNode(n2);
            Node temp = n2.getLink();

            top = n2;
            top.setLink(n1.getLink());
            n1.setLink(temp);
            n2prev.setLink(n1);

            System.out.println("complete");
        }
    }

    public String toString() {
        if (top == null)
            return "There is nothing in the list!";
        else {
            String value = "";
            return toStringRec(top, value);
        }
    }

    private String toStringRec(Node start, String value) {
        if (start.getLink() != null) {
            value += start.getData()+"\n";
            return toStringRec(start.getLink(),value);
        } else
            return value+start.getData();
    }

    public void setTop(Node top) {
        this.top = top;
    }
}

Right now I am just trying to test my swap method for one case(top = n1).

This is my main method: 

public static void main (String[] args) {
    //Testing the getPreviousNode method
    LinkedList myList = new LinkedList();

    myList.add(-700);
    myList.add("hello");
    myList.add(12);
    myList.add(55);
    myList.add(13000);
    myList.add("world");
    myList.add("pizza");
    myList.add(870);

    System.out.println("The previous node of the node containing 12 is the Node containing \"hello\":");

    System.out.println(myList.getPreviousNode(
         myList.getTop().getLink().getLink()).getData());
    System.out.println();

    //Testing swap:
    System.out.println("The initial list is:");
    System.out.println(myList);

    System.out.println();
    System.out.println("Now swapping the first and second nodes, and the result is:");
    myList.swap(myList.getTop(), myList.getTop().getLink());
    System.out.println(myList);
}

Upvotes: 0

Views: 95

Answers (2)

koger
koger

Reputation: 11

It is because at the part

top = n2;
top.setLink(n1.getLink());

n1.getLink() still points at n2, so you make top.getLink() point to top.

Upvotes: 0

Salem
Salem

Reputation: 1

Your methods works if n1 and n2 are 2 nodes apart, in the case they are next to each other like in your example where you do this line:

top.setLink(n1.getLink());

You are pointing n2 link to itself. You need to check if n1 and n2 and if they do point top to n2, n1.link to n2.link and n2.link to n1.

Upvotes: 0

Related Questions