How does java store infinite recursive object

Question

The code below shows a data structure in leetcode. We can see the node1 store a list with node2 and node3, node2 will store a list with node1 and node4. In this case I think node1 and node2 will store the object of each others, which will cause an infinite recursion. How does java store the data structure like this, doesn't it cause a memory exceed?

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public static void main(String[] args) {
        Node node1 = new Node(1, new ArrayList<>());
        Node node2 = new Node(2, new ArrayList<>());
        Node node3 = new Node(3, new ArrayList<>());
        Node node4 = new Node(4, new ArrayList<>());

        node1.neighbors.add(node2);
        node1.neighbors.add(node4);

        node2.neighbors.add(node1);
        node2.neighbors.add(node3);

        node3.neighbors.add(node2);
        node3.neighbors.add(node4);

        node4.neighbors.add(node1);
        node4.neighbors.add(node3);

        Solution solution = new Solution();
        solution.cloneGraph(node1);
    }

Hi @Jackie. I can understand how this is confusing you. Your understanding is correct that each object stores the object of others. But do keep in mind that storing object happens in memory. Recursion is a technique of computation. Storing data in a certain way doesn't mean there will be recursion. Recursion happens when doing some computation. For eg. during a graph traversal (in this case), which would require solution engineer to handle cases where recursion can go in to infinite loop. You should try solving some graph traversal problem to get the hang of it. — Master Chief, Oct 21 '20 at 04:22

score 2 · Accepted Answer · edited Oct 21 '20 at 04:23

You would be correct about this code causing memory to be exceeded if each node's list of neighbours contained copies of those neighbours. But that's not how Java works. Instead the list contains references to the neighbour nodes.

As an analogy, if each time you wrote down someone's address you need a complete copy of their house then you'd run out of space quickly. But you don't - you just need a reference to their house which can itself contain a reference to yours.

Note that's it's pretty easy to write code that causes a stack overflow with objects that contain references to themselves. For example, if your class had a method:

class Node {
    public int sumVals() {
        return val + neighbours.stream().mapToInt(Node::sumVals).sum();
    }
}

calling node1.sumVals() will cause infinite recursion.

How does java store infinite recursive object

1 Answers1