deep copy

[sannere]

题目是clone graph ,只给了第一个head，要求deep clone得到一个新的graph。这题答案的思路是第一步先用bfs遍历得到原来的图的全部的node，第二步复制所有的node， 第三步复制所有的边（即neighbor）。我的问题在第一步，bfs的子函数：

    private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashSet<UndirectedGraphNode> set = new HashSet<>();

        queue.offer(node);
        set.add(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode head = queue.poll();
            for (UndirectedGraphNode neighbor : head.neighbors) {
                if(!set.contains(neighbor)){
                    set.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return new ArrayList<UndirectedGraphNode>(set);
    }

---

Questions:

1. for循环遍历了一个节点的所有neighbor，在循环执行的时候，声明出来的neighbor是传引用还是传值？neighbor在for循环里被声明的时候，执行的不是下面语句吗：

   UndirectedGraphNode neighbor = new UndirectedGraphNode;
   neighbor = head.neighbors.get(index); 

2. 函数结束的返回语句：为什么需要new一个ArrayList？虽然数据结构要求必须返回ArrayList类型的结果，但是这种情况的话，设计的时候为什么要用HashSet，ArrayList也用一个方法containsKey作为判断来去重啊？如果我设计这个函数，函数内部存储结构用的就是ArrayList来存储所有的节点，直接返回这个list可以吗？我不知道老师绕这么一下的用意是什么？

@windmemory

[windmemory]

1. 没有执行你写的代码，而是用的每一个元素的引用，相当于

   UndirectedGraphNode neighbor = head.neighbors.get(index);

   并没有new的过程。你上面写的代码里面，new之后，那个neighbor就指向了A内存地址，这个地方存了刚刚new出来的那个实例。然后第二句赋值了之后，neighbor又指向了B内存地址，B存了之前数组里面的元素。

所以你要这样理解，有内存分配的地方会有新的东西创建，内存分配大多只发生在new的时候。没有看到new一般就不会有新的内存被分配。大多数情况下对非primitive类型的数据做操作的时候，都是在传引用。

2. 这个地方重新做一个ArrayList是为了后面处理的方便吧我猜。为什么一开始不用ArrayList肯定是性能考虑。ArrayList应该没有containsKey这个方法吧，可能有一个查找的方法，但是这个方法的效率肯定没有HashSet的高。从算法角度去分析，这个containsKey应该用O(n)的时间去查找。不是说这个函数不是自己写的，就不需要考虑函数的算法复杂度了。有时候这些系统函数也会比较慢的~所以在这个地方，先用Set收集，同时去重，然后最后转成ArrayList做后面的处理。