英文:
How does java store infinite recursive object
问题
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);
}
英文:
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);
}
答案1
得分: 2
关于这段代码导致内存超限，你的理解是正确的，如果每个节点的邻居列表包含那些邻居的副本，那就会出现内存超限的问题。但是 Java 并不是这样工作的。相反，列表中包含对邻居节点的引用。
类比一下，如果每次你写下某人的地址都需要他们房子的完整副本，那么很快就会耗尽空间。但实际上不是这样的——你只需要一个对他们房子的引用，它本身可以包含对你房子的引用。
需要注意的是，编写会导致对象相互引用从而导致堆栈溢出的代码相当容易。例如，如果你的类有一个方法：
class Node {
public int sumVals() {
return val + neighbours.stream().mapToInt(Node::sumVals).sum();
}
}
调用 node1.sumVals() 将会导致无限递归。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论